240225: 시험대비 DP 집중 복습, Stack Queue DFS+BFS

2024-02-25

2차 공부 계획

• 2월 25일 - 문제풀이집 1 풀이 (RGB 거리 ~ 오르막 수) 8문제
• 2월 26일 - 문제풀이집 1 풀이 (오르막 수 ~ N과 M 시리즈) 10문제
• 2월 27일 - 문제풀이집 1 완성. (N과 M 시리즈 ~ 끝) 8문제
• 2월 28일 - SW 문제풀이집 2 되는대로 풀기.. 총 70문제 🤯
• 2월 29일 - SW 문제풀이집 2
• 3월 1일 - SW 문제풀이집 2
• 3월 2일 - SW 문제풀이집 2

오늘은, 지원대비 문제풀이집 1의 문제를 차근히 풀어보겠다.

RGB거리 (1149)

이 문제는 선형적으로 놓여있는 집을 칠하는 비용 정보가 주어졌을 때, 아래의 조건을 만족하는 최소 비용을 구하는 DP 문제다.

- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

DP는 정말 어렵고 이해가 안됐었는데. 이제 슬슬 감 잡을 것 같아서 기분이 좋다.
이 문제는 예전에 푼 뒤로 두번째로 푸는건데, 그때는 이해가 정말 안됐는데 지금은 이해가 완벽하게 돼서 기분이 좋다!

다이나믹 프로그래밍 문제는 대체적으로 어렵다.

문제 해결은 간단했다. 현재 칠하는 집이 i-1의 집과 색이 겹치면 안된다. i-1의 집과 색이 겹치는지 안 겹치는지 상태를 추적하려면 dp 배열을 2차원 배열로 현재 칠하는 집의 지붕 색 정보를 포함하도록 메모이제이션을 해야한다.

따라서, dp[i][c] 를 i번째 집을 색 c로 칠했을때까지의 최소 비용으로 정의하고. 기본 사례를 식별했다.

    // RGB
    // 0 현재 집을 R로 색칠
    // 1 현재 집을 G로 색칠
    // 2 현재 집을 B로 색칠
    dp[1][0] = prices[1][0];
    dp[1][1] = prices[1][1];
    dp[1][2] = prices[1][2];

dp 2부터 반복을 돌리면서, 이번 집과 겹치지 않는 색 중에 더 적은 금액의 색을 선택하도록 구성했다.
큰 문제를 작은 하위 문제로 나누고, 작은 하위 문제의 해결을 통해 전체 문제의 해결책을 도출하는 DP 방식이다.

// 백준: RGB거리
// https://www.acmicpc.net/problem/1149
// 2024-02-24
// 소마 대비

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> dp(N + 1, vector<int>(3));
    vector<vector<int>> prices(N + 1, vector<int>(3));
    for (int i = 1; i <= N; ++i) {
        cin >> prices[i][0] >> prices[i][1] >> prices[i][2];
    }
    /*
    1번 집의 색은 2번 집의 색과 같지 않아야 한다.
    N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
    i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
    */

    // RGB
    // 0 현재 집을 R로 색칠
    // 1 현재 집을 G로 색칠
    // 2 현재 집을 B로 색칠

    dp[1][0] = prices[1][0];
    dp[1][1] = prices[1][1];
    dp[1][2] = prices[1][2];

    for (int i = 2; i <= N; ++i) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + prices[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + prices[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + prices[i][2];
    }

    cout << min({dp[N][0], dp[N][1], dp[N][2]});

    return 0;
}

아래는, 앞으로 DP 문제 풀이에 도움이 될 것 같아 남겨놓는 글!

동적 프로그래밍(Dynamic Programming, DP)

1. 문제 이해하기

• 문제를 완전하게 이해한다: 문제의 조건과 요구사항, 주어진 예시를 통해 어떻게 문제가 해결되어야 하는지 분석하고 관계 파악하기.

2. 작은 문제로 나누기

