[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 6회차 과제 에디토리얼

6회차 - 재귀, 분할정복

 

---

</17478> 재귀함수가 뭔가요?

https://www.acmicpc.net/problem/17478

글이 많아 약간 귀찮을 수 있지만 재귀의 개념을 익히기 좋은 문제입니다.

#include <iostream>
using namespace std;

int n;

void f(int x) {
    if (x > n) {
        return;
    } else if (x == n) {
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "\"재귀함수가 뭔가요?\"\n";
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "라고 답변하였지.\n";
    } else {
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "\"재귀함수가 뭔가요?\"\n";
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
        f(x + 1);
        for (int i = 0; i < 4 * x; i++) cout << '_';
        cout << "라고 답변하였지.\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";

    f(0);
}

 

---

</15649> N과 M (1)

https://www.acmicpc.net/problem/15649

저는 백트래킹을 이용한 dfs 함수를 만들고 dfs 함수를 재귀적으로 호출하는 방식으로 구현했습니다.

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

int n, m;
vector<int> ans;  // 현재까지 선택된 숫자를 저장하는 배열
vector<bool> chk;  // 숫자 사용 여부를 체크하는 배열

void dfs(int idx) {
    // m개의 숫자를 모두 선택한 경우
    if (idx == m) {
        for (int x: ans) cout << x << ' ';
        cout << '\n';
        return;
    }

    // 1부터 n까지의 숫자를 탐색하며 선택
    for (int i = 1; i < n + 1; i++) {
        if (!chk[i]) {  // 아직 선택되지 않은 숫자라면
            chk[i] = true;  // 숫자 i를 선택했다고 표시
            ans[idx] = i;  // 현재 위치(idx)에 i 저장
            dfs(idx + 1);  // 다음 위치(idx+1)로 이동하여 재귀 호출
            chk[i] = false;  // 다시 이전으로 복구
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    ans = vector<int>(m);
    chk = vector<bool>(n + 1);

    dfs(0);
}

 

---

</2630> 색종이 만들기

https://www.acmicpc.net/problem/2630

2차원 행렬을 반복해서 4등분하는데, 한 영역이 모두 같은 색으로 이루어져 있으면 개수를 증가시켜 주고 다른 색이 있다면 다시 4등분하여 재귀 호출하면 됩니다.

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

vector<vector<int>> p;
int cnt0 = 0;  // 햐얀색 색종이의 개수
int cnt1 = 0;  // 파란색 색종이의 개수

void countp(int r, int c, int s) {
    bool chk = true;
    int tmp = p[r][c];

    for (int i = r; i < r + s; i++) {
        for (int j = c; j < c + s; j++) {
            if (p[i][j] != tmp) {
                chk = false;
                break;
            }
        }
        if (!chk) {
            break;
        }
    }

    // 같은 색으로 이루어졌다면 개수 증가
    if (chk) {
        if (tmp == 0) {
            cnt0++;
        }
        else {
            cnt1++;
        }
    }
    // 그렇지 않다면 4등분하여 재귀 호출
    else {
        int news = s / 2;
        countp(r, c, news);
        countp(r, c + news, news);
        countp(r + news, c, news);
        countp(r + news, c + news, news);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    p = vector<vector<int>>(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
        }
    }
    
    countp(0, 0, n);

    cout << cnt0 << '\n' << cnt1 << '\n';
}

 

---

</1629> 곱셈

https://www.acmicpc.net/problem/1629

단순의 A^B를 구한 뒤 C로 나눠주게 되면 long long 범위를 초과하여 오버플로우 발생할 것입니다. 
그렇다고 A에 A를 한 번 곱하고 C로 나눠주고 다시 A를 곱하고 C로 나눠주는 것을 반복하면 시간 초과가 나겠죠. O(B)의 시간 복잡도를 갖습니다. 
따라서 분할 정복을 활용한 거듭제곱을 사용하여야 합니다. 거듭제곱을 계산할 때 B를 절반으로 줄여가면서 O(logB)의 시간 복잡도로 해결하는 방법입니다. 그리고 오버플로우 방지를 위해 중간 중간 C로 나누면서 연산을 해야 합니다.

#include <iostream>
using namespace std;

long long divpow(long long a, long long b, long long c) {
    if (b == 1) return a % c;
    long long tmp = divpow(a, b / 2, c) % c;
    if (b % 2 == 0) return (tmp * tmp) % c;
    else return (((tmp * tmp) % c) * (a % c)) % c;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long a, b, c;
    cin >> a >> b >> c;

    cout << divpow(a, b, c) << '\n';
}

 

---

</24460> 특별상이라도 받고 싶어

https://www.acmicpc.net/problem/24460

구역 당 인원이 한명이 될 때까지 구역을 나눠주면 되는 간단한 문제입니다.

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

vector<vector<int>> a;

// i: 시작 행 인덱스, j: 시작 열 인덱스
// k: 한 변의 길이
int spc(int i, int j, int k) {
    // 하나라면 그 값 반환
    if (k == 1) return a[i][j];

    int nowk = k / 2;
    int candidate[4];

    // 4개의 구역에서 각각 후보 구하기
    candidate[0] = spc(i, j, nowk);  // 왼쪽 위
    candidate[1] = spc(i, j + nowk, nowk);  // 오른쪽 위
    candidate[2] = spc(i + nowk, j, nowk);  // 왼쪽 아래
    candidate[3] = spc(i + nowk, j + nowk, nowk);  // 오른쪽 아래

    // 후보 정렬
    sort(candidate, candidate + 4);

    // 두 번째로 작은 값 반환
    return candidate[1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    a = vector<vector<int>>(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    cout << spc(0, 0, n) << '\n';
}

 

---

</11729> 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

하노이 탑에서 원판 5개를 첫 번째 탑에서 세 번째 탑으로 이동시키려면 어떻게 해야할까요?

아마 수학 시간에 언젠가 한번쯤 배우신 적이 있으실텐데, 위의 4개의 원판을 두 번째 탑으로 이동시킨 뒤 마지막 제일 큰 판을 세 번째 탑으로 이동시킨 다음에 다시 4개의 원판을 두 번째 탑에서 세 번째 탑으로 이동시키면 되죠.

이 과정을 일반화시켜보겠습니다. s를 현재 원판이 있는 탑, e를 원판을 옮길 탑, ano를 중간에 거쳐갈 탑이라고 해보겠습니다. n개의 원판을 s에서 e로 이동시키려면 n-1개의 원판을 s에서 ano로 이동시키고, 1개의 원판을 s에서 e로 이동시키고, n-1개의 원판을 ano에서 e로 이동시키면 됩니다.

이 논리를 그대로 재귀 함수로 구현하면 끝나는 문제입니다.

 

다만, 전체 이동 횟수를 계산할 때 cmath 헤더에 있는 pow 함수를 쓰신다면 주의해야 합니다.

pow는 int를 파라미터로 줄 때 double을 반환합니다. double의 정밀도는 15~18자리입니다. 하지만 부동 소수점 숫자를 출력할 때 cout의 기본 정밀도는 6자리입니다. 그렇기 때문에 cout으로 double을 출력하는 경우, 6자리가 넘어가면 그 수들을 잘리고 지수 표기로 출력됩니다.

하지만 이 문제에서는 정확한 값 전체를 출력해야 합니다. 이 문제를 해결하기 위한 방법은 2가지가 있습니다.

 

1. pow 함수의 반환값을 int로 형변환해준다.

cout << (int) pow(2, n) - 1 << '\n';

2. cout의 정밀도를 더 크게 조정해준다.

cout.precision(10);
cout << pow(2, n) - 1 << '\n';

더 자세히 공부해보고 싶다면 부동 소수점의 정밀도에 대해서 찾아보세요!

 

저는 1번 방법을 사용했고 전체 코드는 아래와 같습니다.

#include <iostream>
#include <cmath>
using namespace std;

// n: 옮길 원판의 개수
// s: 현재 원판이 있는 탑, e: 원판을 옮길 탑
void recur(int n, int s, int e) {
    if (n == 0) return;
    // ano: s와 e를 제외한 나머지 탑 (거쳐갈 때 필요한 탑)
    int ano = 6 - s - e;

    recur(n - 1, s, ano);
    cout << s << ' ' << e << '\n';
    recur(n - 1, ano, e);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    // 옮긴 횟수: 2^n - 1
    cout << (int) pow(2, n) - 1 << '\n';

    // 수행 과정 출력 by 재귀
    // 원판 5개를 1번 탑에서 3번 탑으로 이동
    recur(n, 1, 3);
}

 

---

</9663> N-Queen

https://www.acmicpc.net/problem/9663

퀸은 같은 행, 같은 열, 그리고 대각선으로 공격할 수 있습니다. promising(idx) 함수에서 현재 배치가 유효한지 검사합니다.

만약 유효한 위치라면 dfs(idx + 1)을 호출하여 다음 행의 퀸을 배치하고, 그렇지 않으면 백트래킹을 수행합니다.

모든 행에 퀸을 배치한 경우 하나의 가능한 배치가 완성되므로 cnt 값을 증가시킵니다.

이렇게 모든 가능한 경우를 탐색한 후 최종적으로 가능한 배치의 개수를 출력합니다.

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

int n;  // 체스판 크기
vector<int> col;  // col[i]: i번째 행에서 퀸이 위치한 열 번호
int cnt = 0;  // 가능한 퀸 배치 경우의 수

// 현재 퀸 배치가 유망한지 확인하는 함수
bool promising(int idx) {
    for (int k = 0; k < idx; k++) {
        // 같은 열(col[idx] == col[k]) 또는 대각선(|col[idx] - col[k]| == |idx - k|)
        if (col[idx] == col[k] || abs(col[idx] - col[k]) == (idx - k)) {
            return false;  // 충돌 발생 시 False 반환
        }
    }
    return true;
}

// 백트래킹을 이용해 퀸을 배치하는 함수
void dfs(int idx) {
    // 모든 퀸을 배치한 경우
    if (idx == n) {
        cnt++;
    } else {
        // 현재 행(idx)에 퀸을 놓을 수 있는 모든 열을 탐색
        for (int j = 0; j < n; j++) {
            col[idx] = j;  // 퀸을 j번째 열에 배치
            if (promising(idx)) {
                dfs(idx + 1);
            }
            col[idx] = -1;  // 원상 복구
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    col = vector<int>(n, -1);

    dfs(0);

    cout << cnt << '\n';
}