[알고리즘 중급] 재귀 - 1

💚 6603 로또

하나의 배열을 재귀적으로 사용하는 방법이다.

문제에서는 6개를 사전순으로 출력하라고 했다. 그런데 오름차순으로 배열이 정렬되어있기 때문에 아래와 같은 방식으로 재귀적으로 탐색하면 자동으로 사전순으로 출력하게 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> lotto;
void solve(vector<int> &a, int index, int cnt) {
    if(cnt == 6) {
        for(int num : lotto) {
            cout << num << ' ';
        }
        cout << '\n';
        return;
    }

    int n = a.size();
    if(n == index) return;
    // 배열이 오름차순으로 정렬되어 있었기에 사전순으로 출력
    lotto.push_back(a[index]);
    solve(a, index + 1, cnt + 1);
    lotto.pop_back();
    solve(a, index + 1, cnt);
}
int main() {
    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        vector<int> a(n);

        for(int i = 0;i < n;i++) {
            cin >> a[i];
        }
        solve(a, 0, 0);
        cout << '\n';
    }
}

💚 1182 부분수열의 합

크기가 크지 않으니 모든 수열을 만들어도 된다.

go(index, sum)

- index: 부분 수열에 포함할지 말지 결정해야 하는 인덱스

- sum: 현재까지 부분수열의 합

 

정답을 찾은 경우

- index == n && sum == s

 

불가능한 경우

- index == n && sum != s

 

다음 경우

- index번째 수를 부분수열에 추가: go(index + 1, sum + a[i])

- index번째 수를 부분수열에 추가하지 않음: go(index + 1, sum)

 

크기가 양수인 경우만 포함해야하기 때문에 크기가 0인 경우는 빼기 위해서 0이 도출되는 경우에는 -1을 해야 한다.

 

💚 14888 연산자 끼워넣기

이건 앞선 순열 문제로도 풀었는데, 재귀로도 푸는 게 가능하다.

go(a, index, cur, plus, minus, mul, div)

- a: 입력으로 주어진 순열

- index: 현재 계산해야 하는 인덱스(미묘한 정의가 중요)

- cur: index - 1번째까지 계산한 결과

- plus, ... div: 사용할 수 있는 연산자의 개수

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
// 최대, 최소 값 리턴
pair<int, int> calc(vector<int> &a, int index, int cur, int plus, int minus, int mul, int div) {
    int n = a.size();

    if(index == n) {
        return make_pair(cur, cur);
    }

    vector<pair<int, int>> res;

    if(plus > 0) {
        res.push_back(calc(a, index + 1, cur + a[index], plus - 1, minus, mul, div));
    }

    if(minus > 0) {
        res.push_back(calc(a, index + 1, cur - a[index], plus, minus - 1, mul, div));
    }

    if(mul > 0) {
        res.push_back(calc(a, index + 1, cur * a[index], plus, minus, mul - 1, div));
    }

    if(div > 0) {
        res.push_back(calc(a, index + 1, cur / a[index], plus, minus, mul, div - 1));
    }
    // 초기화
    auto ans = res[0];

    for(auto p : res) {
        // 최대값
        if(ans.first < p.first) {
            ans.first = p.first;
        }

        // 최소값
        if(ans.second > p.second) {
            ans.second = p.second;
        }
    }

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    int plus, minus, mul, div;
    cin >> plus >> minus >> mul >> div;
    // index = 현재 계산해야 하는 인덱스
    auto p = calc(a, 1, a[0], plus, minus, mul, div);
    cout << p.first << '\n';
    cout << p.second << '\n';
}

 

💚 14500 테트로미노

- 폴리오미노는 크기가 1 * 1인 정사각형을 여러 개 이어 붙여서 만든 도형

- 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 총 5가지가 있다.

- N * M 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸의 쓰여 있는 수의 합을 최대로 하는 문제

- 4 <= N, M <= 500

 