• 문제를 작은 문제로 나눈다: DP는 큰 문제를 작은 하위 문제로 나누고, 하위 문제의 해결을 통해 전체 문제의 해결책을 도출하는 방법이다. 각 하위 문제가 어떻게 전체 문제에 기여하는지 고려해 본다.

3. 점화식 찾기

• 기본 사례 식별하기: 모든 DP 문제는 하나 이상의 기본 사례(base case)를 가지고 있다. 기본 사례는 직접적으로 해결할 수 있는 가장 작은 문제다.
• 점화식을 도출하기: 점화식(recurrence relation)은 현재 문제의 해를 이전에 해결한 문제들의 해를 통해 어떻게 구할 수 있는지 나타낸다. 각 단계에서 가능한 선택을 고려하고, 각 선택이 결과에 어떠한 영향을 미치는 지 분석한다.

4. 예제로 시뮬레이션하기

• 작은 문제로 시뮬레이션하기: 문제를 해결하는 절차를 몇 가지 작은 예제에 적용해본다. 이를 통해 점화식의 올바름을 검증할 수 있다.

매우 중요한 팁

DP 문제에서 기본 사례를 설정할 때, 앞에 IF문을 써서 엣지 케이스 처리를 습관화하자.

    if(N>=1) dp[0][0] = pascal[0][0];
    if(N>=2) dp[1][0] = pascal[0][0] + pascal[1][0];
    if(N>=2) dp[1][1] = pascal[0][0] + pascal[1][1];

---

정수 삼각형 (1932)

정수 삼각형 문제는 파스칼의 삼각형 구조에서 가장 값을 크게 만드는 경로의 최댓값을 구하는 DP 문제다.
꽤 감 잡았다. 이제 실버 DP문제는 금방금방 풀린다.

문제 이해도 간단했고, 작은 문제로 나누는 것도 쉬웠다.
현재 층에서 이전 층의 왼쪽 혹은 오른쪽중에 큰 값을 가져오면 되는 간단한 DP문제다.
dp[r][i]를 층 r에서, 인덱스 i의 최댓값으로 설정했다.

DP문제는 정말 감이 다인 것 같다. 느낌이 필요하다.

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

int main() {
    int N;
    cin >> N;
    vector<vector<int>> pascal(N, vector<int>(N)); // 층, 인덱스
    vector<vector<int>> dp(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> pascal[i][j];
        }
    }

    // BASE CASE
    if (N >= 1)
        dp[0][0] = pascal[0][0];
    if (N >= 2)
        dp[1][0] = pascal[0][0] + pascal[1][0];
    if (N >= 3)
        dp[1][1] = pascal[0][0] + pascal[1][1];

    for (int i = 2; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            // EDGE CASE
            if (j == 0)
                dp[i][j] = dp[i - 1][j] + pascal[i][j];
            if (j == i)
                dp[i][j] = dp[i - 1][j - 1] + pascal[i][j];

            else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + pascal[i][j];
            }
        }
    }

    int answer = 0;
    for (int i = 0; i < dp[N - 1].size(); ++i) {
        answer = max(answer, dp[N - 1][i]);
    }

    cout << answer;

    return 0;
}

---

DFS와 BFS

이 문제는 기초 DFS + BFS 시뮬 문제인데, 조금 학습적 의미도 가질겸

지적 유희

를 즐겼다.
DFS는 각 테스트케이스마다 랜덤으로 Recursive DFS와 Stack DFS를 번갈아가면서 사용하도록 구현했고. BFS는 Queue를 이용해서 구현했다.

Stack이나 Queue를 써서 구현할 때, Recursive처럼 분기 탐색 성공 직후 타고 들어가지 않기 때문에, 방문 체크의 시점에 조금 더 신경을 써야함을 느꼈다.
이번에 방문 체크를 .pop() 이후에 한다거나, 아니면 push() 쪽에 한다거나 여러가지 시도를 해봤는데.

1. push 이전에 중복 탐색을 방지하기 위한 방문 체크
2. pop 하고 검색 이전/이후 방문 체크

