Code and Crescendo raccoon

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

문제

그렙에서는 유연 근무제를 실행할려고 합니다. 이때 직원들의 참여율을 높이기 위해서 일주일동안 지각을 안한 직원에게 상품을 줄려고 합니다. 이때, 희망 시각보다 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;
}

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

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

문제

플레이어 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;
}

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

프로그래머스 양과늑대

문제

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

알고리즘 아이디어

1. 모든 노드를 탐색해야 한다.

2. 탐색을 할 때, 갈 수 있는 모든 자리를 다 들고 다녀야 한다... 그럼 너비탐색이 맞지 않나 싶지만 코드가 너무 어지럽다...

따라서 DFS에서 Queue를 같이 들고 다니는 이상한 알고리즘이 탄생한다.

코드

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

using namespace std;

vector<vector<int>> graph;
int maxSheep = 0;

void DFS(int wolf, int sheep, int nowNode, vector<int> info, queue<int> q) {
    if(info[nowNode] == 0) {
        sheep++;
    } else {
        wolf++;
    }
    
    if (wolf >= sheep) {
        return;
    }
    if (maxSheep < sheep) {
        maxSheep = sheep;
    }
    
    for(int x = 0; x < graph[nowNode].size(); x++) {
        q.push(graph[nowNode][x]);
    }
    
    
    for(int x = 0; x < q.size(); x++) {
        int nextNode = q.front();
        q.pop();
        DFS(wolf, sheep, nextNode, info, q);
        q.push(nextNode);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    graph.resize(info.size(), vector<int>());
    
    for(int i = 0; i < edges.size(); i++) {
        int nowNode = edges[i][0];
        int nextNode = edges[i][1];
        
        graph[nowNode].push_back(nextNode);
    }
    queue<int> q;
    
    DFS(0,0,0,info, q);
    
    return maxSheep;
}

참고문헌

양과늑대 알고리즘 구현