구사과

1. Mountain RoadA 타입 차와 B 타입 차를 분리시키고 생각해 보자. 각각의 그룹에서 먼저 도착한 순서대로 차들을 처리해야 하니, A 차가 현재 몇 대 까지 / B 차가 현재 몇 대 까지 처리되었는지 정도의 상태로 DP를 돌려보자.A와 B가 항상 교차해서 나온다면 단순히 끝나는 시간만을 고려해주면 되겠지만, 실제로 A 차가 연속하거나 B 차가 연속할 경우에는 일련의 추가적인 규칙들이 있다. 고로, 현재의 DP 상태에서 연속한 A 차를 추가하거나, 연속한 B 차를 추가해서 새로운 DP 상태의 시간을 계산해야 한다. 또한, 마지막에 A를 썼는데 거기에 연속한 A 차들을 추가하면 계산이 꼬이니, 현재의 DP 상태는 단순히 차를 몇 대 쓴 것만이 아니라, 마지막에 무슨 차를 썼는지 역시 저장해야 한..

1. 텔레점프아이디어의 큰 틀은 생각보다 간단하다. 다만 이를 실제로 완성하는 건 꽤 까다로운 문제이다. * 먼저 처음에 A 에지 하나와 B 에지 모두를 소모해서, 앞 부분의 점을 다 연결 시켜준다. 1 - 2 / 1 - 3 / 2 - 4 / 3 - 5 ... * 이제 A 에지와 C 에지만이 남았다. B 에지로 만든 path의 두 끝 점 중 하나는 버리고 (즉 시작점으로 하고), 나머지 하나를 이어나갈 것인데, P / P + 3 / P + 6 ... 이런 식으로 이으면 중간에 공백이 생기니, A 에지를 하나 사용해서 P + 1 - P + 2를 이어주고, P + 1 / P + 4 ... 혹은 P + 2 / P + 5 ... 를 계속 이어준다. C 에지를 전부 소모할 때까지 이를 계속한다. * 남은 에지들은..