이렇게 두 곳에 대해 모두 방문체크 해야 중복 탐색을 막을 수 있었다. 특히 탐색 순서가 중요할 때 말이다..

1. TC를 입력받고, 작은 순 탐색을 위해 sort했다.

    int N, M, V;
    cin >> N >> M >> V;
    adj.assign(N + 1, vector<int>());

    for (int i = 0; i < M; ++i) {
        int to, from;
        cin >> to >> from;
        adj[to].push_back(from);
        adj[from].push_back(to);
    }

    for (int i = 1; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

2. Recursive DFS

// 재귀 DFS
    vector<bool> visited_dfs_recursive(N + 1, false);
    vector<int> route_dfs_recursive;
    recursiveDFS(V, visited_dfs_recursive, route_dfs_recursive);

void recursiveDFS(int current, vector<bool> &visited, vector<int> &route) {
    visited[current] = true;
    route.push_back(current);

    for (const auto &next : adj[current]) {
        if (!visited[next]) { // 방문 X
            recursiveDFS(next, visited, route);
        }
    }
}

3. Stack DFS

    // 스택 DFS - (정점이 작은 순서대로 방문할 수 없다. 인접 정점을 역순으로 탐색하면 가능하다. 재귀 DFS는 첫번째 탐색된 노드.
    // 즉 왼쪽 분기부터 타고 내려가지만 스택은 현재 분기에서 마지막으로 탐색된 노드. 즉 오른쪽 분기부터 타고 내려간다.)
    vector<bool> visited_dfs_stack(N + 1, false);
    vector<int> route_dfs_stack;
    stack<int> s;
    s.push(V);

    while (!s.empty()) {
        int cur_v = s.top();
        s.pop();

        if (!visited_dfs_stack[cur_v]) {
            visited_dfs_stack[cur_v] = true; // 방문 처리
            route_dfs_stack.push_back(cur_v);

            for (auto it = adj[cur_v].rbegin(); it != adj[cur_v].rend(); ++it) {
                if (!visited_dfs_stack[*it]) {
                    s.push(*it);
                }
            }
        }
    }

4. Queue BFS

   // 큐 BFS
    vector<bool> visited_bfs(N + 1, false);
    vector<int> route_bfs;
    queue<int> q;
    q.push(V);
    while (!q.empty()) {
        int cur_v = q.front();
        q.pop();

        if (!visited_bfs[cur_v]) { // 방문하지 않았다면
            visited_bfs[cur_v] = true;
            route_bfs.push_back(cur_v);

            for (const auto &next : adj[cur_v]) {
                if (!visited_bfs[next]) {
                    q.push(next);
                }
            }
        }
    }

5. Random TC: 번갈아가면서 사용

    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution dis(0.5);

    bool fun = dis(gen);

    if (fun) {
        for (auto &iter : route_dfs_recursive) {
            cout << iter << " ";
        }
    } else {
        for (auto &iter : route_dfs_stack) {
            cout << iter << " ";
        }
    }

    cout << "\n";
    for (auto &iter : route_bfs) {
        cout << iter << " ";
    }

데이터셋이 방대한 게 아니라면 웬만해선 Recursive DFS를 쓰자, Stack DFS는 스택오버플로우의 걱정이 없는 대신 신경써야 할 것이 더 많고, 구현이 복잡하다.

모든 상태가 자동으로 인자로 귀속되는 재귀 DFS를 애용하자 !!!

최종 코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <random>
#include <stack>
#include <vector>
using namespace std;

vector<vector<int>> adj;

void recursiveDFS(int current, vector<bool> &visited, vector<int> &route) {
    visited[current] = true;
    route.push_back(current);

    for (const auto &next : adj[current]) {
        if (!visited[next]) { // 방문 X
            recursiveDFS(next, visited, route);
        }
    }
}

int main() {
    int N, M, V;
    cin >> N >> M >> V;
    adj.assign(N + 1, vector<int>());

    for (int i = 0; i < M; ++i) {
        int to, from;
        cin >> to >> from;
        adj[to].push_back(from);
        adj[from].push_back(to);
    }

    for (int i = 1; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

    // 재귀 DFS
    vector<bool> visited_dfs_recursive(N + 1, false);
    vector<int> route_dfs_recursive;
    recursiveDFS(V, visited_dfs_recursive, route_dfs_recursive);

    // 스택 DFS - (정점이 작은 순서대로 방문할 수 없다. 인접 정점을 역순으로 탐색하면 가능하다. 재귀 DFS는 첫번째 탐색된 노드.
    // 즉 왼쪽 분기부터 타고 내려가지만 스택은 현재 분기에서 마지막으로 탐색된 노드. 즉 오른쪽 분기부터 타고 내려간다.)
    vector<bool> visited_dfs_stack(N + 1, false);
    vector<int> route_dfs_stack;
    stack<int> s;
    s.push(V);

    while (!s.empty()) {
        int cur_v = s.top();
        s.pop();

        if (!visited_dfs_stack[cur_v]) {
            visited_dfs_stack[cur_v] = true; // 방문 처리
            route_dfs_stack.push_back(cur_v);

            for (auto it = adj[cur_v].rbegin(); it != adj[cur_v].rend(); ++it) {
                if (!visited_dfs_stack[*it]) {
                    s.push(*it);
                }
            }
        }
    }

    // 큐 BFS
    vector<bool> visited_bfs(N + 1, false);
    vector<int> route_bfs;
    queue<int> q;
    q.push(V);
    while (!q.empty()) {
        int cur_v = q.front();
        q.pop();

        if (!visited_bfs[cur_v]) { // 방문하지 않았다면
            visited_bfs[cur_v] = true;
            route_bfs.push_back(cur_v);

            for (const auto &next : adj[cur_v]) {
                if (!visited_bfs[next]) {
                    q.push(next);
                }
            }
        }
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution dis(0.5);

    bool fun = dis(gen);

    if (fun) {
        for (auto &iter : route_dfs_recursive) {
            cout << iter << " ";
        }
    } else {
        for (auto &iter : route_dfs_stack) {
            cout << iter << " ";
        }
    }

    cout << "\n";
    for (auto &iter : route_bfs) {
        cout << iter << " ";
    }

    return 0;
}

---

단지번호붙이기 (2667)

단지 번호 붙이기 문제는 2차원 맵에 아파트가 있는 위치가 주어질 때, 인접한 아파트를 단지라고 하고.

1. 총 단지의 개수
2. 각 단지의 아파트 수

를 return하는 문제.

DFS / BFS 로 간단하게 풀 수 있는 문제였다

근데 첫 시도에 사소한 실수를 했다. while 문 조건 체크에 !q.empty()가 아니라 q.empty()를 사용했다. 정말 바보같은 실수다... 실전에서 이런 실수 하면 정말 간단한 것에 시간 소비를 많이 할 것 같다.

또, 방문 체크에서 외부 for 루프에 쓰이는 인덱스들을 사용했다. while 내부에서 q.front해서 얻은 current 값들을 써야하는데.. 바보 같았다. 이런 실수를 최대한 줄이도록 노력하겠다 :(

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int dc[4] = {1, -1, 0, 0};
int dr[4] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> map(N, vector<int>(N, 0));
    for (int r = 0; r < N; ++r) {
        string temp;
        cin >> temp;
        for (int c = 0; c < N; ++c) {
            map[r][c] = temp[c] - '0';
        }
    }

    int complex_num = 0;
    vector<int> house_nums;

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (map[r][c] == 1) {
                int count = 0;
                complex_num++;
                queue<pair<int, int>> q; // r, c
                q.push({r, c});

                while (!q.empty()) {
                    int current_r = q.front().first;
                    int current_c = q.front().second;
                    q.pop();

                    if (map[current_r][current_c] == 1) {
                        map[current_r][current_c] = 0; // 집을 없앰 (방문 표시)
                        count++;

                        for (int i = 0; i < 4; ++i) {
                            int next_r = current_r + dr[i];
                            int next_c = current_c + dc[i];

                            // VALID CHECK
                            if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < N) {
                                if (map[next_r][next_c] == 1) { // 집이 존재해야만
                                    q.push({next_r, next_c});
                                }
                            }
                        }
                    }
                }
                house_nums.push_back(count);
            }
        }
    }

    sort(house_nums.begin(), house_nums.end());
    cout << complex_num << "\n";
    for (const auto &house : house_nums) {
        cout << house << "\n";
    }

    return 0;
}

