재귀

문제에 존재하는 방법을 재귀함수를 통해서 해결한다.

문제 1 : 1,2,3 더하기

정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다. N이 최대 10까지 인데 N이 10일때 나올 수 있는 개수는 10개 즉, $3^{10}$가지가 나온다. 따라서 N이 주어지면 총 경우의 수는 $3^N$이다.

재귀함수를 만들어보면 go(count, sum, goal) 이러한 형태가 나온다. 숫자 count 개로 합 sum을 만들어 목표가 goal이 되도록 하는 것이다.
그러면 다음 상태는 어떻게 해야하는가? 다음 수 i가 온다고 하면 count에는 +1를하고 sum에는 +i를 하게 된다. 즉 go(count+1, sum+i, goal)를 호출하는 것이다. 다음 상태를 만들려면 문제의 조건을 위배하지 않아야하는데, 문제의 조건은 3가지 경우를 살펴봐야 한다.
1. 불가능한 경우
아무리 재귀함수를 호출해도 정답을 못 구하는 것 또는 문제의 조건을 위배한 경우이다. 문제에서는 sum > goal에 해당한다.
2. 정답을 찾은 경우
문제의 정답을 찾은 것이기 때문에 더이상 함수 호출을 할 필요가 없다. sum == goal에 해당
3. 다음 상태를 호출하는 경우
go(count+1, sum+i, goal)에 해당

하지만 코드를 짜면 count는 사용할 필요가 없기 때문에 이부분은 빼도 상관이 없다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while (t-- > 0) {
		int n = sc.nextInt();
		System.out.println(go(0, n));
	}
}

public static int go(int sum, int goal) {
	if (sum > goal) {
		return 0;
	}
	if (sum == goal) {
		return 1;
	}
	int now = 0;
	for (int i = 1; i <= 3; i++) {
		now += go(sum + i, goal);
	}
	return now;
}

문제 2 : 암호 만들기

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두개의 자음으로 구성되어 있다. 이 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있어야 하며, 암호로 사용할 수 있는 문자의 종류는 C가지 이다. 이때 가능성 있는 암호를 모두 구하는 문제이다.

제일 먼저 암호는 증가하는 순서로 배열되어 있어야 함으로 입력받은 알파벳 배열을 정렬를 해야 한다. 그 뒤에 재귀호출을 하면 된다.

재귀 함수는 go(n, alpha, password, i) 형태로 구성되는데, n은 만들어야 하는 암호의 길이 (= 문제의 L) alpha는 사용할 수 있는 알파벳 (= 정렬된 입력받은 알파벳 배열) password는 현재까지 만든 암호 i는 사용할지 말지 결정해야 하는 알파벳 인덱스를 의미한다.

재귀호출 조건을 살펴보자.
1. 정답을 찾는 경우
이때는 password의 길이 == n 일때를 의미한다.
2. 불가능한 경우
$i \geq alpha의 크기$ 일 때이다. 이 경우일 때 끝까지 다 찾아 다음 인덱스가 없는 경우를 의미한다.
3. 다음 경우
3.1 i번째를 사용할 때
go(n,alpha, password+alpha[i], i+1)
3.2 i번째를 사용하지 않을 때
go(n,alpha, password, i+1)

위 3가지 조건을 고려하여 코드를 구성하면 된다.

아래 코드를 보면 check() 함수가 있는데, 이는 가능한 암호를 다 만들고 정답일 때 모음 1개 자음 2개가 포함되어 있는지 판별하는 용도이다.
그리고 위의 2번조건을 1번 조건보다 먼저 사용하게 되면 안되는데 그 이유는 마지막까지 검색을 했을 때 정답이 나올 수 도 있기 때문이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
		String[] alpha = new String[m];
	for (int i = 0; i < m; i++) {
		alpha[i] = sc.next();
	}
	Arrays.sort(alpha);
	go(n, alpha, "", 0);
}

public static void go(int n, String[] alpha, String password, int i) {
	if (password.length() == n) {
		if (check(password)) {
			System.out.println(password);
		}
		return;
	}
	if (i >= alpha.length) {
		return;
	}
	go(n, alpha, password + alpha[i], i + 1);
	go(n, alpha, password, i + 1);
}