1. ČVENK점 (x, y)가 빈 공간이기 위해서는 x & y = 0이 성립해야 한다. 이 점에서는 항상 (0, 0)으로 가는 경로가 존재하는데, 다음과 같은 방법으로 이를 찾을 수 있다. * x == 0 || y == 0일 경우에는 자명하게 경로를 찾을 수 있다. * x와 y가 모두 0이 아니라고 가정하자. lowest significant bit (LSB) 가 작은 쪽을 찾자. 여기서는 일반성을 잃지 않고 x라고 한다. 그렇다면, (x - LSB(x), y) - (x, y) 를 잇는 경로는 비어 있다. (x - LSB(x), y) 에서 재귀적으로 계속 경로를 찾아나간다.이 경로는 항상 존재하며 유일하다. 이는 빈 공간들이 트리를 이룬다는 증명이 되기도 한다. (사실 그건 사진을 보면 쉽게 눈치챌 수..

1. 숫자카드간단한 동적 계획법이다. 문자열을 길이 1 / 길이 2의 문자열로 분해하는 경우의 수를 세는 것인데, dp[i] = 앞 i자리 문자를 모두 분해하는 경우의 수라고 하면, dp[i-1]과 dp[i-2]에 대한 점화식이 나오고, 이를 통해 해결할 수 있다. 2. 놀이공원배열을 통해서 각 1분 단위의 시간에 휴식이 가능한지를 관리한다. 놀이기구 하나에 대해서, (시작 시간 - 10분) ~ (종료 시간 + 10분) 동안은 휴식이 불가능하다. 고로 각 놀이기구 마다 이 구간에 체크해 두면, 해당 단위 시간에 휴식이 가능한 지 알 수 있다. 이 정보를 안다면, 이 정보를 안다면, 가장 긴 휴식 가능 구간을 구하는 문제는, 0과 1로 이루어진 배열에서, 가장 긴 0으로 이루어진 연속 구간을 구하는 문제가..

1. 워크스테이션 배정그리디 알고리즘으로 해결할 수 있다. 모든 배정을 시작점 순으로 정렬하자. i번 배정을 할 때, 만약에 이미 끝난 다른 배정 중, 끝난 시간과 현재 시간과의 M 이하인 것이 있다면 그 배정과 같은 워크스테이션을 쓴다고 생각하자. 만약에 그러한 배정이 여럿 있다면 차이를 최대화 하는 것이 이득이다. (차이를 괜히 작게 줘 봤자 시작점이 큰 다른 배정에게 도움이 안 되니까) 이러한 그리디 알고리즘을 priority queue 등으로 구현하면 O(nlgn)에 문제를 해결할 수 있다. 2. Identifying Map Tiles주어진 문자열을 비트마스크로 읽어서 출력하면 되는 단순 구현 문제이다. (사실 1번 2번은 일단 placeholder로 넣은 거였습니다. 즉 나중에 다른 문제로 고칠..

1. Kralj원형 구조에서 푸는 문제들은 그대로 풀면 짜증나거나 어려운 경우들이 많기 때문에 선형 구조로 환원시키는 것이 중요하다. 이 문제에서도 그러한 것이 가능하다. 어떠한 자리 i에 대해서, 어떤 몬스터들은 그 자리에 앉기 위해 달려들 것이고, 어떤 몬스터들은 그 자리에 실제로 앉을 것이다. flux(i) = (i번째 자리에 앉으려고 온 몬스터의 수) - 1이라고 하자. 1은 그 자리에 실제로 앉아서 싸우는 몬스터를 뜻한다. flux(i)의 부분합을 한번 그래프로 그려보자. 0점에서 올라갔다 내려갔다 했다가 다시 0점으로 오게 될 것이다. 이 중 최소를 찍는 위치가 있는데, 여기를 중심으로 왼쪽과 오른쪽 구간을 바꿔보자 (cyclic shift). 그렇다면, 이 그래프는 0점에서 올라가다가 내려가..

1. 점 고르기모든 n^2개의 점을 잡아서, 두 점을 최대 / 최소로 하는 직사각형이 존재할 수 있는지를 판별하면 간단하게 풀 수 있다. 이 존재성은 단순한 O(1) 식으로 판단할 수 있어서, 시간 복잡도는 n^2이다. 난 n^2lgn에 풀었는데 내 풀이는 부끄러우니 설명을 생략한다... 2. Number SetsP 이상의 모든 prime factor를 열거해야 할 것 같지만, 실제로 필요한 건 P 이상 1000000 이하의 prime factor 뿐이다. 1000001 이상의 prime factor는 중요하지 않은 게, B - A

1. MP3 Songs아무 생각 없이 아스키 순으로 정렬하면 나옴. 앞으로는 셋에 이런 문제를 넣지 않겠습니다. 2. Reconstruction Trees올바른 입력임을 가정할 때 preorder와 inorder가 주어지면 유일하게 트리를 결정할 수 있다. preorder의 맨 앞에 있는 원소가 루트이고, inorder에서 이 루트를 찾으면, 왼쪽 서브트리와 오른쪽 서브트리를 찾을 수 있다. 우리는 여기서 루트와, 왼쪽 서브트리의 preorder / inorder, 오른쪽 서브트리의 preorder / inorder를 찾을 수 있기 때문에 재귀적으로 전체 트리 모형을 유추할 수 있다. 이 트리를 postorder traversal하면 된다. 여담으로 트리를 만든다는 식으로 서술했지만 실제로는 찾아가면서 ..

다음과 같은 문제를 생각해 보자.크기 N의 수열이 있을 때, 길이 K 이상인 구간 중 최대 평균을 계산하라. 식을 전개해 보자. 주어진 입력의 부분합을 Si 라고 하면, j - i >= K 일 때 (Sj - Si) / (j - i) 를 최대화해야 한다. 하지만 그렇게 쉬워 보이지 않는다. 어떻게 해야 할까?1. 답에 대한 이진 탐색어떠한 문제의 가능한 최대 / 최솟값을 계산하기 위해서, 문제를 결정 문제로 바꿔서 이진 탐색을 하는 방법이 잘 알려져 있다. 예를 들면, "가능한 답 중 최댓값을 계산하라" 는 문제를, "X 이상이 이 문제에서 가능한 답인지를 판단하라"는 문제로 바꾸면, 가능한 답 중 최대인 X를 이진 탐색으로 판별할 수 있다. 만약에 최댓값을 계산하는 것은 어렵지만, X 이상이 가능한 답인..

https://www.acmicpc.net/problem/8128증명에 증명을 더해가면서 시간 복잡도를 줄이는 스타일의 그리디였는데 재밌었다. 일단 먼저 N^2 알고리즘을 목표로 시작해보자. 가장 많은 역을 덮는 지하철 노선의 집합을 최적 집합이라고 한다. Lemma 1. 최적 집합의 모든 끝점을 리프로 변형시킬 수 있다.증명 : 그렇지 않은 최적 집합이 존재한다면 이를 두고 생각해 보자. 만약에 현재 끝점이 리프가 아니면, degree가 2 이상이라 빠져나갈 구멍이 하나 존재한다. 이 구멍으로 경로의 길이를 증가시켜나가면 답을 감소시키지 않으면서 한쪽을 리프로 만들어 줄 수 있다. Lemma 2. 최적 집합에 덮인 지하철역이 서브트리를 이루게 변형시킬 수 있다. (이 때 서브트리는 subgraph로써의..