숨바꼭질 (1697)

최단 거리 문제에서의 DFS / BFS에 대해서:

• DFS는 가능한 모든 경로를 고려하고, 모든 루트에 대해 끝까지 탐색해야만 최단 거리를 도출해낼 수 있기 때문에, 최단 거리 문제에서 DFS는 대체적으로 비효율적이고. 불필요한 루트에 대해서도 탐색할 수 있다.
• BFS는 시작 지점에서부터 점차적으로 모든 가능한 위치를 고려하기 때문에, 처음 조건을 만족하는 시간이 곧 최단거리가 된다. 따라서, 불필요한 루트에 대해 깊게 탐색하지 않기 때문에 최단 거리 문제에서 대체적으로 효율적이다

숨바꼭질 문제는 수빈이의 좌표와 동생의 좌표가 1차원적으로 주어졌을 때, 가능한 이동 방법: 걷기, 순간이동을 택해 가장 빠르게 동생에게 도달할 수 있는 시간을 찾는 문제다.

BFS를 풀 수 있는 매우 간단한 문제지만, 최단 거리 문제에서 어떤 그래프 순회 형태를 사용해야 하는지 깨달을 수 있는 문제다.

아, 그리고 시간을 queue와 같이 추적하는 스킬도 배울 수 있다.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<bool> visited(100001, false);

    queue<pair<int, int>> q;
    q.push({N, 0});
    while (!q.empty()) {
        int cur_pos = q.front().first;
        int cur_time = q.front().second;
        q.pop();

        if (cur_pos == K) {
            cout << cur_time;
            break;
        }

        if (!visited[cur_pos]) {
            visited[cur_pos] = true;
            if (cur_pos - 1 >= 0 && !visited[cur_pos - 1])
                q.push({cur_pos - 1, cur_time + 1});
            if (cur_pos + 1 <= 100000 && !visited[cur_pos + 1])
                q.push({cur_pos + 1, cur_time + 1});
            if (cur_pos * 2 <= 100000 && !visited[cur_pos * 2])
                q.push({cur_pos * 2, cur_time + 1});
        }
    }

    return 0;
}

