개념
- 정답을 무조건 구하는 치트키
- 문제를 해결하기 위해 가능한 경우의 수를 모두 탐색
- 특히 backtracking, 재귀 함수를 활용해야 하는 문제
- 모든 코딩 테스트에서, 부분 점수라도 얻기 위해서 기본적으로 접근할 수 있어야 함
- 일반적으로 시간복잡도가 높은 편
종류 (문제 유형)
- N개 중에서
- 중복을 허용하면서
- 중복을 허용하지 않고
- M개를
- 순서에 따라 나열하라
- 골라라
N개 중에서 중복을 허용하면서 M개를 순서에 따라 나열하라
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected;
static void recursive(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int candidate = 1; candidate <= N; candidate++) {
selected[k] = candidate;
recursive(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) {
recursive(1);
System.out.println(sb.toString());
}
※ 지면을 아끼기 위해 import하는 부분이나, input 값들을 받아오는 로직은 생략했습니다. 😅
- 난이도 : 2
- 시간복잡도 : O(Nⁿ) = 7⁷ = 약 82만
- 공간복잡도 : O(M)
- if문은 M개를 전부 골랐을 때 결과값을 모아주는 연산
- else문은 M개가 아직 안 모였을 때 k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법 시도
N개 중에서 중복을 허용하지 않고 M개를 순서에 따라 나열하라
static void recursive(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int candidate = 1; candidate <= N; candidate++) {
if (used[candidate] == 1) continue;
selected[k] = candidate;
used[candidate] = 1;
recursive(k + 1);
selected[k] = 0;
used[candidate] = 0;
}
}
}
※ 뭔가 상당히 생략되었는데・・・ 😅
- 난이도 : 2
- 시간복잡도 : O(P) = O(N! / (N-M)!) = 8! / 0! = 40320
- 공간복잡도 : O(M)
- 이전 문제에서 used 라는 배열을 추가로 사용해서 어떤 숫자가 쓰였는지 여부를 기록
- 위 코드에서는 0이면 사용 가능, 1이면 사용중
N개 중에서 중복을 허용하면서 M개를 골라라
static void recursive(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(seleceted[i]).append(' ');
sb.append('\n');
} else {
int start = selected[k - 1];
if (start == 0) start = 1;
for (int candidate = start; candidate <= N; candidate++) {
selected[k] = candidate;
recursive(k + 1);
selected[k] = 0;
}
}
}
- 난이도 : 2
- 시간복잡도 : O(Nⁿ) = 8⁸ ≅ 약 1677만
- 공간복잡도 : O(M)
- start 라는 변수를 가능한 최소 숫자 값으로 참조
❖ 비내림차순이란?
: (2,3), (3,2) 둘 다 가능하지 않고 (2,3) 하나로만 가능
N개 중에서 중복을 허용하지 않고 M개를 골라라
static void recursive(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int candidate = selected[k - 1] + 1; candidate <= N; candidate++) {
selected[k] = candidate;
recursive(k + 1);
selected[k] = 0;
}
}
}
- 난이도 : 2
- 시간복잡도 : O(C) = O(N! / M!(N-M)!) = 8! / 4! * 4! = 70
- 공간복잡도 : O(M)
종류별 복잡도 정리
중복 여부 | 순서 여부 | 시간복잡도 | 공간복잡도 |
O | O | O(Nⁿ) | O(M) |
X | O | O(P) = O(N! / (N-M)!) | O(M) |
O | X | O(Nⁿ) 보다 작음 | O(M) |
X | X | O(C) = O(N! / M!(N-M)!) | O(M) |
응용 문제
static boolean attackable(int r1, int c1, int r2, int c2) {
if (c1 == c2) return true;
if (r1 - c1 == r2 - c2) return true;
if (r1 + c1 == r2 + c2) return true;
return false;
}
static void recursive(int row) {
if (row == N + 1) answer++;
else {
for (int c = 1; c <= N; c++) {
boolean possible = true;
for (int i = 1; i <= row - 1; i++) {
if (attackable(row, c, i, col[i])) {
possible = false;
break;
}
}
if (possible) {
col[row] = c;
recursive(row + 1);
col[row] = 0;
}
}
}
}
public static void main(String[] args) {
recursive(1);
System.out.println(answer);
}
- 난이도 : 2
- N개 중에서 중복을 허용하면서 순서대로 나열하는 문제 = O(Nⁿ)
- row + col 값이 서로 같으면 같은 우상향 대각선에 있다는 뜻
- row - col 값이 서로 같으면 같은 좌상향 대각선에 있다는 뜻
⭐️ backtracking의 핵심은 재귀 함수를 올바르게 정의하는 것!!!
'Algorithm > 유형별 풀이 template' 카테고리의 다른 글
Two Pointers (0) | 2022.07.14 |
---|---|
Binary Search (0) | 2022.07.12 |
Sort Application (0) | 2022.07.11 |