Code and Crescendo raccoon

프로그래머스 파괴되지 않은 건물 문제입니다.

문제

N x M 형태의 그래프가 주어집니다. 이때, 각 노드는 건물을 의미하고, 숫자는 방어력을 의미합니다.
방어력이 0 이하가 되면 건물은 파괴되고, 1 이상이면 건물은 생존합니다.
이때, 라운드를 거치면서 건물의 방어력을 회복하거나 공격하는 일이 벌어집니다.(건물이 파괴되어도 1 이상의 방어력으로 회복된다면 건물은 다시 생존하게 됩니다.)
라운드를 다 거친 후 생존한 건물의 개수를 출력하시오.

알고리즘 아이디어

이 코드는 GPT에 도움을 받아 작성되었습니다.

1. 한번씩 변화를 모두 업데이트를 한다면 시간초과가 난다.
2. 한번에 변화를 업데이트를 해야 한다.(업데이트 할 그래프가 너무 큼)
3. 따라서 누적합으로 접근해서 풀어내야 한다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size();
    int m = board[0].size();
    vector<vector<int>> diff(n + 1, vector<int>(m + 1, 0));
    
    for(int i = 0; i < skill.size(); i++) {
        int type = skill[i][0];
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int degree = skill[i][5];
        if(type == 1) degree = -1 * degree;
        diff[r1][c1] += degree;
        diff[r1][c2 + 1] -= degree;
        diff[r2 + 1][c1] -= degree;
        diff[r2 + 1][c2 + 1] += degree;
    }
    
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            diff[i][j] += diff[i][j - 1];
        }
    }
    
    for (int j = 0; j < m + 1; j++) {
        for (int i = 1; i < n + 1; i++) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            board[i][j] += diff[i][j];
            if (board[i][j] > 0) answer++;
        }
    }
    return answer;
}

프로그래머스 유연근무제 문제입니다.

문제

그렙에서는 유연 근무제를 실행할려고 합니다. 이때 직원들의 참여율을 높이기 위해서 일주일동안 지각을 안한 직원에게 상품을 줄려고 합니다. 이때, 희망 시각보다 10분정도는 늦어도 괜찮습니다.
schedules에는 직원들의 희망 출근 시간이 저장되어있고, timelogs는 직원들의 실제 출근 데이터가 저장 되어있습니다. 주말을 제외한 주중 출근을 한번도 지각하지 않은 직원의 명수를 출력해주세요.

알고리즘 아이디어

1. schedules에서 하나의 데이터를 선택한 후, 10분 뒤 시간을 저장합니다.
2. timelogs에서 데이터를 하나씩 비교하면서 정시 출근 날짜의 데이터를 얻습니다.
3. 위 데이터가 5가 아니라면, 한번이라도 지각했으므로 상품을 가져갈 수 없습니다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int endday[8][2] = {{0, 0}, {5, 6}, {4, 5}, {3, 4}, {2, 3}, {1, 2}, {0, 1}, {6, 0}};