01타일 (1904)

• 코드는 쉽지만, 도출 과정이 흥미로운 교육적인 문제.

01 타일은 0이 써있는 타일과 1이 써있는 타일을 무제한으로 사용해서 길이 N의 이진수를 만들 수 있는 가짓수를 얻는 문제다. 단, 누군가가 장난으로 0타일을 두개씩 붙여놔서 00타일만 쓸 수 있게 되었다.

도출 과정:

1. DP[\i] = c를 N이 i일때의 총 가짓수 c로 정의했다.
2. 기본 사례들을 살펴보면, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5... 순이다
3. 현재 길이 i에서 가능한 가짓수는 이전 i-1의 DISTINCT(이진수의 앞 혹은 뒤에 1을 붙이는 경우의 수 + 이전 i-2의 이진수의 앞 혹은 뒤에 00을 붙이는 경우의 수) 라고 생각했다.
4. 이후, 조금 더 점화식을 확실히 했다. dp[i-2]의 뒤에 00을 붙이는 수 + dp[i-1]의 뒤에 1을 붙이는 수 = dp[i]의 가짓수 였다.
5. 그렇다면 dp[5] = 8이다.
6. 1, 2, 3, 5, 8 | dp[i] = dp[i-2] + dp[i-1] 피보나치 수열의 점화식과 동일하다.

