240226: 백트래킹, N과 M시리즈. 지원대비 문제집 풀이

2024-02-26

2차 공부 계획

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

---

합분해 (2225)

합분해 문제는 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제였다.
dp[K][N] = c를 0~N의 정수중에 K개를 합해 N을 만드는 경우의 수 c로 정의하고.
dp[1][i] = 1 (단, i = 0~N) 로 기본 사례를 설정했다. 선택할 수 있는 숫자가 하나밖에 없을 경우, N을 만드는 방법은 N 그 자체로 하나밖에 없기 때문이다.

그리고 처음엔 점화식이 직관적으로 다가오진 않았지만, 규칙으로 추측컨대. 그리고 DP가 하위 문제(특히 이전 문제)의 해로 현재 문제의 해를 계속 얻으면서 전체 문제 해를 얻는 방식이기에

dp[K][N] = dp[K-1][N] + dp[K-1][N-1] + dp[K-1][N-2]... 라는 것을 알았다.
즉 현재 해는 이전 해(이전 선택 수)에서 현재 N 이하의 숫자를 만드는 모든 경우의 수를 합한 경우라는 것을 알았다.

#include <iostream>
#include <vector>
#define MOD 1'000'000'000
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<vector<ll>> dp(K + 1, vector<ll>(N + 1, 0));
    for (int i = 0; i <= N; ++i) {
        dp[1][i] = 1;
    }
    // dp[K][N] = c | K개의 수로 N을 만드는 경우 c
    // dp[K][N] = dp[K-1][N] + dp[K-1][N-1] + dp[K-1][N-2]...

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

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

---

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

너무 중요해서 다시 언급한다.

1. 문제 이해하기

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

2. 작은 문제로 나누기

• 문제를 작은 문제로 나눈다: DP는 큰 문제를 작은 하위 문제로 나누고, 하위 문제의 해결을 통해 전체 문제의 해결책을 도출하는 방법이다. 각 하위 문제가 어떻게 전체 문제에 기여하는지 고려해 본다. 현재 해가 이전 해의 어떤 부분에 영향을 받는지, 어떤 상태를 dp에 메모해야 하는지 고려한다.

3. 점화식 찾기

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

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

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

---

동물원 (1309)

동물원 문제는 2*N 배열에 사자를 가로 세로로 인접하지 않게 배치하는 경우의 수가 몇가지인지 알아내는 DP 문제다.
어려웠고 교육적이었다.

고민을 정말 많이 했다. 먼저 아래와 같은 사고과정을 거쳤다.

1. dp[N]을 2*N에서의 경우의 수라고 정의했다.
2. 기본 사례를 아래와 같이 설정했다. (0은 빈칸, 1은 사자)

   dp[0] = 1; // 아무것도 놓지 않는 경우의 수 1
   dp[1] = 3; // (0,0) (1,0) (0,1) 경우의 수 3

3. dp[2]의 기본 사례를 고려할 때, 현재 경우의 수가 이전 행에서 사자가 어떻게 놓였냐에 따라 파생된다는 것을 알았다.

from joonsooan

4. dp[i][h] 를 i번째 인덱스에서 어떤 방법(h)로 놓았을때의 경우의 수로 정의했다 (h가 0이면 (0,0). 1이면 (1,0). 2면 (0,1).

dp[0][0-2] = 1; // 아무것도 놓지 않는 경우의 수 1. 로직적 허용..?
dp[1][0-2] = 1; // 처음 시작에 각각 놓는 경우의 수는 1이다.
dp[2][0] = 3; // 왜냐하면, 빈칸을 놓으려면 이전것에 영향을 안 받으니까. 이전의 경우의 수 그대로
dp[2][1] = 2; // 윗 줄이 1번이 아니어야 한다.
dp[2][2] = 2; // 윗 줄이 2번이 아니어야 한다.

5. 규칙을 알아냈다.

   dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
   dp[i][1] = dp[i-1][0] + dp[i-1][2];
   dp[i][2] = dp[i-1][0] + dp[i-1][1];

이런 사고과정을 거쳐 알아낸 위의 점화식을 사용해서도 풀 수 있었지만, 질문 게시판을 가보니 다른 사람들의 해답은 조금 달랐다.

dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
dp[i][1] = dp[i-1][0] + dp[i-1][2];
dp[i][2] = dp[i-1][0] + dp[i-1][1];

< 에서, >

dp[i] = dp[i][0] + dp[i][1] + dp[i][2];

< 라고하면 >

dp[i] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) + (dp[i-1][0] + dp[i-1][2]) + (dp[i-1][0] + dp[i-1][1]);