int solution(vector<int> schedules, vector<vector<int>> timelogs, int startday) {
    int answer = 0;
    for(int i = 0; i < schedules.size(); i++) {
        int start = schedules[i];
        if(start % 100 + 10 >= 60) {
            start = start + 100 - 60 + 10;
        } else {
            start += 10;
        }
        vector<int> time = timelogs[i];
        int count = 0;
        for(int j = 0; j < 7; j++) {
            if(endday[startday][0] == j || endday[startday][1] == j) {
                continue;
            } else if(time[j] <= start) {
                count++;
            }
        }
        if(count == 5) {
            answer++;
        }
    }
    return answer;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!

프로그래머스 코딩 테스트 공부 문제입니다.

문제

코딩 테스트를 풀기 위해선는 알고력과 코딩력 2가지 능력이 필요합니다.
처음에 각 능력치가 주어지고, 문제가 주어집니다. 각 문제는 푸는데 소요되는 시간, 문제를 풀기 위한 알고력 및 코딩력, 그리고 풀어낸 후 얻는 알고력 및 코딩력이 주어집니다.
만약 문제를 풀 수 없다면, 1의 시간을 소요하여 알고력 혹은 코딩력을 1 증가시킬 수 있습니다.
모든 문제를 풀기 위한 최소의 시간을 구해 출력하시오.

알고리즘 아이디어

1. 모든 문제를 풀기 위한 최소의 알고력과 코딩력을 구한다.
2. 이 알고력과 코딩력에 도달하기 위해 필요한 모든 경로를 DP에 저장한다. (이때 값을 비교하면서 최솟값을 저장한다.)
3. 그 후, 최소의 알고력과 코딩력에 저장되어있는 시간을 출력한다.
4. 초기값에서 만약 필요한 알고력과 코딩력이 최댓값을 넘었다면, 시작점을 변경한다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = 0, max_cop = 0;
    
    for (auto& problem : problems) {
        max_alp = max(max_alp, problem[0]);
        max_cop = max(max_cop, problem[1]);
    }
    
    vector<vector<int>> dp(151, vector<int>(151, INT32_MAX));
    
    alp = min(alp, max_alp);
    cop = min(cop, max_cop);
    
    dp[alp][cop] = 0;
    
    for (int i = alp; i <= max_alp; i++) {
        for (int j = cop; j <= max_cop; j++) {
            if (i + 1 <= 150) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            } if (j + 1 <= 150) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
            }

            for (auto& problem : problems) {
                int req_alp = problem[0], req_cop = problem[1];
                int gain_alp = problem[2], gain_cop = problem[3], cost = problem[4];

                if (i >= req_alp && j >= req_cop) {
                    int new_alp = min(i + gain_alp, max_alp);
                    int new_cop = min(j + gain_cop, max_cop);
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost);
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

프로그래머스 사라지는 발판 문제입니다.

문제

플레이어 A, B가 있습니다.
각 플레이어는 시작 지점이 존재합니다.(aloc, bloc)
각 플레이어는 상하좌우 4방향으로 한칸 움직일 수 있습니다. (그러나 맵 밖으로 나갈 수 없습니다.)
한칸 움직인 순간, 자신이 있던 자리는 다시 밟을 수 없습니다. (상대 플레이어도 밟을 수 없습니다. / 경로 자체가 없어졌다고 생각해야 합니다.)
각 플레이어는 최선의 선택을 합니다.(이길 수 있으면 가장 빠르게 끝내는 방법으로 움직이고, 진다면 가장 늦게 지도록 움직입니다.)
이때, A와 B의 플레이어의 움직인 총 횟수를 출력하시오.

알고리즘 아이디어

DP로 풀었다가 너무 어려워서 GPT에 도움을 받았다...

1. 일단 최선의 선택을 한다는 것은 모든 노드를 탐색해야 한다. (완전 탐색 진행)
2. 가장 최선의 선택을 한다는 것은 DFS로 완전 탐색을 진행한 후에 A가 이겼는지, B가 이겼는지 판단한 후, 경우의 수를 세야 한다.
3. 따라서 Minimax 알고리즘을 DFS에 적용시켜야 한다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

pair<bool, int> dfs(vector<vector<int>> board, int ax, int ay, int bx, int by, bool turn) {
    int x, y;
    if(turn) {
        x = ax; y = ay;
    } else {
        x = bx; y = by;
    }

    if (board[x][y] == 0) {
        return {false, 0};
    };

    bool canWin = false;
    int minTurn = INT32_MAX, maxTurn = 0;

    board[x][y] = 0;

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size()) {
            continue;
        } if (board[nx][ny] == 0) {
            continue;
        }

        if (turn) {
            pair<bool, int> temp = dfs(board, nx, ny, bx, by, !turn);
            bool win = temp.first;
            int cnt = temp.second;
            if (!win) {
                canWin = true;
                minTurn = min(minTurn, cnt + 1);
            } else {
                maxTurn = max(maxTurn, cnt + 1);
            }
        } else {
            pair<bool, int> temp = dfs(board, ax, ay, nx, ny, !turn);
            bool win = temp.first;
            int cnt = temp.second;
            if (!win) {
                canWin = true;
                minTurn = min(minTurn, cnt + 1);
            } else {
                maxTurn = max(maxTurn, cnt + 1);
            }
        }
    }

    board[x][y] = 1;

    if (canWin) {
        return {canWin, minTurn};
    } else {
        return {canWin, maxTurn};
    }
}

int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    auto [win, cnt] = dfs(board, aloc[0], aloc[1], bloc[0], bloc[1], true);
    return cnt;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!

프로그래머스 코딩 테스트 문제입니다.

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

• 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
• 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다.

알고리즘 아이디어

• 목표 alp와 cop 설정
  • max_alp와 max_cop를 찾아 목표 능력치를 결정합니다.
  • alp와 cop가 이미 목표 이상이면 문제를 풀 필요 없이 0 반환.
