분할정복 알고리즘

분할정복 알고리즘

• 주어진 문제의 입력을 분할하여 문제를 히결하는 방식의 알고리즘이다.
• 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 해를 취합하여 원래 문제의 해를 얻는다.
• 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분 문제는 더 이상 분할할 수 없을 때까지 계속 분할한다.

가짜동전찾기

• 1024개의 동전에서 하나의 가벼운 가짜 동전이 있을 때 하나를 기준으로 1023개를 비교해가며 가짜 동전을 찾을 수도 있고 2개씩 짝지어 n/2번회수로 가짜동전을 찾을 수도 있지만 분할정복기법을 적용하면 비교횟수를 줄일 수 있다.
• 512개씩 저울에 비교 가벼운 쪽을 다시 256개씩 비교, 가벼운쪽을 다시 128개씩, 64,32,16,8,4,2,1씩 비교해가며 가짜 동전을 찾을 수 있다.
• N개의 동전이 있을 때 N을 1이 될때 까지 몇번 나누어야 하는지는 최대 횟수 : $log_{2}{N}$