chaetudy

(8/20-X)

(8/22-O)

https://school.programmers.co.kr/learn/courses/30/lessons/1844

구현

bfs를 이용해서 목적지까지의 최단 거리를 구한다.

1) 각 좌표까지마다의 최단 거리를 담을 2차원 배열, 2) 방문했는지 안 했는지 체크 할 2차원 배열이 필요하다.

queue<pair<int,int>>에 출발지를 넣고 큐를 순회하고 비워 가면서 상하좌우의 이동 가능한 좌표들을 큐에 넣는다.

실수

처음에 dfs로 풀었는데 시간 초과가 났다. dfs로 풀게 되면 도착지에 도달해도 계속해서 탐색을 하기 때문에 결국 완전 탐색을 할 수밖에 없다. bfs로 풀면 도착지에 도달했을 때 바로 반복문을 탈출해서 결과 값을 도출할 수 있기 때문에 시간이 덜 걸린다. 이 문제를 통해서 상황에 따라 dfs와 bfs를 적절히 선택해야 된다는 것을 알았다.

코드

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


int cnt[101][101]; // 1)
bool visited[101][101]; // 2)
int solution(vector<vector<int> > maps)
{
    int m = maps.size();// 행의 개수
    int n = maps[0].size(); // 열의 개수
    int answer = -1;

    queue<pair<int, int>> q;

    q.push({ 0,0 }); // x,y 

    cnt[0][0] = 1;
    visited[0][0] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        q.pop();

        // x,y가 (n-1, m-1)이라면 탈출
        if (x == n-1 && y == m - 1) {
            break;
        }

        
        // 상하좌우가 맵 밖을 뚫지 않고 1이라면 push
        if (y - 1 >= 0 && maps[y - 1][x] == 1 && visited[y - 1][x] == false) {
            q.push({ x, y - 1 });
            cnt[y - 1][x] = cnt[y][x] + 1;
            visited[y - 1][x] = true;
        }
        if (y + 1 < m && maps[y + 1][x] == 1 && visited[y + 1][x] == false) {
            q.push({ x, y + 1});
            cnt[y + 1][x] = cnt[y][x] + 1;
            visited[y + 1][x] = true;
        }
        if (x - 1 >= 0 && maps[y][x - 1] == 1 && visited[y][x-1] == false) {
            q.push({ x - 1, y });
            cnt[y][x - 1] = cnt[y][x] + 1;
            visited[y][x - 1] = true;
        }
        if (x + 1 < n && maps[y][x + 1] == 1 && visited[y][x+1] == false) {
            q.push({ x + 1, y });
            cnt[y][x + 1] = cnt[y][x] + 1;
            visited[y][x+1] = true;
        }
        

    }
    if (cnt[m - 1][n - 1] == 0)
        return -1;
    return cnt[m - 1][n - 1];
}

(7/23 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/12906

구현1

벡터 내의 연속된 숫자만 삭제하면 된다.

stack(이하 s)에 arr의 요소들을 반복문을 통해 순서대로 집어넣는다. 집어넣을 때 s의 top과 집어넣을 요소가 같다면 continue 처리하면 끝.

코드1

#include <vector>
#include <iostream>
#include <stack>

using namespace std;

vector<int> solution(vector<int> arr)
{
    vector<int> answer;
    
    stack<int> s;
    for (const auto& i : arr) {
        if (s.empty()) {
            s.push(i);
            answer.push_back(i);
        }
        else {
            if (s.top() != i) {
                s.push(i);
                answer.push_back(i);
            }
        }
    }


    return answer;
}

구현2

unique를 이용하여 중복 원소 제거

코드2

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> arr)
{
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    vector<int> answer(arr);
    return answer;
}

비교

도움 된 글

https://en.cppreference.com/w/cpp/algorithm/unique

(7/22 - 세모) 푸는 데 1시간이나 걸렸음

https://school.programmers.co.kr/learn/courses/30/lessons/87946

구현

dfs로 입장 가능한 모든 던전을 탐색하고, 가장 높은 depth를 가졌을 때의 수를 세서 반환한다.

실수

dfs도 완전 탐색의 일부구나.. 완전 탐색이라는 건 brute force만 해당되는 줄 알았다..!

코드

#include <string>
#include <vector>

using namespace std;

bool visited[9];
int max_cnt;
void dfs(int cur, int pirodo, vector<vector<int>>& ds, int size, int cnt) {
    if (pirodo < ds[cur][0]) { // 피로도가 최소 피로도보다 낮음, 진입 불가
        return;
    }

    // 던전 입장
    pirodo -= ds[cur][1];
    visited[cur] = true;


    for (int i = 0; i < size; i++) {
        if (visited[i] == true) continue;
        dfs(i, pirodo, ds, size, cnt + 1);
    }

    // 더 돌 수 있는 던전 없음
    max_cnt = max(max_cnt, cnt);

    visited[cur] = false;
}


int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;

    int pirodo = k;
    int size = dungeons.size();
    
    for (int i = 0; i < size; i++) {
        dfs(i, pirodo, dungeons, size, 1);
    }
    answer = max_cnt;
    return answer;
}

