알고리즘 개발 방법론 두번째 장으로 욕심쟁이 기법(탐욕, Greedy Method)와 백트래킹(Backtracking)에 대해서 알아봅니다.
사실 이 두가지 기법은 모든 방법을 동원해서도 풀리지 않는 문제가 있을 때, 마지막으로 시도해볼 수 있는 방법입니다. 혹은 문제의 최적화된 해법을 구하기 전에 미리 그 해답을 찾는 방법이기도 합니다.
그런 의미에서 매우 중요하고 알아두어야 할 기법입니다. 그런데 그 내용을 들여다 보면 우리가 흔히 하는 작업들에 대해 체계적으로 정리해 놓은 것에 불과하다는 생각이 듭니다.
욕심쟁이 기법의 경우, 깊이 생각하지 않고 눈 앞에 놓여져 있는 데이터들을 직관적으로 생각할 수 있는 규칙으로 해결하는 방법입니다. 예를 들어 복잡한 서울에서 부산으로 가는 도로망이 있는데, 갈림길이 나온다면 서울에서 부산가는 방향의 방위각만 생각해서 그 방위각과 가까운 길을 택하는 식입니다. 결과적으로 더 빠른 경로가 있을 수 있지만, 대체적으로 비슷한 해답을 내어 줍니다.
백트래킹의 경우는 이도 저도 방법이 없으면 모두 다 해보는 겁니다. 학교에서 시험칠 때 객관식 문제가 나오면 보기를 문제에 대입해서 풀어보았던 경험이 있을 겁니다. 보기가 4개이면 일도 아니지요. 그런데 현실은 주관식 문제와 같기 때문에 보기 집합이 매우 크다는 문제가 있습니다. 하지만 컴퓨터는 단순 연산이 주특기라는 점을 잊지 마세요. 가능한 보기 집합을 산정한 후 모두 대입해 보아서 최적의 해를 찾는 것이 바로 백트래킹입니다. 그래서 이를 전수조사(Exhaustive Search)라고도 합니다. 물론 무한대의 보기를 가지고 대입할 수는 없기 때문에 가능한 보기 집합을 작게 만드는 것이 기법입니다. 그리고 계산을 진행하는 중에 아니다 싶으면 중간에 그만두는 로직도 필요합니다.
그래서 백트래킹은 어떻게 하면 빠뜨리지 않고 모든 경우의 수를 다 점검해 보느냐가 첫번째 이슈이고, 두번째 이슈는 어떻게 하면 빠뜨리지 않고 보기 집합을 줄이고 계산을 생략하여 효율을 꾀하느냐입니다.
강의 자료
강의 동영상
29.0 알고리즘 개발 방법론 2 - 시작 : 알고리즘 개발 방법론 중에서 욕심쟁이 기법과 백트래킹에 대해 살펴 봅니다. 각각의 개념과 특징 그리고 이를 활용하여 해결할 수 있는 문제를 들어 보고, 그를 소스 코드로 구현해 봅니다.
29.1 욕심쟁이 기법 (Greedy Method) : 욕심쟁이 기법은 직관적인 문제 해결 방법입니다. 그런데 인간의 직관이 항상 맞지는 않습니다. 하지만 대부분의 경우 적절한 정도의 해답을 구할 수 있다는 점에서 여전히 유용합니다. 어떤 문제를 풀 때 욕심쟁이 기법이 최적의 해를 구하는 방법인지는 엄밀하게 증명을 해야 합니다. 만일 욕심쟁이 기법이 최적해를 만드는 것으로 판명된다면 매우 쉬운 문제가 됩니다.
29.2 Fractional Knapsack 문제 : 앞서 배운 Knapsack 문제를 변형한 실수 Knapsack 문제를 풀어 봅니다. 직관적인 해법은 같은 중량일 때 가장 가치있는 것을 우선적으로 실으면 가장 큰 이득을 볼 수 있다는 겁니다. 그리고 이 해법은 최적해입니다.
29.3 백트래킹 (Backtracking) : 백트래킹은 가능한 모든 경우의 수를 테스트해 보는 기법입니다. 그래서 전수조사(Exhaustive Search)라고도 합니다. 그래서 백트래킹은 어떻게 빠짐없이 테스트를 해 보느냐, 그리고 어떻게 불필요한 계산을 줄이느냐가 관건입니다. 백트래킹은 워낙 계산량이 많은 방법이라 조그만 개선도 전체 성능에 큰 영향을 줍니다.
29.4 N-Queen 문제 : N-Queen 문제는 백트래킹의 대표적인 예제입니다. 유망한(Promising) 조건을 설정하고, 재귀 호출을 통해 이 문제를 풀어 봅니다.
29.5 0/1 Knapsack 문제 : 0/1 Knapsack 문제는 물건이 종류별로 하나씩만 있어서, 싣느냐 마느냐만 결정할 수 있는 Knapsack 문제입니다. 그런데 보기와는 달리 그 해를 구할 최적의 방법이 아직 발견되지 않은 어려운 문제입니다. 이 문제도 백트래킹을 이용하면 최적해를 구할 수 있습니다. 그리고 앞서 배운 욕심쟁이 기법이 합쳐지면 백트래킹의 효율을 높일 수 있습니다.
29.6 Bounded Traveling Salesman 문제 : 앞서 언급했던 외판원 순회 문제도 백트래킹이 어울리는 문제입니다. 어떻게 문제를 정의하고 해결할 수 있는지 알아 봅니다.
29.9 알고리즘 개발 방법론 2 - 결론 : 알고리즘 개발 방법론 중에서 욕심쟁이 기법과 백트래킹을 알아 보았습니다. 이 두 방법은 직관에 의존한다는 점과 모든 경우의 수를 따져 본다는 점에서 서로 대조적입니다. 부정확한 해를 낸다고 해도 그것이 합리적인 범위에 든다면 현실적으로 중요한 해법이 될 수 있음을 알아두시기 바랍니다.
관련글 |
- C++로 배우는 알고리즘
- 28장 : 알고리즘 개발 방법론 1 (Divide and Conquer, Dynamic Programming)
- 30장 : 오토마타(Automata)와 XML 파서
댓글 없음:
댓글 쓰기