알고리즘에서 재귀 규칙을 발견하기 어려운 경우가 있다.
그럴 땐 크기가 작은 같은 문제를 발견할 수 있는지 살펴보자. 아래는 하노이 탑의 설명이다.
- A, B, C 세 기둥이 있고 A 기둥에 있는 원판들을 C 기둥으로 모두 옮기는 것이 목표이다.
- 단, 한 번에 한 개의 원판만을 옮길 수 있고, 큰 원판을 작은 원판 위에 놓을 수 없으며,
원판은 모두 세 기둥 중 하나에는 꽂혀있어야 한다.- 처음에는 A 기둥에 밑에서부터 가장 큰 원판이 순차적으로 가장 작은 원판까지 나란히 꽂혀있다.
"그렇다면 몇 번 만에 A 기둥의 원판들을 C 기둥으로 모두 옮길 수 있는가?" 라는 문제가
하노이 탑이다.
글만 보면 규칙을 찾기 어렵다. 따라서 n = 1 부터 몇 가지 경우를 살펴보자.
n = 1일 때는 A에서 C로 1번만에 옮길 수 있다.
n = 2일 때는 1번 원판을 A에서 B로,
2번 원판을 A에서 C로,
1번 원판을 B에서 C로 옮겨서
3번만에 옮길 수 있다.
n = 3일 때는 아래 사진과 같이 옮겨 7번만에 옮길 수 있다.
그럼 아래와 같은 규칙이 발견된다.
- n개의 원판 중 가장 큰 원판을 제외한 다른 원판을 B로 옮긴다. (n-1만큼 옮김)
- 가장 큰 원판을 C로 옮긴다.
- B의 원판 모두를 C로 옮긴다. (n-1만큼 옮김)
1, 3번에서 재귀 규칙이 발견된다. 이를 코드로 구현하면 아래와 같다.
public class Recursion {
static int count = 0;
static void hanoi(int N, int start, int mid, int end) {
if (N == 1) {
count++;
return;
}
hanoi(N-1, start, end, mid);
count++;
hanoi(N-1, mid, start, end);
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
hanoi(N, 1, 2, 3);
System.out.println("총 횟수 : " + count);
}
}그럼 총 횟수가 출력된다.
알고리즘에서 완전 검색으로 문제를 해결할 수 있다.
완전 검색의 유명한 사례로 Baby Gin이란 문제가 있다. 아래는 문제에 대한 설명이다.
3, 4, 5와 같이 연속된 세 수가 1 차이로 등차일 경우를 Run이라 한다.
7, 7, 7와 같이 같은 수가 세 번 연속된 수를 Triplet이라 한다.
여섯개의 숫자 모두가 Run 또는 Triplet일 때 Baby Gin이라고 한다.
이때, 여섯 개의 수가 Baby Gin임을 판별하는 알고리즘을 작성하시오.
해당 문제를 "입력 받은 숫자를 정렬하고, 앞뒤 3자리씩 보면 되겠다!!"라고 생각할 수 있다.
아래 사례를 살펴보자.
{6, 4, 4, 5, 4, 4} -> {4, 4, 4, 4, 5, 6} 으로 Baby Gin 사례를 잡는다.
{1, 2, 3, 1, 2, 3} -> {1, 1, 2, 2, 3, 3} 으로 Baby Gin 사례를 놓친다.
이처럼 그리디 알고리즘적인 사고는 해답을 놓칠 수 있으므로 유의해서 사용해야 한다.
이를 완전 검색으로 푸는 코드는 아래와 같다.
public class BabyGin {
static boolean result = false;
static int[] numberArr, chaseArr;
static boolean[] numberCheck;
static void permutation(int chase) {
if (chase == 6) {
if (((chaseArr[0] + 1 == chaseArr[1]) && (chaseArr[1] + 1 == chaseArr[2])) && ((chaseArr[3] + 1 == chaseArr[4]) && (chaseArr[4] + 1 == chaseArr[5]))) {
result = true;
}
if (((chaseArr[0] == chaseArr[1]) && (chaseArr[1] == chaseArr[2])) && ((chaseArr[3] + 1 == chaseArr[4]) && (chaseArr[4] + 1 == chaseArr[5]))) {
result = true;
}
if (((chaseArr[0] + 1 == chaseArr[1]) && (chaseArr[1] + 1 == chaseArr[2])) && ((chaseArr[3] == chaseArr[4]) && (chaseArr[4] == chaseArr[5]))) {
result = true;
}
if (((chaseArr[0] == chaseArr[1]) && (chaseArr[1] == chaseArr[2])) && ((chaseArr[3] == chaseArr[4]) && (chaseArr[4] == chaseArr[5]))) {
result = true;
}
return;
}
for (int i = 0; i < 6; i++) {
if (numberCheck[i] == true) {
continue;
}
numberCheck[i] = true;
int temp = chaseArr[chase];
chaseArr[chase] = numberArr[i];
permutation(chase + 1);
chaseArr[chase] = temp;
numberCheck[i] = false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String arr = br.readLine();
numberArr = new int[6];
chaseArr = new int[6];
numberCheck = new boolean[6];
for (int i = 0; i < 6; i++) {
numberArr[i] = arr.toCharArray()[i] - '0';
numberCheck[i] = false;
}
permutation(0);
System.out.println("결과 : " + result);
}
}그럼 해당 숫자가 Baby Gin인지 아닌지 나온다.
※ 문제를 풀 때 최초로 완전 검색을 생각해보고.. 시간이 안 터지면 그걸로 푸는 게 코테에서 가장 낫다.
팩토리얼은 n <= 10 일 때 시간적으로 안전하다.
알고리즘에서 순열을 활용할 수 있다.
Baby Gin은 순열을 활용한 문제이다.
순열은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것(순서가 있음)을 의미한다.
순열을 재귀로 구현하면 아래와 같다.
// Java는 참.. 객체의 깊은 복사가 힘드네.. 그래서 방문 체크 쓰는구나..
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Permutation {
static int TC;
static int N;
static int R;
static int[] arr, brr; // 크기가 고정되면 값이 바뀌더라도 static으로 쓸 수 있다.
static int[] v;
static void permutate(int chase) {
if (chase == R) {
for (int i = 0; i < R; i++) {
System.out.print(brr[i] + " ");
}
System.out.println();
return;
}
for (int i = 0; i < N; i++) { // check의 방문 체크
if (v[i] == 1) {
continue;
}
v[i] = 1;
int temp = brr[chase]; // 이 문제에선 생략해도 상관 x
brr[chase] = arr[i];
permutate(chase + 1);
v[i] = 0;
brr[chase] = temp; // 이 문제에선 생략해도 상관 x
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
TC = Integer.parseInt(br.readLine());
for (int i = 0; i < TC; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
arr = new int[N];
brr = new int[R];
v = new int[N]; // 확장성을 넓히기 위해 int로 쓴다. (실제로 풀 때는 boolean)
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[j] = Integer.parseInt(st.nextToken());
v[j] = 0;
}
permutate(0);
}
}
}입력값은 아래와 같다.
1
4 2
1 3 5 7
출력 결과는 아래와 같다.
1 3
1 5
1 7
3 1
3 5
3 7
5 1
5 3
5 7
7 1
7 3
7 5