(7/18 - X) 문제 풀이하는 데도, 문제를 이해하는 데도 굉장히 오랜 시간이 걸렸다. 바보인가ㅠㅠ

https://school.programmers.co.kr/learn/courses/30/lessons/42584/

구현

실수

코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) {

    stack<int> s;
    int size = prices.size();
    vector<int> answer(size, 0);

    for (int i = 0; i < size; i++) {
        while (!s.empty()) {
            if (prices[i] < prices[s.top()]) {
                answer[s.top()] = i - s.top();
                s.pop();
            }
            else {
                break;
            }
        }
        s.push(i);
    }

    while (!s.empty()) {
        answer[s.top()] = size - s.top() - 1;
        s.pop();
    }

    return answer;
}

int main() {
    solution({ 1,2,3,2,1 });
}

도움 된 글

https://moondol-ai.tistory.com/269

https://sanghyu.tistory.com/155

https://ilmiodiario.tistory.com/119

https://school.programmers.co.kr/questions/20326

(7/16 - X) 다른 사람 풀이 보고 풀었는데 제대로 이해했는지 확신이 안 서서 다시 풀기로 했다.

(7/18 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/43164

제한 사항

1. 경로에 방향이 있다.

2. 주어진 항공권을 모두 사용해야 한다.

3. 가능 경로가 2개 이상이라면 알파벳 오름차순으로 간다.

구현

dfs로 모든 노드들을 방문하되, 같은 노드를 두 번 이상 방문할 수도 있으니 visited 처리를 노드가 아닌 간선(항공권)에 한다.

0. 항공권들을 오름차순으로 정렬한다. (제한 사항 3 충족)

1. start를 "ICN"로 해서 dfs를 시작한다.

1.1 use_cnt가 항공권 개수와 같은지 검사한다.

 같지 않다면-> 1.2로 넘어간다.

 같다면 -> true를 반환한다.

1.2 start를 route에 push 한다.

1.3 항공권들을 탐색하여 start가 출발지인 항공권을 찾는다.

 찾았으면-> 해당 항공권을 visited 처리하고, 해당 항공권의 도착지를 start로 해서 dfs 한다. use_cnt를 1 증가시킨다.

 찾지 못 했으면 -> 항공권을 전부 사용하지 못 했는데 길이 막힌 경우이다. start를 route에서 pop 하고 해당 false를 반환한다.

실수

길이 막혔는데 항공권을 다 사용하지 않은 경우를 생각해야 한다.

ex) { "ICN", "a" }, { "a", "b" }, { "b", "d" }, { "a", "c" }, { "c", "a" }

코드

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

using namespace std;

int tickets_size;

bool dfs(vector<vector<string>>& tickets, string start, int use_cnt, vector<bool>& visited, vector<string>& route) {
    route.push_back(start);
    if (use_cnt == tickets_size) return true;
    for (int i = 0; i < tickets_size; i++) {
        if (tickets[i][0] != start) continue;
        if (visited[i] == true) continue;
        visited[i] = true;
        if (true == dfs(tickets, tickets[i][1], use_cnt + 1, visited, route))
            return true;
        else {
            visited[i] = false;
        }
    }
    route.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    tickets_size = tickets.size();
    
    sort(tickets.begin(), tickets.end());
    
    int use_cnt = 0;
    
    vector<bool> visited(tickets_size, false);
    dfs(tickets, "ICN", use_cnt, visited, answer);


    return answer;
}

도움 받은 글

https://yabmoons.tistory.com/528

(7/16 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/42842

구현

갈색을 테두리로, 카펫을 i행 j열로 생각하고 풀이했다.

코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    vector<vector<int>> v;

    // i행 j열 바둑판이라 생각하자.
    // 테두리이므로 j의 최솟값은 y + 2
    int i = 3, j = 3;
    while (true) {
        int line = (brown - (j * 2)) / 2;
        int y_cnt = line * (j - 2);
        if (y_cnt == yellow) {
            i = line + 2;
            break;
        }
        j++;
    }
    if (i > j) {
        int temp = j;
        j = i;
        i = temp;
    }

    answer.push_back(j);
    answer.push_back(i);
    return answer;
}

int main()
{
    solution(24, 24);
}