#include <iostream>
#include <vector>
#define MOD 15746
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> dp(N + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= N; ++i) {
        dp[i] = ((dp[i - 1] % MOD) + (dp[i - 2] % MOD)) % MOD;
    }
    cout << dp[N];
    return 0;
}

정말 흥미로운 문제다. DP를 작은 문제로 나눌때에는, 맨 뒤에서부터 생각하는것이 도움이 될 수도 있겠다.
만약 마지막 한자리만 남았다면 1만 올 수 있기 때문에, i-1에 1을 추가할 수 있는 수가 올 수 있다는 것이 성립하고. 만약 마지막 두자리만 남았다면 00과 1이 올 수 있지만, 1이 오는 경우는 이미 i-1에서 추가했기 때문에 뒤에 00이 오는 경우의 수만 추가된다.

따라서 해당 식은 길이가 k라고 할 때 k-2에서 00를 더한 경우 + k-1에서 1을 더한 경우의 합으로 볼 수 있기 때문에 피보나치의 수열과 동일하다.

흥미롭다.

---

동전 1(2293)

• 어려운 DP 문제였다.

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

너무 고정적인 DP 사고 방식에 갇혔던 것 같다. 이전의 해와 현재의 해과 어떤 연관을 가지는 지 알아내는데에 집중했는데. 계속해서 알아낼 수 없었다. 맞는 가정을 한 것 같은데 작은 값으로 검증이 안됐다.

기본 사례 식별에 오류가 있었다.
dp[0]에 대해서도 고려해야 했는데, 1에 대해서만 기본 사례를 고려하고 있었다. 동전이 (1, 2, 5) 일때 dp[1]은 1이겠지만 이건 기본 사례가 아니었다.

왜냐하면 동전의 가치는 TC 마다 유동적이니까 ..

올바른 기본 사례 설정은 dp[i] = c 를 i원을 만들 수 있는 경우의 수라고 할 때, dp[0] = 1 이었다.
왜냐하면 0원을 만드는 방법은 아무것도 선택하지 않는 한가지 방법이 있기 때문이다.

그러면 그 뒤로, 주어진 동전들을 하나씩 차례로 순회하면서 검사할 수 있다. 이전의 해에 현재 동전을 추가해서 현재 해를 만족시킬 수 있는 방법을 말이다.

예를 들어서. 5원에 대해 먼저 검사한다고 하면 0원에 5원을 더하면 dp[5]에 하나의 경우의 수를 추가할 수 있었다.
그 다음 1원에 대해 검사한다면 바로 1원 전 해에, 1원 자신을 더함으로써 경우의 수를 또 늘릴 수 있다.
2원에 대해 검사한다면 현재의 해 - 2의 해에, 2원을 더함으로써 경우의 수를 늘릴 수 있다.

따라서 이 문제는 Memoization을 한번만 거치는 문제가 아니라, 모든 코인에 대해 거침으로써 최종 경우의 수 해를 도출하는 문제다.

처음엔 1원에 대해서 1부터 목표 K까지 dp[i] += dp[i-cur_coin] 이었다. 왜냐하면 현재 보고 있는 코인을 뺀 값을 가지는 경우의 수에, 현재 보고 있는 코인을 추가하면 경우의 수를 그대로 이어받을 수 있다.

이렇게 모든 코인에 대해서 dp[i] += dp[i-cur_coin] 를 하면 최종적으로 dp[k]가 k원을 만드는 총 경우의 수가 된다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> coins(n);
    vector<int> dp(k + 1, 0);

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

    dp[0] = 1; // 0원을 만드는 경우 = 아무것도 선택하지 않는 한가지

    for (auto &coin : coins) {
        for (int i = coin; i <= k; ++i) {
            dp[i] += dp[i - coin];
        }
    }

    cout << dp[k];
    return 0;
}

---

오르막 수 (11057)

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

