6장 알고리즘 설계 패러다임

알고리즘 설계 패러다임이란 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다.

무식하게 풀기

---

'무식하게 푼다'라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 "완전 탐색"이라고 한다.

재귀 호출과 완전 탐색

---

재귀 호출(=재귀 함수)이란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 말한다.

재귀 함수에는 '더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문(='거저 사례')을 포함해야 한다.

ex) if(n==1) return 1;

재귀 호출은 기존에 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공해 준다. 기존의 코드에 비해 재귀 호출을 통해 얻을 수 있는 별다른 이득은 없지만, 문제의 특성에 따라 재귀 호출은 코딩을 간편하게 해 줄 수 있는 강력한 무기가 된다.

재귀 호출을 이용하여 풀 수 있는 문제

1) 소풍 - 학생들을 두 명씩 짝 지어 주되, 친구인 학생들끼리만 짝을 지어줄 수 있는 방법의 갯수.

2) 게임판 덮기 - 격자 모양의 게임판에 ㄴ자 형식의 블록을 알맞게 삽입할 수 있는 경우의 개수.

최적화 문제(Optimization Problem)

---

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 합니다.

최적화 문제를 해결하는 방식 중 하나는 완전 탐색이다.

최적화 문제를 완전 탐색으로 풀 수 있는 문제 

1) 외판원 문제 - n개의 도시를 한 번씩 돌아서 돌아오는 데 걸리는 최소 거리.

2) 시계 맞추기 문제 -