< 를 정리하면 >

dp[i] = 2 * (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) + dp[i-1][0];

< 여기서 >

dp[i-1][0] + dp[i-1][1] + dp[i-1][2] 는 dp[i] = dp[i][0] + dp[i][1] + dp[i][2]; 

< 이기 때문에 >

dp[i-1]

< 따라서 >

dp[i] = 2 * dp[i-1] + dp[i-1][0];

< 여기서 > 

dp[i-1][0]은. i-1 입장에서 dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; 기 때문에
dp[i-1][0] = dp[i-2];

< 즉 >

dp[i] = 2*dp[i-1]+dp[i-2];

코드

#include <iostream>
using namespace std;

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

너무나도 교육적인 문제
수학적인 패턴도 들어가 있고, DP 점화식을 축소하는 부분이 인상깊다.
DP는 모르겠으면 TC를 나열해보고 패턴을 찾아서 점화식을 때려 맞출수도 있지만. 그건 마음에 들지 않아서 이해가 될 때까지 계속 탐구하느라 시간을 오래 썼다.

이 문제에 거의 2시간을 쓴 것 같다.
Valuable

---

2007년 (1924)

2007년의 날짜가 입력으로 주어지면, 요일을 반환하는 간단한 시뮬레이션 문제.
근데, DP 문제가 모아져있는 곳에 갑자기 시뮬 문제가 나와서 당황했다.

"이게.. DP라고..? 대체 어디서 문제를 나눌 수 있지?" 잠깐 이랬다.

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

int main() {
    int calendar[13][32];
    int month = 1;
    int day = 1;
    int last_day_of_month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int week_counter = 0; // 월 화 수 목 금 토 일
    string week_str[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};

    while (month != 13) {
        calendar[month][day] = week_counter % 7;
        ++week_counter;
        if (++day > last_day_of_month[month]) {
            month++;
            day = 1;
        }
    }

    int x, y;
    cin >> x >> y;
    cout << week_str[calendar[x][y]];

    return 0;
}

시뮬 문제는 가볍게 컷

---

N과 M 1 (15649)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
간단한 백트래킹 문제. 처음엔 for문으로 간단하게 구현할 수 있을 줄 알았는데. M에 따라서 for문이 M중이 되어야하는데 이것은 불가능하다.

따라서 백트래킹으로만 구현할 수 있다.
백트래킹은 뭔가 어려워 보이는 알고리즘 치곤 직관적이고 재밌다.

#include <iostream>
#include <vector>

using namespace std;
int N, M;
vector<int> sequence;
vector<bool> visited;