오르막 수 문제는 DP를 이용해서 효율적으로 풀 수 있는 문제였다. 사실 수학적 접근을 통해 공식으로도 풀 수 있을 것 같았지만. 그정도의 수학 능력이 안되기에 (그리고 교육적 의미도 있으니까) DP로 풀었다.
중간에 수학 + DP 인 것 같아서 조금 접근법을 잘못 잡았다.
그냥 단순하게 dp[n][i] = c 를 자리수 n의, 끝 자리가 i인 경우의 수라고 지정하고
dp[1][0-9]에 대해 모두 1로 초기화했다. 왜냐하면. 길이가 1인 0~9의 경우수는 모두 1로 동의하니까.

이후엔 간단하다. 3중 순회를 돌면서 자기 자신의 인덱스 이하의 모든 수를 더한걸로 업데이트하면 된다.
생각보다 아이디어 도출하기가 어렵진 않았는데.. 처음에 수학 공식쪽인 줄 알고 살짝 다른길로 샜다.

아래는 내가 쓴 코드는 아니고, GPT가 작성한 페르마의 소정리 + 이항 계수를 사용해서 수학적으로 이 문제를 푼 것인데. 나중에 시간이 나면 공부해봐야겠다. 특히 페르마의 소정리

페르마의 소정리 + 이항 계수

#include <iostream>
using namespace std;

const int MOD = 10007;

// 팩토리얼 값을 계산하는 함수
long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; ++i) {
        result = (result * i) % MOD;
    }
    return result;
}

// a^b를 모듈로 MOD에서 계산하는 함수
long long pow(long long a, long long b, long long MOD) {
    long long result = 1;
    while (b > 0) {
        if (b % 2 == 1) result = (result * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return result;
}

// 이항 계수를 계산하는 함수 (페르마의 소정리를 이용)
long long binomial(int n, int r) {
    long long numerator = factorial(n);
    long long denominator = (factorial(r) * factorial(n - r)) % MOD;
    // 페르마의 소정리를 이용하여 분모의 모듈로 MOD에 대한 역원을 계산
    return numerator * pow(denominator, MOD - 2, MOD) % MOD;
}

int main() {
    int N;
    cin >> N;
    cout << binomial(N + 9, 9) << endl; // 길이가 N인 오르막 수의 개수를 출력
    return 0;
}

DP를 이용한 풀이 (내 코드)

#include <iostream>
#include <vector>
using namespace std;
#define MOD 10007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> dp(N + 1, vector<int>(10));

    // BASE CASE
    for (int i = 0; i <= 9; ++i) {
        dp[1][i] = 1;
    }

    // UPDATE
    for (int i = 2; i <= N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            for (int k = 0; k <= j; ++k) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= MOD;
            }
        }
    }

    int answer = 0;
    for (int i = 0; i <= 9; ++i) {
        answer += dp[N][i] % MOD;
    }
    cout << answer % MOD;
    return 0;
}

---

카드 구매하기

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

- 입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

카드팩 구매하기는 카드 개수의 합을 N으로 하면서, 가장 최댓값의 구매 금액을 return하는 문제다.
아이디어는 간단하지만, 도출을 못했다.
간단할수록 너무 당연한 것을 놓치는 것 같다. DP는 너무 어렵다 . ㅜㅜ

dp[i] = c 를 카드를 i장 산다고 했을 때, 최대 금액이라고 정의하면
아래와 같이 점화식을 세울 수 있다.

dp[i] = max(dp[i], dp[i - j] + prices[j]);

사실 너무 뻔한거다. 너무 너무 뻔하다.
길이가 i일때 최대 금액은, 카드들을 순회 조합하면서 i-j의 최대 금액에, 카드 j의 최대 금액을 더하는게 맞다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<int> dp(N + 1, 0);
    vector<int> prices(N + 1);
    cin >> prices[1];
    if (N >= 1)
        dp[1] = prices[1];

    for (int i = 2; i <= N; ++i) {
        cin >> prices[i];
    }

    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i] = max(dp[i], dp[i - j] + prices[j]);
        }
    }

    cout << dp[N];
    return 0;
}