public static boolean check(String password) {
	int ja = 0;
	int mo = 0;
	for (char x : password.toCharArray()) {
		if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
			mo += 1;
		} else {
			ja += 1;
		}
	}
	return ja >= 2 && mo >= 1;
}

문제 3 : 퇴사

N+1일이 되는날 퇴사를 하려고 하는데 남은 N일 동안 최대한 많은 상담을 하려고 한다. 하루에 하나의 상담을 할 수 있고 i일에 상담을 하면 T[i]일이 걸리고 P[i]원을 번다.

특정 일에 상담을 할지 말지로 나눌 수 있어서 총 $2^N$가지의 경우가 나올 수 있다.

함수는 go(day, sum)형태로 구성할 수 있는데, day는 상담을 할지 말지 정하는 day 라고 할 수 있고 sum은 지금까지 얻은 수익을 의미한다.

조건을 생각해보자.
1. 정답을 찾는 경우는 day == n+1일 때 인데 문제에서 N+1일에 퇴사하는 것이기 때문에 이와 같이 조건을 줄 수 있다.
2. 불가능한 경우는 상담이 퇴사일보다 길어지는 경우 즉 day > n+1 인 경우이다.
3. 다음 경우 호출은 상담을 하는 경우와 하지 않는 경우로 나눌 수 있다.
상담을 하는 경우는 go(day+T[day], sum+P[day]) 이며 하지 않은 경우는 go(day+1, sum)이 된다.

public static int[] t;
public static int[] p;
public static int n;
public static int ans = 0;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	t = new int[n + 1];
	p = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		t[i] = sc.nextInt();
		p[i] = sc.nextInt();
	}
	go(1, 0);
	System.out.println(ans);
}

public static void go(int day, int sum) {
	if (day == n + 1) {
		if (ans < sum) {
			ans = sum;
		}
		return;
	}
	if (day > n + 1) {
		return;
	}
	go(day + 1, sum);
	go(day + t[day], sum + p[day]);
}

백트래킹

재귀함수를 이용해 브루트 포스를 하다보면 더이상 함수 호출이 의미 없는 경우가 있는데 이런 경우를 제외하고 브르투 포스를 진행하면 백트래킹이라고 한다.
재귀 함수는 모든 방법을 다 만들고 나서 정답이 아닌지 맞는지 결정하는 반면 백트래킹은 함수 호출이 진행되는 중에 이것이 아무리봐도 더이상 정답을 못 구하는 순간이 오면 중단하는 것이다.

문제 1 : 스타트와 링크

N명을 N/2명씩 두 팀으로 나누려고 한다. 두 팀의 능력치를 구한 다음, 차이를 최솟값을 구하는 문제이다. S[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때 팀에 더해지는 능력치이며 팀의 능력치는 팀에 속한 모든 쌍의 S[i][j]의 합이다.

한사람이 1팀에 속하거나 2팀에 속하는 경우 2가지가 나오기 때문에 N명이면 총 경우의 수는 $2^N$가지가 나온다.

함수는 go(index, first, second) 이렇게 정의할 수 있다. index는 index번째 사람을 어떤 팀에 넣을지 정하는 부분이고 first와 second는 1팀, 2팀을 의미한다.
정답을 찾은 경우는 index == n 일때를 의미하며 다음 경우 호출하는 것은 1팀 2팀 둘다 go(index+1,first,second)를 호출 하면 된다. 이때 함수를 호출 전에 first 또는 second에 index를 넣고 호출 후에는 다시 빼줘야한다.

지금가지 하는 방식이 모든 방법을 찾는 재귀 호출 방식이라면 백트래킹 방식은 조건 하나만 추가하면 된다. 문제에서 각 팀은 n/2으로 나눈다고 하였으니 불가능한 경우조건을 넣어주면 된다. 불가능한 경우는 first의 크기가 n/2보다 클 때와 second의 크기가 n/2보다 클 때이다.

public static int[][] s;
public static int n;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	s = new int[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			s[i][j] = sc.nextInt();
		}
	}
	ArrayList<Integer> first = new ArrayList<Integer>();
	ArrayList<Integer> second = new ArrayList<Integer>();
	System.out.println(go(0, first, second));
}