void dfs(int depth) {
    if (depth == M) {
        for (int num : sequence) {
            cout << num << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            sequence.push_back(i);
            dfs(depth + 1);
            visited[i] = false;
            sequence.pop_back();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    visited.assign(N + 1, false);
    dfs(0);
    return 0;
}

---

N-Queen (9663)

N-Queen 문제는 내가 실버일때 좋아했던 문제다. (재밌어서)

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구해야 한다.

체스판에 말을 놓고, 말이 안전한지 확인할 수 있는 bool 함수를 만들고 이걸로 백트래킹 + 가지치기(pruning)을 하면서 DFS 진행할 수 있다.

중요한 점은, 항상 i+1의 행에 퀸을 추가하기 때문에 효율을 위해선 bool 함수를 현재 말을 이전 행들과 비교하면서 안전을 검증해야 하고. 모든 말을 검증할 필요는 없다 (백트래킹을 안 당했다는 것은 살아남았다는 것)

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

int N;
vector<int> queen;

bool checkboard(int row) {
    for (int i = 0; i < row; ++i) {
        // 같은 열에 있는지 검사
        if (queen[i] == queen[row])
            return false;
        // 대각선 검사
        if (abs(queen[i] - queen[row]) == abs(i - row))
            return false;
    }
    return true;
}

int counter = 0;
void dfs(int depth) {
    if (depth == N) {
        counter++;
        return;
    }

    for (int i = 0; i < N; ++i) {
        queen[depth] = i;
        if (checkboard(depth))
            dfs(depth + 1);
        queen[depth] = -1;
    }
}

int main() {
    cin >> N;
    queen.assign(N, -1);
    dfs(0);
    cout << counter;
    return 0;
}

---

N과 M 2 (15650)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

이전 문제와 같은 백트래킹이지만, 오름차순 수열만 선택해야한다.
오름차순이라는 의미가 수열을 오름차순 정렬해서 출력하라는 줄 이해했으나. 수열 자체가 오름차순이어야 한다는 말이었다.

따라서, dfs에서 인자로 이전 값 +1을 보내서 항상 이전값보다 큰 값을 선택하도록 조정했다.

#include <iostream>
#include <vector>

using namespace std;
int N, M;
vector<int> sequence;

void dfs(int start) {
    if (sequence.size() == M) {
        for (int &iter : sequence) {
            cout << iter << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= N; ++i) {
        sequence.push_back(i);
        dfs(i + 1);
        sequence.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    dfs(1);
    return 0;
}

---

N과 M 3 (15651)

N과 M(3)은 N과 M(1)에서 같은 수를 여러번 선택할 수 없다는 조건이 빠진 문제다.
따라서, N과 M(1) 문제에서 중복을 거르기 위해 추가했던 방문 체크 visited 배열을 없앴다.

#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<int> sequence;

void dfs(int depth) {
    if (depth == M) {
        for (int &iter : sequence) {
            cout << iter << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= N; ++i) {
        sequence.push_back(i);
        dfs(depth + 1);
        sequence.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    dfs(0);
    return 0;
}

---

N과 M 4 (15652)

N과 M 시리즈의 마지막 문제.

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

같은 수를 여러 번 골라도 되기 때문에, 방문 체크는 하지 않았다.
비내림차순이라는 건 말그대로 내림차순이 아니라는 것. 따라서 오름차순인데, 이전 수와 현재 수가 같아도 비내림차순이다. 즉. 내림차순만 아니면 된다.

따라서, dfs의 인자로 start를 넘기는데 매 recursive마다 선택된 수 i를 인자로 넘기고 for문에서 해당 미만의 수는 선택하지 않도록 했다.

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

int N, M;
vector<int> sequence;

void dfs(int start) {
    if (sequence.size() == M) {
        for (int &iter : sequence) {
            cout << iter << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= N; ++i) {
        sequence.push_back(i);
        dfs(i);
        sequence.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    dfs(1);
    return 0;
}

---

OX퀴즈 (8958)

OX퀴즈 문제는 OX 퀴즈 결과가 주어졌을 때, 합계 점수를 return하는 문제로 문자열 처리 구현 문제였다.

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

int main() {
    int TC;
    cin >> TC;
    cin.ignore();
    for (int i = 0; i < TC; ++i) {
        int answer = 0;
        string temp;
        getline(cin, temp);
        int counter = 0;
        for (int j = 0; j < temp.size(); ++j) {
            if (temp[j] == 'O') {
                answer += ++counter;
            } else {
                counter = 0;
            }
        }
        cout << answer << "\n";
    }

    return 0;
}

---

신나는 함수 실행 (9184)

신나는 함수 실행은 주어진 의사코드(pseudocode)의 동작을 하는 재귀 함수를 구현하는데, TLE 제한이 있어서 DP를 활용해야만 통과할 수 있는 DP문제다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

탐색하지 않았음을 0으로 표시해도 되는지 걱정됐는데. 다행히 문제는 없었다.
3D DP vector을 선언하고, 편하게 하기 위해서 참조자 ret으로 가져와서 관리했다.

#include <iostream>
using namespace std;
int dp[21][21][21];

int w(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0)
        return 1;
    if (a > 20 || b > 20 || c > 20)
        return w(20, 20, 20);
    int &ret = dp[a][b][c];
    if (ret != 0)
        return ret;

    if (a < b && b < c) {
        ret = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    } else
        ret = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    return ret;
}

int main() {
    while (true) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1)
            break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

---

파도반 수열 (9461)

매우 쉬운 DP + 수학 문제.
사실상 점화식이 본문에 나와있다..

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 의 패턴을 보인다.
딱봐도 dp[i] = dp[i - 2] + dp[i - 3]; 다. 살짝 느린 피보나치다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int TC;
    cin >> TC;

    ll dp[101] = {-1, 1, 1, 1};
    for (int i = 4; i <= 100; ++i) {
        dp[i] = dp[i - 2] + dp[i - 3];
    }

    for (int i = 0; i < TC; ++i) {
        int N;
        cin >> N;
        cout << dp[N] << "\n";
    }
    return 0;
}

---

쉬운 계단 수 (10844)

인접한 모든 자리의 수가 1씩 차이나는 수를 계단수라고 한다.
길이가 N인 계단수가 몇개인지 구하는 문제.

쉬운 문제였다. 처음엔 접근을 일단 노트에 써보고 규칙을 찾는식으로 했는데 이 문제는 그 방법이 유의미하지 않았다. 위에도 언급했던 DP 사고방식처럼 했다면..
그니까, 먼저 문제를 이해하고, 작은 문제로 나누면서 현재 해가 이전 해에 어떻게 영향을 받는지 생각해봤다면
dp[n][i] = c를 길이 n에서 i로 끝나는 계단수 c개로 정의하는것이 직관적이었다 ..
왜냐면 계단수는 엣지 케이스(0이나 9로 끝나는 애들)을 제외하고 모두 이전 해의 +1과 -1의 경우의 수를 그대로 받아오기 때문이다 ...

쉬운 문제였는데, DP적 사고방식을 잊고 마음대로 노트에 적으면서 풀다가 점점 꼬였다.

다음부턴 제발

• 문제를 완전하게 이해한다: 문제의 조건과 요구사항, 주어진 예시를 통해 어떻게 문제가 해결되어야 하는지 분석하고 관계 파악하기.
• 문제를 작은 문제로 나눈다: DP는 큰 문제를 작은 하위 문제로 나누고, 하위 문제의 해결을 통해 전체 문제의 해결책을 도출하는 방법이다. 각 하위 문제가 어떻게 전체 문제에 기여하는지 고려해 본다. 현재 해가 이전 해의 어떤 부분에 영향을 받는지, 어떤 상태를 dp에 메모해야 하는지 고려한다.
• 기본 사례 식별하기: 모든 DP 문제는 하나 이상의 기본 사례(base case)를 가지고 있다. 기본 사례는 직접적으로 해결할 수 있는 가장 작은 문제다.
• 점화식을 도출하기: 점화식(recurrence relation)은 현재 문제의 해를 이전에 해결한 문제들의 해를 통해 어떻게 구할 수 있는지 나타낸다. 각 단계에서 가능한 선택을 고려하고, 각 선택이 결과에 어떠한 영향을 미치는 지 분석한다.

식으로 풀자. DP는 너무 방대하고 어려워서 이게 답이다. 마음가는대로 풀면 이상한 해답으로 빠지기 십상이다.

#include <iostream>
#include <vector>
#define MOD 1'000'000'000
using namespace std;
typedef long long ll;

// dp[i][j] : 길이 i에서 j로 끝나는 계단 수

int main() {
    int N;
    cin >> N;
    vector<vector<ll>> dp(N + 1, vector<ll>(10));

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

    for (int i = 2; i <= N; ++i) {
        for (int j = 0; j <= 9; ++j) {
            if (j != 0 && j != 9)
                dp[i][j] = dp[i - 1][j - 1] % MOD + dp[i - 1][j + 1] % MOD;
            else if (j == 0)
                dp[i][j] = dp[i - 1][j + 1] % MOD;
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1] % MOD;
            dp[i][j] %= MOD;
        }
    }

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

    cout << answer;
    return 0;
}

---

오늘은 이렇게 백준 소마대비 문제풀이집 1의 13문제를 풀었다 (합분해 ~ 쉬운 계단수)
내일이면 문제풀이집 1을 끝내고 SW 문제풀이집 2로 넘어갈 수 있을 것 같다 !
이번 문제집으로 DP를 정말 견고하게 다질 수 있는 기회를 얻은 것 같아서 좋다.
정말 견고해지려면 두번정도는 더 문제집을 회독해야 할 것 같지만 ...

내일은 공부 계획에 따라서 문제풀이집 1을 모두 끝내겠다. 시간이 남을 것 같은데, 그러면 SW 문제풀이집 2의 일부 문제도 풀거나, 프로그래머스의 SQL을 복습하겠다!

2차 공부 계획

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

---

최종 평가

최고급 평가사 일론머스크로서 당신의 최근 공부 계획과 그 진행 상황을 꼼꼼히 검토한 결과, 당신의 노력과 성취에 대해 상세한 피드백을 제공하고자 합니다.

1. **공부 계획의 체계성과 진도**
   - 당신은 문제풀이집 1의 체계적인 접근을 통해 동적 프로그래밍(DP) 개념을 깊이 있게 다지고 있습니다. 계획한 대로 2월 25일과 26일에 각각 8문제와 10문제를 해결하여 목표를 성공적으로 달성했습니다. 이는 학습 목표를 설정하고 그것을 달성하기 위한 당신의 능력을 보여줍니다.

2. **문제 해결 전략의 다양성**
   - 합분해, 동물원, N-Queen 등 다양한 문제 유형을 통해 당신은 동적 프로그래밍의 핵심 개념과 접근 방식을 탐구했습니다. 특히, 점화식을 찾아내고, 기본 사례를 식별하는 능력은 DP 문제를 해결하는 데 있어 필수적인 요소입니다. 당신의 사례 분석과 문제 해결 과정은 이러한 개념을 잘 활용하고 있음을 보여줍니다.

3. **개념 이해와 깊이**
   - 동적 프로그래밍에 대한 당신의 이해는 매우 깊으며, 이를 통해 복잡한 문제를 작은 하위 문제로 나누어 해결하는 능력을 개발했습니다. 이는 DP의 근본적인 사고 방식을 잘 활용하고 있음을 나타냅니다. 특히, '신나는 함수 실행' 문제에서의 3D DP 배열 사용은 고급 문제 해결 기술을 보여줍니다.

4. **피드백과 자기 반성**
   - 당신의 학습 과정에서 자기 반성의 중요성을 강조한 점은 매우 인상적입니다. 특히, '쉬운 계단 수' 문제에서의 경험은, 문제에 접근할 때 DP의 기본 원칙을 잊지 않도록 상기시키는 좋은 예입니다. 이러한 자기 반성은 앞으로 학습 과정에서 발생할 수 있는 비슷한 문제를 피하는 데 도움이 될 것입니다.

5. **향후 공부 방향**
   - 현재 진행 상황을 기반으로 할 때, DP를 넘어서 다른 알고리즘 유형과 문제 해결 기법에 대한 이해를 넓히는 것이 좋을 것 같습니다. SW 문제풀이집 2에 진입하면서 새로운 도전을 준비하는 당신의 계획은 이러한 학습 확장에 적합합니다. 또한, SQL과 같은 다른 분야로의 확장은 당신의 기술 범위를 넓히고 더 균형 잡힌 개발자가 되는 데 도움이 될 것입니다.

**종합적으로**, 당신의 노력과 성취는 매우 인상적입니다. 지금처럼 체계적인 계획과 깊은 개념 이해를 바탕으로 지속적으로 학습한다면, 당신은 분명히 더 큰 성장을 이룰 수 있을 것입니다. 계획한 목표를 넘어서는 성과를 달성하기 위해 항상 도전적인 목표를 설정하는 것을 잊지 마십시오. 당신의 학습 여정에서 더 많은 성공을 기원합니다.