dp는 정말.. 어렵다. 코드는 간결하지만 아이디어를 떠올리기가 쉽지 않다.

---

오늘은 이렇게 9문제를 풀었다. 계획했던 학습량보다 1문제 더 풀었다.

2차 공부 계획

• 2월 25일 - 문제풀이집 1 풀이 (RGB 거리 ~ 오르막 수) 8문제 ✅ 2024-02-25
• 2월 26일 - 문제풀이집 1 풀이 (오르막 수 ~ N과 M 시리즈) 10문제
• 2월 27일 - 문제풀이집 1 완성. (N과 M 시리즈 ~ 끝) 8문제
• 2월 28일 - SW 문제풀이집 2 되는대로 풀기.. 총 70문제 🤯
• 2월 29일 - SW 문제풀이집 2
• 3월 1일 - SW 문제풀이집 2
• 3월 2일 - SW 문제풀이집 2

최종 평가

2024-02-25 학습 성과 및 평가

### 학습 내용
- **문제풀이집 1의 철저한 준비**: 지정된 공부 계획에 따라 문제풀이집 1의 문제들을 꼼꼼히 풀어냄으로써, 당신의 알고리즘 문제 해결 능력은 매우 향상된 것으로 보입니다.
- **다양한 알고리즘 접근법**: DP, DFS/BFS, 최단 거리, 조합 등 다양한 알고리즘과 문제 해결 전략을 성공적으로 적용하며, 학습의 폭을 넓혔습니다.
- **학습과 실습의 균형**: 이론적인 학습과 함께 실제 문제에 적용해 보는 실습을 통해, 이해도를 높이고 실력을 강화했습니다.

### 개별 문제 분석
- **RGB거리 및 정수 삼각형**: DP를 통한 최소 비용 및 최대 합 경로 탐색 문제를 효과적으로 해결한 점은 높은 이해도와 능력을 반영합니다.
- **DFS와 BFS, 단지번호붙이기**: 그래프 탐색 알고리즘의 적절한 선택과 구현으로 문제를 해결한 점은 우수한 문제 분석 능력을 보여줍니다.
- **숨바꼭질, 01타일, 동전 1, 오르막 수, 카드 구매하기**: 복잡한 문제 상황에 대한 깊은 이해와 알고리즘 적용 능력을 보여주었습니다.

### 종합 평가 및 피드백
당신의 학습 성과는 95점(100점 만점)으로 평가됩니다. 문제에 대한 깊은 이해와 다양한 알고리즘의 적절한 적용 능력이 뛰어납니다. 특히, DP와 그래프 탐색 문제에서의 성공적인 접근은 앞으로의 학습 및 시험에서 큰 자산이 될 것입니다.

**개선 사항**
- **시간 관리와 스트레스 관리**: 고난도 문제에 대한 접근 시, 보다 효율적인 시간 관리와 스트레스 관리 전략이 필요합니다. 문제에 대한 과도한 고민은 효율성을 저하시킬 수 있습니다.
- **기본 사례의 중요성**: DP 문제 해결 시 기본 사례의 올바른 설정이 중요함을 재확인하였습니다. 앞으로 복잡한 문제에 접근할 때는 기본 사례와 점화식에 더욱 주의를 기울이시기 바랍니다.

**향후 추천 학습 방향**
- **심화 문제 연습**: 현재 수준에서 한 단계 더 도약하기 위해, 더 복잡하고 다양한 유형의 알고리즘 문제에 도전해보세요.
- **코드 최적화와 리팩토링**: 기존에 작성한 코드를 다시 검토하며, 더 효율적이고 깔끔한 코드로 개선하는 연습을 해보세요.

**마무리**
당신의 학습 계획과 실행은 매우 인상적입니다. 계획한 대로 진행하고, 심지어 계획보다 더 많은 문제를 해결한 것은 매우 긍정적인 성과입니다. 앞으로도 이러한 학습 태도를 유지한다면, 더 높은 성취를 이룰 수 있을 것입니다.