[Algorithm] 3주차 스터디 - 재귀, 백트래킹

 

---

목차

1. 개념 정리

(1) 재귀

(2) 백트래킹

 

2. 3주 차 필수 문제 풀이

(1) A - 눈덩이 굴리기 (백준 21735번)

(2) B - 222-풀링 (백준 2164번)

(3) C - 하노이 탑 이동 순서 (백준 11729번)

(4) D - N과 M(7) (백준 15656번)

(5) E -  스도쿠(백준 2239번)

---

1. 개념 정리

(1) 재귀

 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다.  어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다. 이때 재귀 함수의 조건은 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하며(Base condition), 모든 입력은 base condition으로 수렴해야 한다.

[ 재귀의 특징 ]

- 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함

- 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음

- 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄

- 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음

- 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨

 

(2) 백트래킹

 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 백트래킹에서 시도할 필요가 없는 상황을 가지치기라고 부르는데 가지치기가 빈번하면 백트래킹의 시간복잡도를 가늠하기 어렵다. 따라서 백트래킹 문제일 경우 가장 시간이 오래 걸릴만한 케이스를 직접 돌려봐서 시간초과가 나는지 확인하면 된다. 로컬에서 돌릴 때는 Release모드로 실행해 보는 것이 좋다.

[ 백트래킹 연습문제 ]

- N과 M :  15649번: N과 M (1) (acmicpc.net)

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하기

- N-Queen : 9663번: N-Queen (acmicpc.net)

크기가 N × N인 체스판 위에서 퀸을 놓는 방법의 수를 구하기

- 부분수열의 합 : 1182번: 부분수열의 합 (acmicpc.net)

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기

 

 

---

 

 

2. 3 주차 필수 문제 풀이

해당 주차는 C++을 사용했습니다

(1)  A - 눈덩이 굴리기 (백준 21735번)

21735번: 눈덩이 굴리기 (acmicpc.net)

21735번: 눈덩이 굴리기

 

📢 풀이 : 백트래킹

✔️ i번째 눈덩이를 골랐을 때 대회시간과 고르기 직전의 size를 dfs함수의 인자로 설정함

✔️ i번째 위치에서 다음 위치는 i+1 또는 i+2이므로, max(i + 1, cnt + 1, size + i+1번째 눈덩이 크기, i + 2, cnt + 1, size + i+2번째 눈덩이 크기)가 i번째 위치에서 가장 큰 눈덩이 크기가 된다. 이로써 모든 경우의 수를 확인할 수 있다. 대회시간의 최댓값이 10이므로 O(2^10) 안에 해결할 수 있다.

#include <iostream>
using namespace std;
int n, m, a[101];

int func(int i, int cnt, int size) {
    if (cnt > m) return 0;
    if (cnt == m) return size;
    int ans = 0;
    ans = max(func(i + 1, cnt + 1, size + a[i + 1]), func(i + 2, cnt + 1, size / 2 + a[i + 2]));
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << func(0, 0, 1);
}

 

(2)  B - 222-풀링 (백준 17829번)

17829번: 222-풀링 (acmicpc.net)

17829번: 222-풀링

 

📢 풀이 : 재귀함수 - 분할 정복

✔️ n x n 행렬에 풀링 한 번 적용 -> (n / 2) x (n / 2) 행렬

✔️ n = 2^k 일 때, n x n 행렬을 1 x 1로 만들기 -> 풀링 k 번 반복

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX_SIZE 1025

using namespace std;

int N, re_N;
int falling[MAX_SIZE][MAX_SIZE];
queue<int> q;

bool compare(int a, int b) {
    if (a > b) return true;
    else return false;
}

void submatrix(int x, int y) {
    vector<int> v;
    for (int i = x; i < x + 2; i++) {
        for (int j = y; j < y + 2; j++) {
            v.push_back(falling[i][j]);
        }
    }
    sort(v.begin(), v.end(), compare);
    q.push(v.at(1));
    v.clear();
}

