무식하게 풀기
무식하게 푼다(brute-force) 라는 것은 일반적으로 가능한 모든 경우의수를 일일이 나열하며 답을 찾는 방법을 의미한다. 이러한 알고리즘을 흔히 "완전 탐색" 이라고 부르며, 이는 컴퓨터의 빠른 계산 능력을 가장 잘 활용하는 알고리즘이라고 할 수 있다.
다만, 일반적으로 문제의 크기가 커질수록 경우의 수가 기하급수적으로 늘어나므로 완전 탐색을 적용할 수 없게 된다. 따라서 이 알고리즘은 문제의 크기가 그리 크지 않은 경우에 유용하게 사용할 수 있다.
재귀함수와 완전 탐색
일반적으로 완전 탐색은 재귀함수를 통해 쉽게 구현할 수 있다.
동전 뒤집기
5개의 동전이 있을 때, 다음과 같이 모든 가능한 동전의 상태를 출력하는 문제를 생각해보자.
앞 앞 앞 앞 앞 앞 앞 앞 앞 뒤 앞 앞 앞 뒤 앞 ... 뒤 뒤 뒤 뒤 뒤
이를 다음과 같은 재귀 함수로 구현할 수 있다.
int coin[5]; // 0: 뒷면, 1: 앞면 void printCoin() { for (int i = 0; i < 5; i++) { printf("%s ", coin[i] ? "앞" : "뒤"); } printf("\n"); } // i번쨰 동전의 상태를 결정한다. void filpCoin(int i) { // 마지막 동전까지 결정했다면 출력하고 종료한다. if (i == 5) { printCoin(); return; } coin[i] = 1; // 앞면 filpCoin(i + 1); // 다음 동전으로 coin[i] = 0; // 뒷면 filpCoin(i + 1); // 다음 동전으로 }
답의 순서와 형태 제한하기
경우의 수를 세는 문제에서 완전 탐색을 적용할 때 흔히 발생하는 실수 중 하나는 같은 답을 중복하여 세는 경우이다. 이러한 문제를 방지하기 위해, 특정한 순서 또는 형태의 답만 세도록 강제할 수 있다.
게임판 덮기
예를 들어, 다음과 같은 게임판의 빈 칸을 ㄱ자 모양의 블록을 통해 모두 덮는 경우의 수를 세는 문제를 생각해보자.
이 문제에서 블록을 놓는 순서는 중요하지 않다. 즉, 블록을 놓는 순서가 다르더라도 같은 모양이라면 같은 경우로 세어야 한다.
같은 경우를 중복으로 세지 않기 위해, 다음과 같이 블록을 놓는 순서를 제한할 수 있다.
- 블록을 놓을 때 빈 칸 중 가장 위, 그 중에서도 가장 왼쪽에 있는 칸에 놓는다.
이렇게 하면 한 답을 한 가지 방법으로밖에 생설할 수 없으므로, 중복으로 답을 세는 문제를 해결할 수 있다.
짝 짓기
또 다른 예로, N명의 학생을 2명씩 짝지어 팀을 만드는 경우의 수를 세는 문제를 생각해보자.
이 문제에서 다음 두 경우는 하나로 세어야 한다.
- (철수, 영희), (민수, 상현)
- (상현, 민수), (철수, 영희)
이 문제에서도 답의 형태를 제한하기 위해 우선 학생들에게 번호를 매길 수 있다. 여기서는 다음과 같이 답의 형태를 제한할 수 있다.
- 새로운 짝을 만들 때, 아직 짝이 지어지지 않은 학생 중에서 번호가 가장 작은 학생을 선택한다.
이런식으로 답을 생성하면 결과가 항상 정렬된 형태로 생성되므로, 같은 답을 중복하여 세지 않게 된다.
격자판 불 켜기
또한, 답의 순서 또는 형태를 제한하는 기법은 중복을 방지하기 위함 뿐만 아니라 탐색해야 할 경우의 수를 획기적으로 줄이는 방법으로도 사용될 수 있다.
위와 같은 격자판에 몇 개의 칸에만 불이 켜져있다. 이때, 각 칸을 누르면 그 칸과 상하좌우에 있는 칸의 불이 켜지거나 꺼진다. (즉, 켜져있으면 꺼지고, 꺼져있으면 켜진다.) 이때, 모든 불을 켜기 위해 눌러야 하는 횟수를 최소하하는 문제를 생각해보자.
이 문제를 모든 경우의 수를 따져가며 풀려고 하면 개의 경우의 수가 나온다. 그러나, 칸을 누르는 순서가 중요하지 않다는 사실을 깨닫고 나면, 누르는 순서를 강제함으로써 경우의 수를 개까지 줄일 수 있다. 이것이 어떻게 가능한지는 스스로 생각해보면 도움이 될 것이다.
CLOCKSYNC: 시계 맞추기
https://algospot.com/judge/problem/read/CLOCKSYNC
답 제한하기
조금만 생각해보면 이 문제에서 다음과 같은 사실을 발견할 수 있다.
- 스위치를 누르는 순서는 중요하지 않다.
- 한 스위치를 4번 이상 누르는 것은 의미가 없다.
따라서, 다음과 같이 답의 형태를 제한할 수 있다.
- 0번 스위치부터 9번 스위치까지 순서대로 누른다.
- 한 스위치를 누르는 횟수는 0~3이다.
코드
char linked[10][16] = { "xxx.............", "...x...x.x.x....", "....x.....x...xx", "x...xxxx........", "......xxx.x.x...", "x.x...........xx", "...x..........xx", "....xx.x......xx", ".xxxxx..........", "...xxx...x...x.." }; int clocks[16]; // 시계가 모두 12시를 가리키고 있는지 확인한다. int areAligned() { for (int i = 0; i < 16; i++) { if (clocks[i] != 12) { return 0; } } return 1; } // swtch번 스위치를 누른다. void push(int swtch) { for (int clock = 0; clock < 16; clock++) { if (linked[swtch][clock] == 'x') { clocks[clock] += 3; if (clocks[clock] == 15) { clocks[clock] = 3; } } } } // 이번에 누를 스위치의 번호 swtch가 주어질 때, // 남은 스위치들을 눌러서 모든 시계를 12시로 맞출 수 있는 최소 횟수를 반환한다. int solve(int swtch) { // 모든 스위치를 눌러봤으면, 남은 시계들이 전부 12시를 가리키는지 확인한다. if (swtch == 10) return areAligned() ? 0 : INF; // swtch번 스위치를 0~3번 눌러본다. int ret = INF; for (int cnt = 0; cnt < 4; cnt++) { ret = min(ret, cnt + solve(swtch + 1)); push(swtch); } return ret; }