TechBlog

분할정복 알고리즘 주어진 문제의 입력을 분할하여 문제를 히결하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 해를 취합하여 원래 문제의 해를 얻는다. 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분 문제는 더 이상 분할할 수 없을 때까지 계속 분할한다. 가짜동전찾기 1024개의 동전에서 하나의 가벼운 가짜 동전이 있을 때 하나를 기준으로 1023개를 비교해가며 가짜 동전을 찾을 수도 있고 2개씩 짝지어 n/2번회수로 가짜동전을 찾을 수도 있지만 분할정복기법을 적용하면 비교횟수를 줄일 수 있다. 512개씩 저울에 비교 가벼운 쪽을 다시 256개씩 비교, 가벼운쪽을 다시 128개씩, 64,32,16,8,4,2,1씩 비교해가..