void fallingDown(int size, int x, int y) {
    int n = size / 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            submatrix(x + i * 2, y + j * 2);
        }
    }
    re_N = n;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> falling[i][j];
    re_N = N;

    while (1) {
        fallingDown(N,0,0);
        if (re_N == 1) break;
        for (int i = 0; i < N / 2; i++) {
            for (int j = 0; j < N / 2; j++) {
                int data = q.front();
                q.pop();
                falling[i][j] = data;
            }
        }
        N /= 2;
    }

    cout << q.front();
    return 0;
}

 

(3)  C - 하노이 탑 이동 순서 (백준 11729번)

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

 

📢 풀이 : 재귀함수

✔️ n-1개의 원판을 n(가장 큰 원판)이 원하는 목적지가 아닌 곳으로 옮기고, n번의 원판을 원하는 곳으로 옮긴 다음 다시 n-1개를 n번 원판이 있는 곳으로 옮긴다.  

✔️ 1<<num은 2^num과 같은 표현이다. 

#include <iostream>
using namespace std;

void hanoi(int n, int from, int to, int bypass)
{
    if (n == 1)
        cout << from << ' ' << to << '\n';
    else
    {
        hanoi(n - 1, from, bypass, to);
        cout << from << ' ' << to << '\n';
        hanoi(n - 1, bypass, to, from);
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1 << num) - 1 << "\n";
    hanoi(num, 1, 3, 2);
}

 

(4)  D - N과 M(7) (백준 15656번)

15656번: N과 M (7) (acmicpc.net)

15656번: N과 M (7)

 

📢 풀이 : 백트래킹

✔️ 입력받은 숫자들을 저장할 벡터 v와 선택된 숫자들을 저장할 벡터 ans를 사용한다.  

✔️ n_m 함수 : num과 m이 같으면 선택된 숫자들을 출력하고 함수를 종료하고 그렇지 않은 경우에는 재귀적으로 함수를 호출한다.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int n, m;
vector<int> v;
vector<int> ans;

void n_m(int num)
{
    if (num == m) {
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < v.size(); i++) {
        ans.push_back(v[i]);
        n_m(num + 1);
        ans.pop_back();
    }
}

int main()
{
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());
    n_m(0);
    return 0;
}

 

(5)  E - 스도쿠 (백준 2239번)

15656번: N과 M (7) (acmicpc.net)

15656번: N과 M (7)

 

📢 풀이 : 백트래킹

✔️ 숫자를 입력받는 동시에 bool형 배열 세 개를 채워준다.

✔️  빈칸이 비어있다면 1부터 9까지의 숫자를 넣어주고 앞선 bool형 배열 세 개의 값을 true로 바꿔준 후, 재귀함수를 돌린다. 여기서 숫자를 넣었는데 false인 경우에는 bool형 배열 세 개의 값을 다시 false로 바꿔주어야 한다. 

#include <iostream>
using namespace std;

int map[10][10];
bool row[10][10] = { false, };
bool col[10][10] = { false, };
bool square[10][10] = { false, };

void print() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++)
			cout << map[i][j];
		cout << '\n';
	}
}

void sudoku(int idx) {
	if (idx > 81) {
		print();
		exit(0);
	}
	int x = (idx - 1) / 9 + 1;
	int y = (idx - 1) % 9 + 1;
	int square_num = (x - 1) / 3 * 3 + (y - 1) / 3 + 1;
	if (map[x][y] == 0) {
		for (int i = 1; i <= 9; i++) {
			if (row[x][i] == false && col[y][i] == false && square[square_num][i] == false) {
				map[x][y] = i;
				row[x][i] = true;
				col[y][i] = true;
				square[square_num][i] = true;
				sudoku(idx + 1);
				map[x][y] = 0;
				row[x][i] = false;
				col[y][i] = false;
				square[square_num][i] = false;
			}
		}
	}
	else
		sudoku(idx + 1);
}

int main() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			scanf("%1d", &map[i][j]);
			row[i][map[i][j]] = true;
			col[j][map[i][j]] = true;
			square[((i - 1) / 3) * 3 + (j - 1) / 3 + 1][map[i][j]] = true;
		}
	}
	sudoku(1);
	return 0;
}

 

참고 자료 : 강좌 [실전 알고리즘] 0x0B ~ 0x0C강 BaaaaaaaarkingDog