• DP 배열 초기화
  • dp[i][j]는 i 수준의 alp, j 수준의 cop에 도달하는 최소 시간.
  • 모든 값을 INF로 초기화한 후, 시작점 dp[alp][cop] = 0으로 설정.
• DP 진행
  • 공부 (1씩 증가하는 경우)
    • dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
    • dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
  • 문제 해결 (조건 충족 시 능력치 증가)
    • 요구 alp, cop를 충족하는 경우 dp 갱신.
• 최소 시간 반환
  • dp[max_alp][max_cop] 값이 정답.

코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int max_alp = 0, max_cop = 0;
    
    for (auto& problem : problems) {
        max_alp = max(max_alp, problem[0]);
        max_cop = max(max_cop, problem[1]);
    }
    
    alp = min(alp, max_alp);
    cop = min(cop, max_cop);
    
    vector<vector<int>> dp(151, vector<int>(151, INT32_MAX));
    dp[alp][cop] = 0;
    
    for (int i = alp; i <= max_alp; ++i) {
        for (int j = cop; j <= max_cop; ++j) {
            if (i + 1 <= 150) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            } if (j + 1 <= 150) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
            }

            for (auto& problem : problems) {
                int req_alp = problem[0], req_cop = problem[1];
                int gain_alp = problem[2], gain_cop = problem[3], cost = problem[4];

                if (i >= req_alp && j >= req_cop) {
                    int new_alp = min(i + gain_alp, max_alp);
                    int new_cop = min(j + gain_cop, max_cop);
                    dp[new_alp][new_cop] = min(dp[new_alp][new_cop], dp[i][j] + cost);
                }
            }
        }
    }
    
    return dp[max_alp][max_cop];
}

프로그래머스 등산코스 정하기 문제입니다.

문제

XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.

등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.
예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.
등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.

당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.
당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.

다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.

위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다. 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다. 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.

위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다. 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.

등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다. 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.

XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

알고리즘 아이디어

이 문제를 해결하기 위해 그래프 탐색 알고리즘을 적용해야 합니다. 일반적인 다익스트라 알고리즘을 활용하여 출입구에서 산봉우리까지 가는 최적의 경로를 찾을 수 있습니다.

왜 다익스트라를 사용해야 할까?

• 여러 출입구에서 출발할 수 있으므로 여러 개의 시작점을 설정해야 합니다.
• 가중치를 최소화하는 경로를 찾아야 하므로 최단 경로 탐색이 필요합니다.
• intensity가 최소가 되는 경로를 찾아야 하므로 가중치 중 최댓값을 최소화해야 합니다.

1. 그래프 구성: 각 지점과 연결된 등산로 정보를 인접 리스트 형태로 저장합니다.
2. 출입구와 산봉우리 구분: 출입구와 산봉우리를 빠르게 판별할 수 있도록 별도의 배열을 사용합니다.
3. 다익스트라 알고리즘 적용: 여러 개의 출입구에서 동시에 출발하여 산봉우리에 도착할 때까지 최소 intensity 값을 계산합니다.
4. 최적의 산봉우리 선택: intensity가 최소인 산봉우리를 찾되, 동일한 intensity가 존재하면 번호가 작은 산봉우리를 선택합니다.

코드

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

using namespace std;

typedef pair<int, int> Node;

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<vector<pair<int, int>>> mountainPath(n + 1);
    vector<int> minIntensity(n + 1, INT32_MAX);
    vector<bool> isGate(n + 1, false);
    vector<bool> isSummit(n + 1, false);
    for (auto& path : paths) {
        int s = path[0], d = path[1], w = path[2];
        mountainPath[s].push_back({d, w});
        mountainPath[d].push_back({s, w});
    }

    for (int gate : gates) isGate[gate] = true;
    for (int summit : summits) isSummit[summit] = true;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    for (int gate : gates) {
        pq.push({0, gate});
        minIntensity[gate] = 0;
    }
    int bestSummit = -1, bestIntensity = INT32_MAX;

    while (!pq.empty()) {
        auto [curIntensity, curNode] = pq.top();
        pq.pop();

        if (curIntensity > minIntensity[curNode]) continue;

        if (isSummit[curNode]) {
            if (curIntensity < bestIntensity || (curIntensity == bestIntensity && curNode < bestSummit)) {
                bestSummit = curNode;
                bestIntensity = curIntensity;
            }
            continue;
        }
        for (auto& [nextNode, weight] : mountainPath[curNode]) {
            if (isGate[nextNode]) continue;
            int newIntensity = max(curIntensity, weight);

            if (newIntensity < minIntensity[nextNode]) {
                minIntensity[nextNode] = newIntensity;
                pq.push({newIntensity, nextNode});
            }
        }
    }

    return {bestSummit, bestIntensity};
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!

