[도서]"알고리즘 퍼즐"로 알고리즘 사고력 키우기(2)

완전 탐색의 가장 큰 단점은 느리다는 것이다. 대입해봐야 할 답의 개수는 문제의 크기에 대해 지수함수보다 빠르게 증가하므로 완전 탐색 전략은 사람뿐만 아니라 컴퓨터가 풀 때도 바람직한 방법은 아니다!

마방진 같은 예시를 보여주면서 완전탐색을 알려주는 것이 흥미로웠다.

 

 

다음은 역추적이다. 완전 탐색을 적용하는 데 크게 두 가지 문제가 있는데,

첫번째는 모든 가능한 풀이를 생성하는 과정이고 더 근본적인 두번째 문제점은 생성해서 처리해야 할 풀이의 수다.

역추적은 완전탐색의 주먹구구식 접근법에 비해 상당히 발전된 방식으로, 불필요한 후보는 생성하지 않으면서 적절한 풀이 후보를 생성하도록 해주는 편리한 방법이다.

기본 개념은 풀이를 한 번에 하나씩 구축하면서 부분적으로 구축된 후보를 식으로 평가하는 것이다.

이 책에서는 체스판을 예시로 역추적 알고리즘에 대해 설명해줘서 깔끔하게 이해가 됐다.

 

마지막으로 동적 프로그래밍은 부분 문제가 중복되는 문제를 풀기 위한 기법이다. 

중복되는 부분 문제를 계속 다시 푸는 대신 한 번만 풀고 그 결과를 표에 저장한 후 그 값으로부터 원래 문제에 대한 답을 구하는 방식이다.

어떤 최적화 문제를 이 기법으로 풀기 위해서는 최적화된 부분 구조가 있어야 하며 부분 문제에 대한 최적해로부터 전체 문제에 대한 최적해를 효율적으로 구성할 수 있어야 한다.

최단 경로 개수를 구하는 방법을 그림을 통해 보여줘서 이해에 도움이 되던 것 같다.