4가지의 테트로미노는 첫번째 블럭에서 3 연속으로 나아가서 만들 수 있지만, 나머지 하나는 불가능하다. 즉 예외 발생!

어떻게 처리할까? 별도로 수동체크 하자.

 

#include <iostream>
using namespace std;
int a[500][500];
bool c[500][500];

int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int ans = 0;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void go(int x, int y, int sum, int cnt) {
    if(cnt == 4) {
        if(ans < sum) ans = sum;
        return;
    }

    if(!inside(x, y)) {
        return;
    }

    // 이미 방문한 블럭이면 패스
    if(c[x][y]) return;

    // DFS와 다른 일반적인 브루트 포스의 특징 (체크했다가 탐색 후 해제)
    // 아닌 경우도 물론 존재한다.
    c[x][y] = true;
    
    for(int k = 0;k < 4;k++) {
        go(x + dx[k], y + dy[k], sum + a[x][y], cnt + 1);
    }

    c[x][y] = false;
}

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

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            go(i, j, 0, 0);
            if(j + 2 < m) {
                int temp = a[i][j] + a[i][j + 1] + a[i][j + 2];
                if(i - 1 >= 0) {
                    int temp2 = temp + a[i- 1][j + 1];
                    if(temp2 > ans) ans = temp2;
                }

                if(i + 1 < n) {
                    int temp2 = temp + a[i + 1][j + 1];
                    if(temp2 > ans) ans = temp2;
                }
            }

            if(i + 2 < n) {
                int temp = a[i][j] + a[i + 1][j] + a[i + 2][j];
                if(j + 1 < m) {
                    int temp2 = temp + a[i + 1][j + 1];
                    if(ans < temp2) ans = temp2;
                }

                if(j - 1 >= 0) {
                    int temp2 = temp + a[i + 1][j - 1];
                    if(ans < temp2) ans = temp2;
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

💚 16197 두 동전

- N * M 크기의 보드, 4개의 버튼이 있다.

- 칸은 비어있거나, 동전, 벽이다.

- 동전은 2개이다.

- 버튼은 왼쪽, 오른쪽, 위, 아래이고, 누르면 그 방향으로 이동한다.

- 이동하려는 칸이 벽이면 이동하지 않는다.

- 이동하려는 칸이 없으면 보드 바깥으로 떨어진다.

- 그 외에는 이동한다.

- 두 동전 중 하나만 보드에 떨어뜨리기 위해 버튼을 몇 번 눌러야 하는가?

- 10번보다 많이 눌러야 하면 -1을 출력한다.

 

총 4^10 가지의 방법을 수행한다.

 go(step, x1, y1, x2, y2)

- step: 버튼을 누른 횟수

- (x1, y1): 한 동전의 위치

- (x2, y2): 다른 동전의 위치

 

불가능한 경우

- step == 11

- 두 동전이 모두 떨어지는 경우

 

정답인 경우

- 두 동전 중 하나만 떨어지는 경우

 

다음 경우

- go(step + 1, nx1, ny1, nx2, ny2)

 

💚 16198 에너지 모으기

처음에 N개의 구슬이 존재하면 (N - 2) 개의 구슬을 고를 수 있고, 마지막에는 3개의 구슬이 남아서 가운데 구슬만 고를 수 있다.

그래서 경우의 수는 (N - 2)!이다.

#include <iostream>
#include <vector>

using namespace std;
int go(vector<int> &a) {
    int n = a.size();
    if(n == 2) return 0;
    int ans = 0;
    for(int i = 0;i < n -1;i++) {
        int energy = a[i - 1] * a[i + 1];
        vector<int> b(a);
        b.erase(b.begin() + i);
        energy += go(b);
        if(ans < energy) {
            ans = energy;
        }
    }

    return ans;
}

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

    cout << go(a) << '\n';
    return 0;
}

 

다음 강의는 백트래킹 관련 재귀 문제이다.