이 문제는 모두 6팀만이 푼 문제로, 1등을 한 WE ARE BUT MEN, ROCK! 팀이 유일하게 풀지 못한 문제라고 하네요. 제출 성공률도 16% 밖에 되지 않으니 어려운 문제라는 건 누가 봐도 명약관화한 사실이겠죠.
이 문제를 가장 까다롭게 하는 것은 우리가 커버해야 할 영역이 원형을 이루고 있다는 것입니다. 1차원 상에서는 쉽게 풀리던 문제도
이와 같이 끝과 끝을 이어서 환형으로(circular) 바꾸어 놓으면 어려워지는 일이 다반사죠. 대개 이와 같은 조건을 해결하기 위해서는 한 점에서 이 원을 끊어서 1차원 문제로 변형하는 방식을 적용하는 것이 효과적입니다. 따라서 더 이상의 얘기를 하기 전에, 이 문제가 원형이 아니라 직선이었다면 어떻게 되었을까를 먼저 생각해 보도록 하죠. 만약 이 문제에서 감시해야 할 영역이 원이 아니라 선분이었다면 어떻게 되었을까요?
직선 버전의 문제
1 부터 100,000 까지의 칸이 일렬로 늘어서 있고, 입력에 주어진 구간들 중 일부를 선택해서 이 칸들을 모두 덮어야 합니다. 모든 구간의 영역은 a,b 으로 주어집니다. 선택해야 하는 구간의 최소 수는?
이 직선 버전의 문제는 사실 굉장히 유명한 문제로, 욕심쟁이 방법(Greedy method) 을 이용해서 풀 수 있습니다. 어떻게 푸냐고요?
1번칸을 포함하는 구간 중 가장 오른쪽으로 길게 가는 것을 선택합니다. 이 구간의 오른쪽 끝을 a 라고 합시다.
a+1 번 칸을 포함하는 구간 중 가장 오른쪽으로 길게 가는 것을 선택합니다. 이것을 100,000 번 칸까지 모두 덮을 때까지 반복합니다.
이렇게 해서 이 문제의 최적해를 구할 수 있습니다. 간단한 증명은 다음과 같습니다.
1번칸을 포함하는 구간 [1,a] 와 [1,b] 가 있어서 a < b 라고 합시다. 만약 최적해에는 [1,a] 가 포함된다고 해도 거기서 [1,a] 를 빼고 [1,b] 를 넣으면 같은 개수의 구간으로 또 다른 답을 만들 수 있죠. 따라서 반드시 최적의 선택을 할 수 있습니다.
a번칸까지 커버가 되었다면, 남은 구간에서 [1,a] 와 겹치는 부분은 의미가 없죠. 이들과 겹치는 부분을 다 지워도 답은 변하지 않을 것입니다. 그러고 보면 1. 과 같은 문제가 됩니다.
좀 더 포멀한 증명은.. 음, 독자 여러분에게 맡기겠습니다. :p 하여간 이와 같은 그리디 알고리즘을 intuit 하기 쉬운 것은 사실입니다. 이와 같은 그리디 알고리즘은 모든 구간을 구간의 시작 위치에 오름차순으로 정렬한 뒤 O(n) 으로 간단하게 구현할 수 있습니다. (따라서 전체 시간 복잡도는 O(nlgn) 이 되겠죠.)
원 버전의 문제
자 그러면 다시 우리의 원(circle) 버전으로 돌아가 봅시다. 1번 칸과 100,000번 칸이 연결되어 있어서 구간이 wraparound 할 수 있다는 조건을 추가해야겠지요. 이제 직선 버전의 그리디 알고리즘을 그대로 적용할 수는 없습니다. 따라서 어딘가에서 적절히 이 원을 끊어서 선분으로 펴 봅시다. 자연스럽게, 1번 칸과 100,000번 칸 사이를 끊어서 직선으로 만들 생각을 하게 되겠지요. 에.. 물론 그냥 하면 안 되겠죠? 이 때 최적해에 대해 두 가지 경우가 있을 수 있습니다.
최적해에 포함된 구간들 중, [100000,1] 을 포함하는 구간이 없는 경우: 따라서, 1차원으로 변환해서 문제를 풀어도 답은 변하지 않습니다. (이 때 [100000,1] 을 포함하는 구간들은 무시해도 되겠지요. ^^)
최적해에 포함된 구간들 중, [100000,1] 을 포함하는 구간이 있는 경우
어려운 것은 2. 경우의 답을 구하는 것입니다. 2. 경우를 풀기 위해, 최적해 중에 [100000,1] 을 포함하는 구간이 있다고 가정하고 알고리즘을 설계하겠습니다. 이 를 구하는 방법은 많은 직관을 필요로 하는데요, 바로 이 원을 연장해서 두 바퀴 돌리는 것입니다. :) 그러니까, 1번 칸부터 100,000번 칸까지가 아니라 200,000번 칸까지로 만드는 것이지요. 다르게 말하자면, [0,2*pi] 구간으로 구성되어
있던 원을 [0,4*pi] 구간으로 확장한다고 할 수 있습니다. 그 후, 1번 칸과 200,000번 칸 사이를 끊어서 이를 선분으로 만듭니다.
이 때 각 구간들은 2개에서 3개로 늘어나게 됩니다. 예를 들어 [100,200] 구간은 [100,200] 과 [100100,100200] 구간의 두 개로 늘어나게 되겠지요. 원래 [100000,1] 을 포함하던 구간들은 3개로 늘어나게 됩니다. 예를 들어 [100000,1] 은, [1,1],
[100000,100001] 과 [200000,200000] 의 세 개 구간으로 늘어나게 됩니다.
이렇게 변형된 문제에 대해서 선형 버전의 그리디로 답을 구합니다. 이 답에 포함된 구간의 개수를 a 라고 하고, 원래 문제의 최적해에 포함된 구간의 개수를 b 라고 합시다. 이 때 a >= b 는 자명하죠. (하물며 두 배 길이의 구간을 그리디로 덮었는데 좋아질 순 없으니까요.) 그런데 a 의 상한은 얼마일까요? a 는 2b 보다 클까요? 아니면 클 수 없을까요? 정답은 a <= 2b 입니다. 왜냐구요?
[1,200000] 을 모두 덮기 위해 2b 개의 구간을 사용할 수 있습니다. 최적해에 포함된 b개를 가져와서 [1,100000] 을 일단 덮고, [100001,200000] 은 이 b개들의 오른쪽에 반사된 버전으로 덮으면 되니까요. (사실은 a <= 2b-1 을 보일 수도 있지만 생략하겠습니다. ^^)
이게 왜 중요하냐 하면, 이 그리디의 답에 포함된 a개의 구간 중 한 부분에 반드시 최적해 (b개의 구간만을 써서 100,000 길이를 커버하는 해)가 존재한다는 데 쓸 수 있기 때문입니다. :) 이것을 어떻게 증명할까요? 만약 최적해가 없다면, a개의 구간 중 어떤 연속된 b개의 구간을 잡아도 이들 길이의 총합이 100,000 보다 작아야 합니다. 그런데, a <= 2b 입니다. 첫 b개의 구간과 마지막 b개의 구간을 잡고 이 합을 구해도 이 합이 200,000 보다 작아야겠지요? 그런데 a는 [1,200000] 을 덮는 답이기 때문에 모순이 됩니다. 따라서, a에 포함된 구간 중 연속된 b개를 잡았을 때 반드시 100,000 을 넘는 구간들이 최소한 하나는 있어야 합니다.
그러므로, 이 문제는 이 원을 두 바퀴 돌려서 선분으로 만든 뒤 이를 그리디로 해결하고, 이 중 총 길이가 100,000 이 넘는 구간들의 최소 수를 구하는 문제로 변형될 수 있습니다. 이 구간들의 최소 수를 구하는 문제는 지금까지 오기 위한 과정에 비하면 쉬운 편이니까
생략할께요. O(n) 에 된다는 것만 아시면 됩니다. ^^
그래서 이 문제는 O(nlgn) 의 전처리 과정에 이은 O(n) 그리디 알고리즘과 O(n) 스캐닝 알고리즘으로 해결할 수 있습니다.
JongMan
문제 보러 가기
이 문제는 모두 6팀만이 푼 문제로, 1등을 한 WE ARE BUT MEN, ROCK! 팀이 유일하게 풀지 못한 문제라고 하네요. 제출 성공률도 16% 밖에 되지 않으니 어려운 문제라는 건 누가 봐도 명약관화한 사실이겠죠.
이 문제를 가장 까다롭게 하는 것은 우리가 커버해야 할 영역이 원형을 이루고 있다는 것입니다. 1차원 상에서는 쉽게 풀리던 문제도
이와 같이 끝과 끝을 이어서 환형으로(circular) 바꾸어 놓으면 어려워지는 일이 다반사죠. 대개 이와 같은 조건을 해결하기 위해서는 한 점에서 이 원을 끊어서 1차원 문제로 변형하는 방식을 적용하는 것이 효과적입니다. 따라서 더 이상의 얘기를 하기 전에, 이 문제가 원형이 아니라 직선이었다면 어떻게 되었을까를 먼저 생각해 보도록 하죠. 만약 이 문제에서 감시해야 할 영역이 원이 아니라 선분이었다면 어떻게 되었을까요?
직선 버전의 문제
1 부터 100,000 까지의 칸이 일렬로 늘어서 있고, 입력에 주어진 구간들 중 일부를 선택해서 이 칸들을 모두 덮어야 합니다. 모든 구간의 영역은 a,b 으로 주어집니다. 선택해야 하는 구간의 최소 수는?
이 직선 버전의 문제는 사실 굉장히 유명한 문제로, 욕심쟁이 방법(Greedy method) 을 이용해서 풀 수 있습니다. 어떻게 푸냐고요?
이렇게 해서 이 문제의 최적해를 구할 수 있습니다. 간단한 증명은 다음과 같습니다.
좀 더 포멀한 증명은.. 음, 독자 여러분에게 맡기겠습니다. :p 하여간 이와 같은 그리디 알고리즘을 intuit 하기 쉬운 것은 사실입니다. 이와 같은 그리디 알고리즘은 모든 구간을 구간의 시작 위치에 오름차순으로 정렬한 뒤 O(n) 으로 간단하게 구현할 수 있습니다. (따라서 전체 시간 복잡도는 O(nlgn) 이 되겠죠.)
원 버전의 문제
자 그러면 다시 우리의 원(circle) 버전으로 돌아가 봅시다. 1번 칸과 100,000번 칸이 연결되어 있어서 구간이 wraparound 할 수 있다는 조건을 추가해야겠지요. 이제 직선 버전의 그리디 알고리즘을 그대로 적용할 수는 없습니다. 따라서 어딘가에서 적절히 이 원을 끊어서 선분으로 펴 봅시다. 자연스럽게, 1번 칸과 100,000번 칸 사이를 끊어서 직선으로 만들 생각을 하게 되겠지요. 에.. 물론 그냥 하면 안 되겠죠? 이 때 최적해에 대해 두 가지 경우가 있을 수 있습니다.
어려운 것은 2. 경우의 답을 구하는 것입니다. 2. 경우를 풀기 위해, 최적해 중에 [100000,1] 을 포함하는 구간이 있다고 가정하고 알고리즘을 설계하겠습니다. 이 를 구하는 방법은 많은 직관을 필요로 하는데요, 바로 이 원을 연장해서 두 바퀴 돌리는 것입니다. :) 그러니까, 1번 칸부터 100,000번 칸까지가 아니라 200,000번 칸까지로 만드는 것이지요. 다르게 말하자면, [0,2*pi] 구간으로 구성되어
있던 원을 [0,4*pi] 구간으로 확장한다고 할 수 있습니다. 그 후, 1번 칸과 200,000번 칸 사이를 끊어서 이를 선분으로 만듭니다.
이 때 각 구간들은 2개에서 3개로 늘어나게 됩니다. 예를 들어 [100,200] 구간은 [100,200] 과 [100100,100200] 구간의 두 개로 늘어나게 되겠지요. 원래 [100000,1] 을 포함하던 구간들은 3개로 늘어나게 됩니다. 예를 들어 [100000,1] 은, [1,1],
[100000,100001] 과 [200000,200000] 의 세 개 구간으로 늘어나게 됩니다.
이렇게 변형된 문제에 대해서 선형 버전의 그리디로 답을 구합니다. 이 답에 포함된 구간의 개수를 a 라고 하고, 원래 문제의 최적해에 포함된 구간의 개수를 b 라고 합시다. 이 때 a >= b 는 자명하죠. (하물며 두 배 길이의 구간을 그리디로 덮었는데 좋아질 순 없으니까요.) 그런데 a 의 상한은 얼마일까요? a 는 2b 보다 클까요? 아니면 클 수 없을까요? 정답은 a <= 2b 입니다. 왜냐구요?
[1,200000] 을 모두 덮기 위해 2b 개의 구간을 사용할 수 있습니다. 최적해에 포함된 b개를 가져와서 [1,100000] 을 일단 덮고, [100001,200000] 은 이 b개들의 오른쪽에 반사된 버전으로 덮으면 되니까요. (사실은 a <= 2b-1 을 보일 수도 있지만 생략하겠습니다. ^^)
이게 왜 중요하냐 하면, 이 그리디의 답에 포함된 a개의 구간 중 한 부분에 반드시 최적해 (b개의 구간만을 써서 100,000 길이를 커버하는 해)가 존재한다는 데 쓸 수 있기 때문입니다. :) 이것을 어떻게 증명할까요? 만약 최적해가 없다면, a개의 구간 중 어떤 연속된 b개의 구간을 잡아도 이들 길이의 총합이 100,000 보다 작아야 합니다. 그런데, a <= 2b 입니다. 첫 b개의 구간과 마지막 b개의 구간을 잡고 이 합을 구해도 이 합이 200,000 보다 작아야겠지요? 그런데 a는 [1,200000] 을 덮는 답이기 때문에 모순이 됩니다. 따라서, a에 포함된 구간 중 연속된 b개를 잡았을 때 반드시 100,000 을 넘는 구간들이 최소한 하나는 있어야 합니다.
그러므로, 이 문제는 이 원을 두 바퀴 돌려서 선분으로 만든 뒤 이를 그리디로 해결하고, 이 중 총 길이가 100,000 이 넘는 구간들의 최소 수를 구하는 문제로 변형될 수 있습니다. 이 구간들의 최소 수를 구하는 문제는 지금까지 오기 위한 과정에 비하면 쉬운 편이니까
생략할께요. O(n) 에 된다는 것만 아시면 됩니다. ^^
그래서 이 문제는 O(nlgn) 의 전처리 과정에 이은 O(n) 그리디 알고리즘과 O(n) 스캐닝 알고리즘으로 해결할 수 있습니다.
이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기
16년 전