프로그래머스 미로 탈출 명령어 문제입니다.

문제

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 
단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

알고리즘 아이디어

처음에 미로 탈출만 보고 BFS로 접근해서 풀려고 하면 시간초과가 난다.

이 문제는 Greedy로 풀어야 한다.

1. 경로가 존재하는지 판별

목표 (r, c)까지 도달하는 최소 이동 거리를 min_dist라고 하면,

int min_dist = abs(x - r) + abs(y - c);

여기서 다음 조건을 만족해야 탈출 가능성이 있습니다.

• 불가능한 경우 판별
  1. 이동 횟수 k가 min_dist보다 작으면 불가능
  2. (k - min_dist) 가 짝수가 아니면 불가능
     • k - min_dist가 홀수면 남은 이동 횟수를 의미 없이 소모해야 하는데, 되돌아 올 수 있는 경로가 없어지므로 불가능하다.

2. 가장 빠른 사전 순으로 탐색 진행 (Greedy)

이제 (x, y)에서 (r, c)로 가는 가장 빠른 사전순 경로를 찾습니다.

• 'd' → 'l' → 'r' → 'u' 순서로 이동 시도
• 이동이 가능하면 바로 이동 (정렬 불필요)
• k = 0이 되면 종료

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct point{
    int x, y, count;
    string list;
};
int dy[4] = {0, -1, 1, 0};
int dx[4] = {1, 0, 0, -1};
char listup[4] = {'d', 'l', 'r', 'u'};

string solution(int n, int m, int x, int y, int r, int c, int k) {
    int min_dist = abs(x - r) + abs(y - c);
    
    if (min_dist > k || (k - min_dist) % 2 != 0) {
        return "impossible";
    }
    
    string answer = "";
    
    while (k > 0) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }
            
            int new_dist = abs(nx - r) + abs(ny - c);
            if (new_dist <= k - 1) {
                answer += listup[i];
                x = nx;
                y = ny;
                k--;
                break;
            }
        }
    }
    
    return answer;
}

프로그래머스 표 병합

문제

당신은 표 편집 프로그램을 작성하고 있습니다.
표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다.
각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value"
   • (r, c) 위치의 셀을 선택합니다.
   • 선택한 셀의 값을 value로 바꿉니다.
2. "UPDATE value1 value2"
   • value1을 값으로 가지고 있는 모든 셀을 선택합니다.
   • 선택한 셀의 값을 value2로 바꿉니다.