public static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
	if (index == n) {
		if (first.size() != n / 2) {
			return -1;
		}
		if (second.size() != n / 2) {
			return -1;
		}
		int t1 = 0;
		int t2 = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) {
					continue;
				}
				t1 += s[first.get(i)][first.get(j)];
				t2 += s[second.get(i)][second.get(j)];
			}
		}
		int diff = Math.abs(t1 - t2);
		return diff;
	}
	if (first.size() > n / 2) {
		return -1;
	}
	if (second.size() > n / 2) {
		return -1;
	}
	int ans = -1;
	first.add(index);
	int t1 = go(index + 1, first, second);
	if (ans == -1 || (t1 != -1 && ans > t1)) {
		ans = t1;
	}
	first.remove(first.size() - 1);
	second.add(index);
	int t2 = go(index + 1, first, second);
	if (ans == -1 || (t2 != -1 && ans > t2)) {
		ans = t2;
	}
	second.remove(second.size() - 1);
	return ans;
}

문제 2 : 링크와 스타트

문제 1번과 같은 문제이지만 조건이 최소한 1명이 팀에 속해있으면서 팀원 수가 같지 않아도 된다는 것이 추가되었다.

문제 1과 마찬가지로 정답을 찾은 경우(index == n) first와 second의 크기가 0이면 -1를 반환하고 각 배열의 크기만큼 for문을 돌려 팀의 능력치를 계산한다.

public static int[][] s;
public static int n;

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	s = new int[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			s[i][j] = sc.nextInt();
		}
	}
	ArrayList<Integer> first = new ArrayList<Integer>();
	ArrayList<Integer> second = new ArrayList<Integer>();
	System.out.println(go(0, first, second));
}

public static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
	if (index == n) {
		if (first.size() == 0) {
			return -1;
		}
		if (second.size() == 0) {
			return -1;
		}
		int t1 = 0;
		int t2 = 0;
		for (int i = 0; i < first.size(); i++) {
			for (int j = 0; j < first.size(); j++) {
				if (i == j) {
					continue;
				}
				t1 += s[first.get(i)][first.get(j)];
			}
		}
		for (int i = 0; i < second.size(); i++) {
			for (int j = 0; j < second.size(); j++) {
				if (i == j) {
					continue;
				}
				t2 += s[second.get(i)][second.get(j)];
			}
		}
		int diff = Math.abs(t1 - t2);
		return diff;
	}
	int ans = -1;
	first.add(index);
	int t1 = go(index + 1, first, second);
	if (ans == -1 || (t1 != -1 && ans > t1)) {
		ans = t1;
	}
	first.remove(first.size() - 1);
	second.add(index);
	int t2 = go(index + 1, first, second);
	if (ans == -1 || (t2 != -1 && ans > t2)) {
		ans = t2;
	}
	second.remove(second.size() - 1);
	return ans;
}

문제 3 : 부등호

부등호 기호 '<' 와 '>' 가 나열된 수열 A가 있다. 기호의 앞 뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 이때 선택된 수는 모두 달라야한다. k개의 부등호 관계를 모두 만족시키는 k+1개 자리의 정수 중에서 최대값과 최소값을 구하는 문제이다.

예를 들면 ㅁ > ㅁ < ㅁ < ㅁ 이런식으로 주어진다면 ('ㅁ'은 한자리 수가 들어갈 자리) 'ㅁ'
에는 0~9까지 올 수 있다. 하지만 문제에서 서로 다른 수를 사용하라 했으니 앞에서 사용한 수를 제외한 나머지 0~9에 있는 수를 써야 한다.

재귀 함수로 go(index, num)으로 구현할 수 있다. index번째에 수를 넣을 거고, num은 수를 다 합친 문자열를 의미한다.

이를 백트래킹 방식으로 바꾸면 시간이 많이된다. 이유는 앞의 방식은 부등호 기호를 만족하는지를 가장 마지막에 모든 수를 결정하고 검사하기 때문에 오래 걸리는 반면 백트래킹 방식은 수를 결정하고 부등호가 맞는지 체크를 하여 뒤에 함수가 호출될 것인지를 판단하기 때문이다.

