Divide And Conquer

크기가 크고 복잡한 문제를 해결하기 위한 방법으로 문제를 작은 단위로 나누어 해결하자는 것이 Divide and conquer이다. 나누어 해결한다는 원칙은 이 뿐만이 아니라 여러 문제를 동시에 해결하는 데도 유효한 원칙인 듯 하다.

여러 작업을 동시에 처리하기 위해 짧은 시간에 쉽게 처리할 수 있는 더 작은 단위의 작업으로 나누고 나누어진 작은 작업들을 우선순위를 정해 작업목록에 적당히 서로 끼워 넣어 하나씩 해결해 나가면 마치 여러가지 작업을 동시에 처리하는 것처럼 보인다. 비선점형(non-preemptive) 방식의 멀티테스킹 OS 처럼.

이 때 적당한 크기로 작업를 나누는 것이 중요하다. 너무 크게 나눠진 작업는 새로 추가된 더 작은 작업들에 의해 우선순위가 계속 밀리게 되고 나중에는 기한 내에 처리하기 어려워지는 상황이 되기 쉽다. 더 짧은 시간에 처리할 수 있는 작업이 선호되기 때문이다.

또, 동시에 진행해야 할 작업이 많을 수록 더 작은 크기로(더 짧은 시간에 처리할 수 있는 크기로) 나눠야 한다. 그래야만 여러 작업들이 동시에 진행되고 있는 것 처럼 보이게 될 것이다.

문제는 작게 나눠진 작업들을 오가며 처리할 때 생기는 문맥 변경(context change)에 따른 오버헤드이다. 작업을 더 잘게 나누게 되면 더 잦은 문맥 변경으로 이에 따르는 오버헤드 또한 증가하게 된다.

여러 작업을 동시에 처리하게 될 때 이런 오버해드를 고려해야 하는 것은 작업을 지시하는 사람이나 작업을 수행하는 사람이 염두해 두어야만 하는 것이다.

하지만 쉽게 잊게 된다. -_-;