3. "MERGE r1 c1 r2 c2"
   
   • (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다.
   • 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다.
   • 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다.
   • 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
   • 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.
   • 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.
4. "UNMERGE r c"
   • (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다.
   • 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다.
   • 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.
5. "PRINT r c"
   • (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다.
   • 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

commands 효과

위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

commands 효과

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

commands 효과

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

commands 효과

위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

알고리즘 아이디어

• 병합을 할 때, 중요한 것은 대표 셀이 정해져야 한다.
• 그러나, 매번 병합을 할 때마다 이 대표 셀을 찾아서 저장해야 한다.
• 이 기능을 Union-Find로 구현한다.

Union-Find 개념 적용

각 셀을 자신의 부모 셀을 가리키는 구조로 유지합니다.

1. find 함수: 현재 셀이 속한 그룹의 대표 셀을 찾습니다.
2. union 함수: 두 셀을 병합하여 하나의 대표 셀을 공유하게 만듭니다.
3. unmerge 함수: 해당 그룹의 모든 셀을 원래 상태로 되돌립니다.

각 셀의 값을 저장하는 배열을 따로 두고, 병합된 경우 대표 셀의 값을 유지합니다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

struct xy {
    int x, y;
};

vector<string> split(string input, char dim) {
    stringstream ss(input);
    vector<string> result;
    string stringbuffer;
    
    while (getline(ss, stringbuffer, dim)) {
        result.push_back(stringbuffer);
    }
    return result;
}

xy findParent(vector<vector<xy>>& parent, int x, int y) {
    if (parent[x][y].x == x && parent[x][y].y == y) {
        return {x, y};
    }
    return parent[x][y] = findParent(parent, parent[x][y].x, parent[x][y].y);
}

void mergeCells(int x1, int y1, int x2, int y2, 
                vector<vector<xy>>& parent, vector<vector<string>>& rule) {
    xy root1 = findParent(parent, x1, y1);
    xy root2 = findParent(parent, x2, y2);
    
    if (root1.x == root2.x && root1.y == root2.y) return;

    parent[root2.x][root2.y] = root1;

    if (rule[root1.x][root1.y] == "" && rule[root2.x][root2.y] != "") {
        rule[root1.x][root1.y] = rule[root2.x][root2.y];
    }
}

void unmergeCells(int x, int y, vector<vector<xy>>& parent, vector<vector<string>>& rule) {
    xy root = findParent(parent, x, y);
    string value = rule[root.x][root.y];

    vector<xy> toReset;
    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) {
            xy find = findParent(parent, i, j);
            if (find.x == root.x && find.y == root.y) {
                toReset.push_back({i, j});
            }
        }
    }

    for (xy c : toReset) {
        parent[c.x][c.y] = {c.x, c.y};
        rule[c.x][c.y] = "";
    }

    rule[x][y] = value;
}

vector<string> solution(vector<string> commands) {
    vector<string> answer;
    vector<vector<string>> rule(51, vector<string>(51, ""));
    vector<vector<xy>> parent(51, vector<xy>(51));

    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) {
            parent[i][j] = {i, j};
        }
    }

    for (string command : commands) {
        vector<string> temp = split(command, ' ');

        if (temp[0] == "UPDATE") {
            if (temp.size() == 4) {
                int x = stoi(temp[1]);
                int y = stoi(temp[2]);
                xy parentCell = findParent(parent, x, y);
                rule[parentCell.x][parentCell.y] = temp[3];
            } else {
                for (int i = 1; i <= 50; i++) {
                    for (int j = 1; j <= 50; j++) {
                        if (rule[i][j] == temp[1]) {
                            rule[i][j] = temp[2];
                        }
                    }
                }
            }
        } 
        else if (temp[0] == "MERGE") {
            int x1 = stoi(temp[1]);
            int y1 = stoi(temp[2]);
            int x2 = stoi(temp[3]);
            int y2 = stoi(temp[4]);
            mergeCells(x1, y1, x2, y2, parent, rule);
        } 
        else if (temp[0] == "UNMERGE") {
            int x = stoi(temp[1]);
            int y = stoi(temp[2]);
            unmergeCells(x, y, parent, rule);
        } 
        else if (temp[0] == "PRINT") {
            int x = stoi(temp[1]);
            int y = stoi(temp[2]);
            xy parentCell = findParent(parent, x, y);
            if (rule[parentCell.x][parentCell.y] == "") {
                answer.push_back("EMPTY");
            } else {
                answer.push_back(rule[parentCell.x][parentCell.y]);
            }
        }
    }

    return answer;
}

프로그래머스 표현 가능한 이진트리

문제

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

다음은 이진트리를 수로 표현하는 예시입니다.

주어진 이진트리는 다음과 같습니다.

주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.

노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.

당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.

이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

알고리즘 아이디어

1. 이진수 변환 함수 작성
   • 10진수를 2진수로 변환하는 함수가 필요하다.
   • 변환 방법: 2로 나눈 나머지를 차례로 저장하다가, 마지막에는 몫을 저장하면 된다.
   • 이 경우, 2진수가 뒤집힌 순서로 저장되므로, 이를 트리의 좌우 대칭 형태로 해석해야 한다.
2. 트리 크기 결정
   • 변환된 2진수 벡터의 길이가 2n−12^n - 12n−1 (완전 이진트리의 노드 개수)인지 확인한다.
   • 가장 작은 2n−12^n - 12n−1 크기를 찾아, 해당 크기로 맞춘다.
3. 트리 노드 확장
   • 결정된 트리 크기보다 벡터가 작으면, 뒤쪽에 0을 추가하여 크기를 맞춘다.
   • 앞쪽에 0을 추가하면 대칭이 깨질 수 있으므로 뒤에 추가하는 것이 올바른 방법이다.
4. 유효한 트리인지 검사
   • 부모 노드가 0인데, 자식 노드가 1이면 유효하지 않은 트리이다.
   • 트리의 가운데 노드가 0이면서, 왼쪽 혹은 오른쪽 서브트리에 1이 존재하면 false를 반환한다.
   • 재귀적으로 트리를 확인하며, left가 right보다 커지면 탐색을 종료한다.