아래 코드에서 정답인 경우(index == n+1)에는 ArrayList에 바로 넣어주면 되었고, good()함수를 만들어 이전 수와 부등호 관계를 파악한다. good 함수 첫번째 매개변수에는 앞에서 사용한 수이고 두번째는 사용하려는 수 세번째는 부등호이다.

public static int n;
public static char[] a = new char[20];
public static ArrayList<String> ans = new ArrayList<String>();
public static boolean[] check = new boolean[10];

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	for (int i = 0; i < n; i++) {
		a[i] = sc.next().toCharArray()[0];
	}
	go(0, "");
	Collections.sort(ans);
	int m = ans.size();
	System.out.println(ans.get(m - 1));
	System.out.println(ans.get(0));
}

public static void go(int index, String num) {
	if (index == n + 1) {
		ans.add(num);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (check[i]) {
			continue;
		}
		if (index == 0 || good(num.charAt(index - 1), (char) (i + '0'), a[index - 1])) {
			check[i] = true;
			go(index + 1, num + Integer.toString(i));
			check[i] = false;
		}
	}
}

public static boolean good(char x, char y, char op) {
	if (op == '<') {
		if (x > y) {
			return false;
		}
	}
	if (op == '>') {
		if (x < y) {
			return false;
		}
	}
	return true;
}

문제 4 : 맞춰봐

-10부터 10까지 N개의 정수(중복 없음)로 이루어진 수열 A가 있다. ($N \leq 10$) s[i][j]는 A[i] + A[i+1] + ... + A[j]가 0보다 크면 +, 작으면 -, 같으면 0이 들어간다. s가 주어졌을 때 가능한 A를 아무거나 하나 찾는 문제이다.

총 21개 수를 10개 자리에 넣어야 하기 때문에 총 경우의 수는 ${21}^{10}$이 나오는데 너무 많은 경우의 수이다. 이를 재귀 함수로 풀게 되면 무조건 시간 초과가 나온다.

그러면 어떻게 해야 하는가? s배열에는 i번째 부호가 들어 있는데 기존에는 -10부터 10까지 순회 했다면 지금은 s[i][i]를 보고 + 일때는 1부터 10까지 - 일때는 -10부터 -1까지 0이면 0을 넣는 방식으로 개선할 수 있다. 이때 나오는 경우의수는 $10^{10}$으로 많이 줄어 들었지만 여전히 오래 걸린다.

백트래킹 방식을 적용을 해보자. 문제 3번에서 푼 방식처럼 이전에 나온 것을 보면서 비교하는 것이다. index번째 수를 결정하면 0~index번째 수는 변하지 않는다. 따라서 모든 s[k][index] ($0 \leq k \leq index$) 를 함수 안에서 검사할 수 있다.

public static int n;
public static int[][] sign;
public static int[] ans;

public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	ans = new int[n];
	sign = new int[n][n];
	String s = sc.next();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			char x = s.charAt(cnt);
			if (x == '0') {
				sign[i][j] = 0;
			} else if (x == '+') {
				sign[i][j] = 1;
			} else {
				sign[i][j] = -1;
			}
			cnt += 1;
		}
	}
	go(0);
	for (int i = 0; i < n; i++) {
		System.out.print(ans[i] + " ");
	}
	System.out.println();
}

public static boolean check(int index) {
	int sum = 0;
	for (int i = index; i >= 0; i--) {
		sum += ans[i];
		if (sign[i][index] == 0) {
			if (sum != 0)
				return false;
		} else if (sign[i][index] < 0) {
			if (sum >= 0)
				return false;
		} else if (sign[i][index] > 0) {
			if (sum <= 0)
				return false;
		}
	}
	return true;
}

public static boolean go(int index) {
	if (index == n) {
		return true;
	}
	if (sign[index][index] == 0) {
		ans[index] = 0;
		return check(index) && go(index + 1);
	}
	for (int i = 1; i <= 10; i++) {
		ans[index] = sign[index][index] * i;
		if (check(index) && go(index + 1))
			return true;
	}
	return false;
}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.