알고리즘문제해결전략 - 완전 탐색
완전 탐색
- 모든 경우의 수를 순회하는 방법
- 재귀 호출
더이상 쪼개지지 않는 기저 사례(base case)를 선정하고 반복적으로 같은 작업(코드)를 처리하는 것
완전 탐색 레시피
완전탐색의 대략적인 지침은 다음과 같다.
완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다. 만약 시간 안에 계산 할 수 없으면 다른 알고리즘을 써야 한다.
가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성 했으므로, 이것을 기저 사례로 선택해 처리한다.
이론적 배경: 재귀 호출과 부분 문제
제귀 호출을 공부하면서 짚고 넘어가야 할 중요한 개념 중 하나로 문제(problem)와 부분 문제(subproblem)에 대해서 알아야 한다.
이 정의는 동적 계획법이나 분할 정복과 같은 중요한 디자인 패러다임을 설명하는데 사용되는데, 쉽게 생각할 수 있는 직관과는 약간 차이가 있다. 다음의 두 정의를 보자.문제 : 주어진 자연수 수열을 정렬하라.
문제 : {16,7,9,1,3}을 정렬하라.
같은 문제라고 생각 할 수 있지만 두 정의 사이에는 큰 차이가 있다. 전자는 특정한 입력을 지정하지 않은 반면, 후자는 특정한 입력을 지정하기 때문이다. 재귀호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다. 예를 들어 {1,2,3}을 정렬하는 문제와 {3,2,1}을 정렬하는 문제는 서로 다른 문제이다. 따라서 앞의 두정의 중 엄밀하게는 후자만을 문제의 정의라고 할 수 있다.
[알고스팟] - 보글게임
보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.
예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.
보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.
해당 문제의 지문을 읽고 문제를 정의한다고 하면, '게임판에서의 현재 위치 (y,x) 그리고 단어 word가 주어질 때 해당 단어를 이칸에서부터 시작해서 찾을수 있는가?'로 정의된다. 그럼 우리는 해당 단어를 이 위치에서 찾을 수 있는지 알기 위해 최대 아홉 가지의 정보를 알아야 한다.
- 현재 위치(y,x)에 단어의 첫 글자가 있는가?
- 윗 칸(y-1, x)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
- 왼쪽 위 칸(y-1,x-1)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
- ...
- ...
이런 식으로 현재 위치, 상하좌우대각선 방향으로 검사를 해야 할 것이다. 이 중 2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과이다. 문제를 구성하는조각들 중 하나를 뺏기 때문에, 이 문제들은 원래 문제의 일부라고 할 수 있다. 이런 문제들을 원래 문제의 부분문제라고 한다.