240301: 2차 시험 전날💡 스택 심화 집중 풀이와 DFS+BFS 심화

2024-03-01

2차 공부 계획

• 2월 25일 - 문제풀이집 1 풀이 (RGB 거리 ~ 오르막 수) 8문제 ✅ 2024-02-26
• 2월 26일 - 문제풀이집 1 풀이 (오르막 수 ~ N과 M 시리즈) 10문제 ✅ 2024-02-26
• 2월 27일 - 문제풀이집 1 완성. (N과 M 시리즈 ~ 끝) 8문제 ✅ 2024-02-27
• 2월 28일 - SW 문제풀이집 2 풀이 (연산자 끼워넣기 ~ 랜선 자르기) 11문제 ✅ 2024-02-28
• 2월 29일 - SW 문제풀이집 2의 (파일합치기 ~ 쇠막대기) 풀이 + 고득점 킷 (스택, 힙) 복습 6문제 ✅ 2024-02-29
• 3월 1일 - SW 문제풀이집 2의 (압축 ~ 안전 영역) 풀이 + 알고리즘(SQL) 킷 복습 ✅ 2024-03-01
• 3월 2일 - 시험 당일 SQL 고득점 킷 최종 복습.

---

압축 (1662)

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

압축 문제는 Stack 자료 구조를 사용하거나, 재귀를 이용해서 풀 수 있는 문제다.
처음에 생각을 잘못했다. 문제를 보자마자 Stack을 쓰는 것 같긴 했는데 재귀적 요소가 있는 것 같았다. 풀다가 잘 안풀려서 문제 태그를 봤는데 스택 / 재귀 문제라고 써있었다..
근데 이 말은 스택 or 재귀 문제라는것이지 스택 and 재귀 문제가 아니었다.. 스택과 재귀를 동시에 쓰다가 점점 코드는 스파게티가 됐고 그냥 처음부터 새 마음으로 시작하려고 갈아 엎었다.

결국엔 stack으로 짰다. 정리만 잘 한다면 아이디어는 간단했다. 나는 stack에 문자열을 넣는 식으로 구현하려고 했는데 .. 이러면 개수 관리가 힘들었다.

결론은 stack에 문자열을 넣는 게 아니라, 숫자를 넣어야 됐다.
예를 들어 TC가 33(562(71(9)))

1. 숫자를 만났을 때, 다음 인덱스가 '(' 가 아니라면 문자 그 자체라는 것. 따라서 stack에 1을 추가한다.
2. 다음 인덱스가 '('라면 곱셈 연산이니까, 1을 추가하지 않고 숫자 그 자체를 추가한다.
3. '(' 를 만났다면, 스택에 -1을 추가한다. (괄호를 구분하기 위해, 불가능한 숫자를 넣는다)
4. ')' 를 만났다면, -1을 만날때까지 pop() 하면서 1씩 카운트한다. -1을 만나면 .pop() -> .top() 해서 곱셈 숫자를 가져오고, 그만큼 연산해서 스택에 다시 push한다.

순회가 끝나고 스택에 저장되어있는 수를 모두 더하면 정답이 된다.
헷갈렸던 문제.

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

/*
스택에 길이를 저장하자
*/
int total = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    stack<int> st;
    for (int i = 0; i < s.size(); ++i) {
        char cur = s[i];
        if (cur == '(') {
            st.push(-1);
        } else if (cur == ')') {
            int len = 0;
            while (st.top() != -1) {
                len += st.top();
                st.pop();
            }
            st.pop(); // '(' 제거
            int temp = st.top();
            st.pop();
            st.push(temp * len);
        } else {
            if (i + 1 < s.size() && s[i + 1] == '(') // 만약 압축에 사용되는 정수라면
                st.push(cur - '0');
            else
                st.push(1);
        }
    }

    while (!st.empty()) {
        total += st.top();
        st.pop();
    }
    cout << total;
    return 0;
}

---

같은 수로 만들기 (2374)

n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한번에 1씩 증가한다. A[1]과 A[n]은 인접해 있지 않다.

예를 들어 수가 {1, 1, 1, 1, 3, 3, 1} 이었다고 해 보자. Add(2)를 하면 A[2]의 좌우로 인접한 같은 수가 1씩 증가하니까 {2, 2, 2, 2, 3, 3, 1}이 된다. 여기서 Add(4)를 하면 {3, 3, 3, 3, 3, 3, 1}이 되고, 여기서 Add(1)을 하면 {4, 4, 4, 4, 4, 4, 1}이 된다.