(7/15 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

베스트 앨범에 수록될 곡의 고유번호를 answer에 담아야 한다.

구현

map 두 개, vector 두 개를 이용해서 풀었다. 이하 m1, m2, v1, v2이다.

1. 가장 많이 플레이된 장르를 구한다.

1.1 m1에 (key)장르, (value)플레이 횟수를 누적하여 담는다. map의 key는 중복되지 않음을 이용한다.

1.2 map을 value 기준으로 정렬해야 한다. --> v1에 이동시킨 후 second 기준으로 내림차순 sorting(lamda 이용)한다.

1.3 v1[0].first가 가장 많이 플레이된 장르이다.

1.4 m1에서 value가 v1[0].first인 원소를 삭제한다.

2. 가장 많이 플레이된 장르 내 곡들을 두 개 또는 한 개를 뽑는다.

2.1 가장 많이 플레이된 장르에 해당하는 곡들을 m2에 (key)고유번호, (value)플레이 횟수로 담는다.

2.2 map을 value 기준으로 정렬한다. --> v2에 이동시킨 후 second 기준으로 내림차순 sorting 한다.

2.3 v2의 사이즈가 2보다 작으면 v2의 사이즈만큼 앞에서부터 answer에 넣고, v2의 사이즈가 2보다 크면 앞에서부터 2개의 원소를 answer에 넣는다.

3. m1이 empty 상태인가? Y->4, N->1

4. answer를 반환한다.

실수 (코드 상에 표시)

1. 장르에 곡이 꼭 2개 이상 있는 게 아니다. 1개일 경우를 고려해야 한다.

2. 같은 장르 내에 플레이 횟수가 같은 곡이 있다면 고유 번호가 낮은 순으로 뽑는다.

코드

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

using namespace std;

// 베스트 앨범에 들어갈 노래의 고유번호를 순서대로 리턴!
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int song_cnt = genres.size();

    // 1. 가장 많이 플레이된 장르는?
    map<string, int> m1;
    for (int i = 0; i < song_cnt; i++) {
        m1[genres[i]] += plays[i];
    }
    int genres_cnt = m1.size();

    int while_cnt = 0;
    while (!m1.empty()) {
        vector < pair<string, int >> v1(m1.begin(), m1.end());
        sort(v1.begin(), v1.end(), [](const pair<string, int>& p1, const pair<string, int>& p2) {
            return p1.second > p2.second;
            });
        string maxplay_genre = v1[0].first;
        m1.erase(maxplay_genre);

        // 2. 가장 많이 플레이된 장르 중에서 가장 많이 플레이된 곡 두 개를 뽑아서 고유번호를 push
        map<int, int> m2; // first 고유번호, second 플레이 횟수
        for (int i = 0; i < song_cnt; i++) {
            if (genres[i] == maxplay_genre) {
                m2[i] = plays[i];
            }
        }
        vector<pair<int, int>> v2(m2.begin(), m2.end());
        sort(v2.begin(), v2.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
            if (p1.second == p2.second) { // 실수 2
                p1.first < p2.first;
            }
            else {
                return p1.second > p2.second;
            }});
        int song_cnt = m2.size();
        for (int i = 0; i < song_cnt; i++) { // 실수1
            if (i >= 2) break;
            answer.push_back(v2[i].first);
        }
    }



    return answer;
}

(7/11 - X) 문제를 제대로 이해 못 함

(7/12 - X)

(7/14 - O)

https://school.programmers.co.kr/learn/courses/30/lessons/42898

구현

모든 좌표의 최단 경로의 개수를 dp 테이블에 갱신해 준다.

웅덩이가 있는 좌표는 -1로 넣어 준다.

이동할 수 있는 방법은 오른쪽, 아래이므로 기본적으로 최단 경로는 [x-1][y]와 [x][y-1]을 더한 값으로 계산한다. 위/왼쪽이 막혀 있는(웅덩이 또는 테두리 위치) 경우도 있으므로 아래 경우1234에 따라 계산한다. 막혀 있음은 -1로 표기한다.

• 경우1. 왼쪽, 위쪽 모두 막혀 있는 경우 - 갈 수 있는 방법이 0이다.
• 경우2. 왼쪽이 막혀 있는 경우 - 위쪽에서만 올 수 있으므로, 위쪽에서 올 수 있는 경로 개수를 더한다.
• 경우3. 위쪽이 막혀 있는 경우 - 왼쪽에서 올 수 있는 경로 개수를 더한다.
• 경우4. 위/왼쪽에서 모두 올 수 있는 경우 - 위/왼쪽의 경로 개수를 모두 더한다.

계산한 최단 경로 개수에 1,000,000,007를 나머지 연산 해서 dp 테이블에 넣어 준다.

실수

!좌표 반전!

코드

// 프로그래머스 고득점kit 동적계획법 - 등굣길
// (7/11 - X) 틀림
// (7/12 - X)
// (7/14 - )
#include <string>
#include <vector>

using namespace std;

int dp[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for (int i = 0; i < 101; i++) {
        dp[0][i] = -1;
        dp[i][0] = -1;
    }

    dp[1][1] = 1;

    for (vector<int>& v : puddles) {
        dp[v[1]][v[0]] = -1;
    }


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue; // 시작 좌표
            if (dp[i][j] == -1) continue; // 웅덩이
            if (dp[i][j - 1] == -1 && dp[i - 1][j] == -1) { // 경우4
                dp[i][j] = 0;
            }
            else if (dp[i][j - 1] == -1) { // 경우2
                dp[i][j] = dp[i - 1][j] % 1'000'000'007;
            }
            else if (dp[i - 1][j] == -1) { // 경우3
                dp[i][j] = dp[i][j - 1] % 1'000'000'007;
            } 
            else { // 경우4
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1'000'000'007;
            }
        }
    }
    
    answer = dp[n][m] ;

    return answer;
}
int main() {
    vector<vector<int>> v = { {2,2} };
    solution(4, 3, v);
}