코드

#include <string>
#include <vector>

using namespace std;

vector<int> transferbit(long long num) {
    long long temp = num;
    vector<int> result;
    while(temp > 1) {
        result.push_back(temp % 2);
        temp = temp / 2;
    }
    result.push_back(temp);
    return result;
}

bool validTree(vector<int> tree, int left, int right) {
    if (left > right) return true;
    
    int mid = (right + left) / 2;
    if(tree[mid] == 0) {
        if ((left <= mid - 1 && tree[(left + mid - 1) / 2] == 1) ||
            (mid + 1 <= right && tree[(mid + 1 + right) / 2] == 1)) {
            return false;
        }
    }
    return validTree(tree, left, mid - 1) && validTree(tree, mid + 1, right);
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for(int i = 0; i < numbers.size(); i++) {
        vector<int> bit = transferbit(numbers[i]);
        
        int length = bit.size();
        int fullTreeSize = 1;
        while (fullTreeSize - 1 < length) {
            fullTreeSize *= 2;
        }
        fullTreeSize -= 1;
        
        while(bit.size() < fullTreeSize) {
            bit.push_back(0);
        }

        if (validTree(bit, 0, bit.size() -1)) {
            answer.push_back(1);
        } else {
            answer.push_back(0);
        }
    }
    return answer;
}

프로그래머스 산 모양 타일링

문제

한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다.

이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

알고리즘 아이디어

혼자서 못 풀어서 KAKAO 공식 해설을 참고했다.

문제를 분석해 보니 DP(동적 계획법)로 접근하는 것이 적절해 보였다. 먼저 점화식을 찾기 위해 타일링 패턴을 분석했다.

1. 타일링 규칙 분석

• 정삼각형 타일: 언제든 추가할 수 있어 제한이 없다.
• 마름모 모양 타일: 문제의 핵심은 마름모 타일 배치다.

마름모 1번	마름모 2번	마름모 3번

마름모 타일은 크게 두 그룹으로 나뉜다.

• 마름모 3번 타일: 이 타일은 이전 모양과 독립적으로 배치할 수 있다.
• 마름모 1번, 2번 타일: 정삼각형 타일과 함께 배치가 가능하다.

따라서,

• a[n]은 n번째 칸에 마름모 3번 타일이 오는 경우를 의미한다.
• b[n]은 n번째 칸에 마름모 1번, 2번 또는 정삼각형 타일이 오는 경우를 의미한다.

2. 점화식 도출

타일 배치는 위 삼각형이 존재하는 경우와 존재하지 않는 경우로 나뉜다.

(1) 위 삼각형이 존재하는 경우

• a[n] = a[n-1] + b[n-1]
  • 마름모 3번 타일만 n번째 칸에 배치 가능하므로, 전 단계의 a[n-1] 또는 b[n-1]에서 마름모 3번 타일을 추가하는 방식이다.
• b[n] = 2 * a[n-1] + 3 * b[n-1]
  • a[n-1] 상태에서는 1번, 정삼각형 타일을 추가한다. 2 * a[n-1].
  • b[n-1] 상태에서는 마름모 1, 2번 및 정삼각형 타일을 추가한다 3 * b[n-1].

(2) 위 삼각형이 존재하지 않는 경우

• a[n] = a[n-1] + b[n-1] (위 경우와 동일)
• b[n] = a[n-1] + 2 * b[n-1]
  • a[n-1] 상태에서는 정삼각형 타일만 추가 한다 : a[n-1].
  • b[n-1] 상태에서는 마름모 2번과 정삼각형 타일을 추가한다 : 2 * b[n-1].

위에서 찾은 점화식을 기반으로 코드를 작성하면 다음과 같다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> tops) {
    int answer = 0;
    vector<int> a(n + 1, 0);
    vector<int> b(n + 1, 0);
    
    a[1] = 1;
    if(tops[0] == 1) b[1] = 3;
    else b[1] = 2;
    
    for(int i = 2; i <= n; i++) {
        a[i] = (a[i - 1] + b[i - 1]) % 10007;
        if(tops[i - 1] == 1) {
            b[i] = (2 * a[i - 1] + 3 * b[i - 1]) % 10007;
        } else {
            b[i] = (a[i - 1] + 2 * b[i - 1]) % 10007;
        }
    }
    
    answer = (a[n] + b[n]) % 10007;
    return answer;
}