6개의 댓글이 있습니다.
-
-
amok -
이런 답이 질문의 의도에 맞는건지는 모르겠지만... 문제를 분할했을 때, 분할된 문제들을 원래의 문제보다 훨씬 빠르게 풀 수 있기 때문이 아닐까요.
예를 들어 brute force로 O(n^2)시간이 걸리는 정렬 문제에 대해 생각해봅시다. 정렬해야 할 배열의 길이가 원래 길이의 절반이라면, 그 절반짜리 문제를 brute force로 푸는 데 걸리는 시간은 1/4로 줄어들겠죠. 원래 문제의 1/4 시간이 걸리는 문제를 두 번 풀어도 원래 문제를 푸는 데 걸리는 시간의 1/2(=1/4+1/4)밖에 되지 않습니다. 배열을 병합하는 데 걸리는 시간을 무시한다면, 이렇게 해서 문제를 푸는 데 걸리는 시간을 절반으로 줄일 수 있습니다. 분할 정복을 이용해서 문제를 푸는 데 걸리는 시간을 줄인 것이죠. 실제로는 이러한 과정을 재귀적으로 적용하고 병합하는 데 걸리는 시간이 있기 때문에 O(nlogn)이 됩니다.
또 다른 예로 정렬된 배열을 검색하는 문제에 대해 생각해봅시다. brute-force로는 O(n)이 걸리는 문제입니다. 배열의 길이가 원래 배열의 길이의 절반이라면, 문제를 푸는 데 걸리는 시간도 절반이 되겠죠. 이때, 두 개로 분할된 문제 중 하나는 안 풀어도 됩니다! 문제를 푸는 데 걸리는 시간이 절반으로 줄어든 것이죠. 이 과정을 재귀적으로 적용하고, 문제를 분할하는 데 걸리는 상수시간을 고려하면 O(logn)만큼의 시간이 걸립니다.
8년 전 link
-
-
-
philosup -
본질 이야기가 나와서 말인데요.
분할정복이 무조건 brute force보다 빠르다는 보장은 없습니다.
분할정복으로 풀 수 있는 문제는 따로 존재하지요.
왜 그럴까요?문제를 나누고 나눈문제를 다시 합치면서 어떠한 이점이 있기 때문입니다
이런게 가능한 문제들만 분할정복을 하는거죠.
그러니 '분할정복이 알고리즘을 빠르게 만드는 요인'이라는건 각 문제별로 조금씩 다를수밖에 없습니다.그걸 캐치하고 이 문제는 분할정복으로 풀어야 겠구나라는 판단을 내려야 하는거죠.
병합정렬에서의 분할정복의 이점은 amok님이 잘 설명해주셨네요.
다른 알고리즘도 같은 방법인 경우도 있고 전혀 다른 이점으로 분할정복을 하는 경우도 있습니다.결국 이거다 라는 답은 없고 각 알고리즘을 잘 이해하는 수밖에 없다고 생각되네요.
8년 전 link
-
-
-
Jaekwan -
답변 감사드려요.
분할 정복은 여러가지 알고리즘 패러다임 중 하나로 알고 있어요. 알고리즘에서 말하는 패러다임은새로운 알고리즘을 만들어 내는데 쓸 수 사용할 수 있는 사고방법 정도로 이해하고 있구요. 욕심쟁이나 동적계획법도 그런 패러다임 중 하나일 뿐 알고리즘이라고 부르기에는 어폐가 있구요. 따라서 문제에 따라 여러 패러다임 중 적용될 수도 있고 없을 수도 없다는 것은 이해하고 있습니다.
Amok님이 말씀 주신 것처럼 1/2(=1/4+1/4)의 처리를 만들게 되는 원인에 대해서 좀 더 이해를 하고 싶어 "본질"이라는 단어를 꺼냈네요.
가령, N크기의 배열이 있고 가장 빠르게 이 배열을 고칠 수 있는 한계는 O(N)입니다. 최소한 [1..N]에 방문을 해서 그 값을 바꿔야 할 수 밖에 없다고 보거든요. 이 선상에서 brute force 알고리즘이 O(N^2)인 이유 또한 각 방문시 N만큼의 연산이 더 필요하기 때문에 N^2되는 것이구요. 그리고 병합 정렬또한 각 배열에 무조건 한번은 방문(O(N))해야만 한다는 가정을 했을때, 나머지 연산은 logN이 되는 것이고 총 연산 시간이 NlogN으로 된다고 볼 수 있다고 생각합니다.즉 총 연산 시간에서 각 배열의 셀에 방문시간을 제외하면 연산시간이 N->logN으로 줄어 든 것이죠. ( 좀 억지같지만 병합정렬의 케이스에서는 타당하다고 생각합니다.)
문제를 조금 더 자세하게 말하지면,
분할 정복이 특정 문제에서 더 빠르게 연산할 수 있다는 것은 수학적으로 이해는 가는데, 분할 정복이 더 빠르게 되는 원인?에 대한 생각을 듣고 싶어요.
8년 전 link
-
-
-
astein -
일단 병합 정렬의 시간복잡도가 O(N lg N)인 이유를 수학적으로 설명해보면...
N개의 수를 병합정렬을 이용하여 정렬할 때의 시간복잡도를 Merge(N)이라고 가정합니다. 병합정렬은 N개의 수를 절반으로 쪼갠 후 각각을 정렬한 다음 합치는 과정을 거치게 되지요. 따라서
Merge(N) = Merge(N/2) + Merge(N/2) + O(정렬된 두 리스트를 합치는데 걸리는 시간) 입니다.
정렬된 두 리스트를 합치는 데 걸리는 시간은 O(N)입니다. 앞에서부터 차례대로 보면서 작은 것을 선택해 나가면, 각각의 인덱스를 한번씩만 방문하면 되니까요.
Merge(N) = 2 * Merge(N/2) + O(N)이 되고, 책에서 자주 확인하실 수 있는것처럼 N의 사이즈를 절반으로 줄이는 과정을 lg N번 반복하면 해결 가능하므로, O(N lg N)이 됩니다.분할 정복이 특정 문제에서 더 빠르게 연산할 수 있는 이유는, 작은 문제들을 해결한 후, 합치는 과정의 코스트가 작기 때문입니다. 위에서 예로 설명한 병합정렬에서 "정렬된 두 리스트를 합치는데 걸리는 시간"이 O(N)에 해결되지 못했다면, 병합정렬 또한 O(N lg N)이라는 시간복잡도를 가질 수 없었을 거에요.
8년 전 link
-
-
-
chongkong -
저도 간단히 생각을 남기고 가 봅니다.
1.
일단 분할정복을 쓰는 경우는 대체로 O(N^2) 알고리즘을 O(NlgN)으로 줄이고자 할 때 사용하죠. 이유는 시간 복잡도가
T(N) = 2T(N/2) + O(N)으로 주어질 때 T(N)의 점근적 시간복잡도가 O(NlgN)이 되기 때문이죠.
2.
시간복잡도가 O(N)보다 큰 이유는 본질적으로 하위 문제들이 독립적이지 못하기 때문입니다. (여기서 하위 문제라 함은 문제를 단순히 반으로 쪼갠 경우를 생각합니다.) 만약에 하위 문제들이 "완전히 독립적"이라면 그 문제의 시간복잡도는 O(N)이 되겠죠. 왜냐하면 T(N/2) + T(N/2) = T(N)이 되어야 하니까요.하지만 대부분의 문제들은 하위 문제들이 독립적이지 못합니다. 예를 들면 정렬의 경우에는 각 원소들을 서로 비교해 보아야 하는데 이 경우 비교해야 할 대상이 많아질 경우 비교 가능한 경우의 수는 그 제곱에 비례해서 증가하게 되죠.
만약 어떤 정렬 알고리즘이 O(N^2)이라면 그 정렬 알고리즘은 하위 문제들을 "완전히 종속적"인 문제로 여긴다고 생각할 수 있습니다. 왜냐하면 모든 수들을 서로 비교해보고 있잖아요?
3.
하지만 몇몇 문제들은 하위 문제들이 완전히 종속적이지 않은 경우가 있습니다. 예를 들어 a, b, c라는 원소를 정렬하기 위해 비교를 하는데 a<b이고 b<c이면 a와 c는 굳이 비교해 보지 않아도 a<c임을 알 수 있잖아요?이러한 미묘한 독립성이 결국 탐색 공간을 줄이고 시간 복잡도를 줄이게 됩니다.
4.
그러한 미묘한 독립성은 결국 시간복잡도 식을 통해서 나타나게 됩니다. T(N) = 2T(N/2) + K 이라는 식에서 K이라는 아이가 결국 하위 문제들간의 독립성의 척도가 되겠지요. T(N) = 2T(N/2) + O(1)이라면 하위 문제가 완전 독립적이기 때문에 T(N) = O(N)이 되는 것이고 T(N) = 2T(N/2) + O(N)이라면 하위 문제들이 O(N)만큼 종속적이기 떄문에 T(N) = O(NlgN)이 되고요.
8년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Jaekwan
안녕하세요. 느지막하게 알고리즘에 대해서 다시 공부를 하고있는 개발자 입니다.
공부를 새로하는 초점은 "패러다임을 어떻게 하면 잘 이용할까"인데, 그러다 보니 분할정복에서 멈춰버렸군요..
제가 막힌 곳의 문제 자체를 좀 더 자세하게 설명하자면,
"무엇이 그리고 왜분할 정복을 brute force보다 빠르게 만드는가?"입니다.
가령, 정렬이 포함된 알고리즘 혹은 프로그램의 경우 정렬을 하는 이유는 순서화되지 않은 데이터에서 순서화를 시킴으로써 프로그램의 진행 분기의 가능성을 최소화 시킬 수 있다. 라고 생각합니다.
그래프 상에서 최단거리를 구하는 것도 결국 다른 노드로 움직이는 경우의 수를 최소로 줄임으로써(결국 다른 노드로 움직이는 경우를 분기라고 볼 경우) 성능을 올리는 것이고 보고요.
물론, 위와같이 생각하는 것에 한계가 있을 수도 있지만 이해하기 편리한 점과 줄여야 하는 목적지가 분명하기 때문에 적용하기 쉽다고 생각합니다.
그런데, 분할 정복의 경우는 생각보다 이 부분을 생각하기가 쉽지가 않네요. 물론 수학으로 증명을 하면 더 빠르게 작동한다는 것을 알 수 있지만, 프로그램 디자인 부분이라던지, 실생활 문제를 적용하는데 있어서는 쉽지 않네요.
분할 정복이 알고리즘을 빠르게 만드는 요인 혹은 이유가 무엇인자 조언을 듣고 싶습니다. =) 좀 더 문제를 줄여보자면, 정렬의 경우 병합정렬(nlogn)이 brute force(n^2) 빠르게 될 수 있는 이유(트리 형태의 진핸과정이 전체 연산을 줄 일 수 있는 이유)가 무엇일까요?
PS. 질문이 너무 애매모호 할지 몰라 걱정이네요.
8년 전