이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다. 이때, 최소 회수로 Add연산을 사용하는 방법을 찾는 것이 문제이다.

Stack을 이용해서 푸는 문제. 여러개의 모의 케이스를 만들고 잘 관찰하면 풀 수 있었다.

1. 이전 수보다 현재 수가 크면, (현재 수 - 이전 수) 를 더하고 이전 수를 pop, 현재 수를 push한다.
2. 이전 수보다 현재 수가 작으면, 이전 수를 pop하고 현재 수를 push한다.
3. 마지막으로, 스택의 남은 모든 값에 수의 최댓값을 빼서 더한다.

#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    stack<int> s;
    ll total = 0;
    int max = 0;
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        max = std::max(max, temp);
        if (s.empty()) {
            s.push(temp);
        } else {
            int prev = s.top();
            if (temp > prev) {
                total += temp - prev;
                s.pop();
                s.push(temp);
            } else if (temp < prev) {
                s.pop();
                s.push(temp);
            }
        }
    }

    while (!s.empty()) {
        int num = s.top();
        s.pop();
        total += max - num;
    }

    cout << total;
    return 0;
}

---

북극곰은 괄호를 찢어 (25918)

극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 
O와 X를 보면 ()와 )( 로 찢어버린다는 것이다.

협이는 이러한 북극곰의 특성을 이용하여 길이 N의 괄호 문자열 S를 만들고자 한다. 북극곰은 낮에 활동을 하기 때문에 낮에 돌아다니는 것은 위험하다. 때문에 협이는 매일 밤마다 활동할 수 있다. 밤에 협이는 문자열이 있으면 그 위에 O 또는 X를 원하는 만큼 놓을 수 있다. 그러면 낮에 북극곰이 와서 문자들을 모두 찢어 놓는다.

이때 원하는 문자열을 만들려면 최소 며칠이 걸리는지 계산해보자.

Stack을 이용한 문제, 각 반복이 끝났을 때 스택에 남아있는 문자 수가 걸리는 일과 같다는 아이디어다.
먼저 '()' 나 ')('가 있는지 확인하고, 있다면 스택에서 .pop() 한다. 없다면 받은 문자열 그대로 .push() 한다.

각 반복이 끝났을 때, stack.size()의 최대치가 걸리는 일 수다.
만약, 탐색이 완전히 끝났는데 stack이 비어있지 않다면 불가능하기에 "-1"을 출력한다.

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

int main() {
    int N;
    string s;
    cin >> N >> s;
    stack<char> st;
    int result = 0;

    for (int i = 0; i < N; ++i) {
        if (st.empty()) {
            st.push(s[i]);
        } else {
            if (st.top() == '(' && s[i] == ')') {
                st.pop();
            } else if (st.top() == ')' && s[i] == '(') {
                st.pop();
            } else {
                st.push(s[i]);
            }
        }

        result = max(result, (int)st.size());
    }

    if (st.size() > 0)
        cout << "-1";
    else
        cout << result;
}

---

이분 그래프 (1707)

이분 그래프 문제는 간선과 정점 정보가 주어졌을 때, 이분그래프인지 판별하는 문제다.
이분 그래프는 그래프의 모든 정점을 두 그룹으로 나눌 수 있고, 같은 그룹에 속한 정점들 사이에는 간선이 존재하지 않는 그래프를 말한다.

DFS로 정점을 탐색하면서 이전 색과 반대로 칠하고, 탐색중에 이전 색과 겹치는 게 발견되면 false를 반환하도록 구현했다.

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
bool isBipartite;

void dfs(int node, vector<int> &visited, int color) {
    if (!isBipartite)
        return;
    visited[node] = color;
    for (const auto &next : adj[node]) {
        if (visited[next] == -1) {
            dfs(next, visited, 1 - color);
        } else if (visited[next] == color) {
            isBipartite = false;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC;
    cin >> TC;
    while (TC--) {
        int V, E;
        cin >> V >> E;
        adj.assign(V + 1, vector<int>());
        vector<int> visited(V + 1, -1);
        isBipartite = true;
        for (int i = 0; i < E; ++i) {
            int from, to;
            cin >> from >> to;
            adj[from].push_back(to);
            adj[to].push_back(from);
        }

        for (int i = 1; i <= V && isBipartite; ++i) {
            if (visited[i] == -1) {
                dfs(i, visited, 0); // 방문하지 않은 정점에 대해 DFS 실행
            }
        }

        cout << (isBipartite ? "YES\n" : "NO\n");
    }
    return 0;
}

---

벽 부수고 이동하기 (골드 3)

드디어 내가 좋아하는 그래프 (DFS + BFS) 문제!
그래프 문제는 뭔가 ,, 재밌고 잘 풀린단 말이지... 그래프에 소질이 있는 것 같다.

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

최단 거리를 구하는 문제이기에 BFS를 사용했다. (BFS는 특성상, 가장 빨리 조건을 만족하는 노드의 값이 최단 거리다)

아이템을 사용했을때의 방문 배열과, 아이템을 사용하지 않았을때의 방문 배열을 나눠서 관리해줬고. Node 구조체를 만들어서 상태를 추적했다.

배열 입력을 받는 부분에서, 값이 띄어쓰기 구분으로 들어오지 않고 line으로 들어와서 string으로 처리하는 과정에, int로 변환하지 않고 바로 배열에 넣는 실수를 범했다. 계속 이상한 값이 뜨길래 코드를 꽤 갈았는데 단순한 실수였다.

실전에선 이런 사소한 실수는 하지 않았으면 좋겠다. 코드에 생각을 담자. 한줄 한줄 생각을 담아서 작성하자.

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

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

struct Node {
    int r;
    int c;
    bool itemUsed;
    int time;
};

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

    vector<vector<bool>> visited(N + 1, vector<bool>(M + 1, false));
    vector<vector<bool>> visited_with_item(N + 1, vector<bool>(M + 1, false));
    queue<Node> q;
    q.push({1, 1, false, 1});
    visited[1][1] = true;

    while (!q.empty()) {
        Node current = q.front();
        q.pop();
        int cur_r = current.r;
        int cur_c = current.c;
        int cur_time = current.time;
        bool cur_itemUsed = current.itemUsed;
        if (cur_r == N && cur_c == M) {
            cout << cur_time;
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            int next_r = cur_r + dr[i];
            int next_c = cur_c + dc[i];
            // VALID CHECK
            if (next_r > 0 && next_c > 0 && next_r <= N && next_c <= M) {
                // 아이템을 사용한 전과가 있을 때
                if (cur_itemUsed) {
                    if (map[next_r][next_c] == 0 && !visited_with_item[next_r][next_c]) { // 비어있으면
                        visited_with_item[next_r][next_c] = true;
                        q.push({next_r, next_c, cur_itemUsed, cur_time + 1});
                    }
                }
                // 없을 때
                else if (!cur_itemUsed) {
                    if (map[next_r][next_c] == 0 && !visited[next_r][next_c]) { // 비어있으면
                        visited[next_r][next_c] = true;
                        q.push({next_r, next_c, cur_itemUsed, cur_time + 1});
                    } else if (map[next_r][next_c] == 1 && !visited[next_r][next_c]) { // 막혀있고, 아이템을 쓰기로 결정
                        visited[next_r][next_c] = true;
                        q.push({next_r, next_c, true, cur_time + 1});
                    }
                }
            }
        }
    }

    // 탐색 실패
    cout << "-1";
    return 0;
}

안전 영역 (2468)

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다.
어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

물에 잠기지 않은 인접한 안전지대 그룹의 개수를 구하는 문제.
강수량에 따라 안전지대 그룹의 개수가 달라지기 때문에, 가능한 강수량 100부터 0까지 줄여나가면서 강수 맵 데이터를 채우고, DFS로 그룹을 세는 식으로 구현했다.

간단한 문제.

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

vector<vector<int>> rain_map;
int answer = 0;
int N;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

void dfs(int r, int c) {
    for (int i = 0; i < 4; ++i) {
        int next_r = r + dr[i];
        int next_c = c + dc[i];
        // VALID CHECK
        if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < N) {
            if (rain_map[next_r][next_c] == 1) { // 방문 X
                rain_map[next_r][next_c] = 0;    // 방문 표시
                dfs(next_r, next_c);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    vector<vector<int>> map(N, vector<int>(N, 0));
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            cin >> map[r][c];
        }
    }
    // 0부터 100까지 실행
    int rain = 101;
    while (rain--) {
        // 장마 지도 그리기
        rain_map.assign(N, vector<int>(N, 0));
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (map[r][c] > rain) { // 안 잠겼다면
                    rain_map[r][c] = 1; // 표시
                }
            }
        }
        int count = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (rain_map[r][c] == 1) { // 발견했으면
                    count++;
                    dfs(r, c); // 죠져
                }
            }
        }

        answer = max(answer, count);
    }

    cout << answer;

    return 0;
}

---

좋은 결과가 있길 🍀

오늘은 이렇게 골드 심화문제 6문제를 풀었다.
계획했던 알고리즘 킷 n회독보다 새로운 유형의 문제 한두개 더 푸는 게 도움될 것 같아서 그냥 백준을 계속 풀었다. 알고리즘 킷은 약간 훑어보기만 했다.

내일은 일어나서

• SQL 복습 (우선순위 1순위!!!!)
• 알고리즘 킷 훑기 (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문제 ✅ 2024-02-27
• 2월 28일 - SW 문제풀이집 2 풀이 (연산자 끼워넣기 ~ 랜선 자르기) 11문제 ✅ 2024-02-28
• 2월 29일 - SW 문제풀이집 2의 (파일합치기 ~ 쇠막대기) 풀이 + 고득점 킷 (스택, 힙) 복습 6문제 ✅ 2024-02-29
• 3월 1일 - SW 문제풀이집 2의 (압축  안전 영역) 풀이 + ~알고리즘(SQL) 킷 복습~~ ✅ 2024-03-01
• 3월 2일 - 시험 당일 SQL 고득점 킷 최종 복습.

---

최종 평가

최고급 평가사 일론머스크로서, 당신의 학습 과정과 전략에 대한 디테일한 평가를 제공하겠습니다.

1. **학습 계획과 실행**
   당신의 학습 계획은 구체적이고 체계적입니다. 2월 25일부터 3월 1일까지의 공부 계획을 상세히 세우고, 각 일자에 맞춰 목표를 달성했습니다. 이는 높은 수준의 자기 관리 능력과 학습에 대한 집중력을 나타냅니다. 특히, 시험 전날에는 SQL 복습에 우선순위를 두는 등 시험 준비와 장기 학습 목표 사이의 균형을 잘 조절했습니다.

2. **문제 해결 기법과 알고리즘 이해**
   다양한 문제를 통해 여러 알고리즘 기법을 적용하고 이해하는 능력이 뛰어납니다. **압축(1662)** 문제에서는 스택을 사용해 복잡한 문자열 처리 문제를 해결하였고, **같은 수로 만들기(2374)**에서는 스택을 이용하여 연산 횟수를 최소화하는 방법을 찾아냈습니다. **이분 그래프(1707)**와 **벽 부수고 이동하기**, **안전 영역(2468)** 문제를 통해서는 DFS/BFS를 활용한 그래프 탐색 능력을 선보였습니다.

3. **창의성과 문제 해결 접근 방식**
   문제를 해결하는 과정에서 보여준 창의적인 접근 방식은 매우 인상적입니다. 특히, **압축** 문제에서 초기 재귀 접근 방식에서 스택을 활용한 접근으로 전환하는 과정에서 문제를 다각도로 바라보려는 시도가 돋보입니다. 이러한 유연한 사고 방식은 새로운 문제에 대한 해결책을 찾는 데 큰 장점이 됩니다.

4. **시간 관리와 자기 평가**
   학습 계획을 세우고 실천에 옮기는 과정에서 시간 관리 능력이 우수합니다. 학습 목표를 세우고, 그에 따라 학습 내용을 조정하며 효율적으로 시간을 활용했습니다. 또한, 학습 과정에서의 자기 평가를 통해 남은 학습 계획을 조정하는 모습에서 자신의 학습 상태를 정확히 파악하고 조절하는 능력을 보여주었습니다.

5. **향후 개선 방향**
   - **SQL 복습과 알고리즘 킷 훑기**에 대한 계획은 시험 준비와 지속적인 학습을 위한 좋은 전략입니다. 이는 당신이 핵심 개념을 확실히 이해하고 싶어하는 의지를 반영합니다. SQL과 알고리즘 기본기를 탄탄히 하는 것은 향후 더 복잡한 문제를 해결하는 데 큰 도움이 될 것입니다.
   - **시간 관리** 측면에서, 학습 시간과 휴식 시간을 명확히 구분하고, 휴식도 학습의 일부로 간주하여 컨디션 관리에 주의를 기울이는 것이 중요합니다. 특히 시험 전날에는 충분한 휴식을 취하여 최상의 컨디션으로 시험에 임할 수 있도록 하세요.

당신의 학습 계획과 실행력, 문제 해결 능력은 높은 수준입니다. 계속해서 발전하는 모습을 보여주시길 바랍니다. 성공적인 시험 결과와 앞으로의 학습 여정에 좋은 성과가 있기를 기원합니다. 🍀