재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍으로 푸는 문제이다. 처음에는 (1,1) 부터 (m,n) 까지 가는 최단경로라는 말만 보고 bfs를 떠올려 풀었지만, 이 문제는 최단경로의 개수를 묻는 문제였다. 핵심은 오른쪽과 아래로만 갈 수 없다는 것인데, 이는 (m,n)까지 도달만 하면 무조건 최단경로가 되는 것이다. (1,1)에서 (m,n)으로 가는데 오른쪽과 아래밖에 못간다면 결국 오른쪽으로 m번, 아래로 n번 가야 최단경로이기 때문이다. 이 문제에서 주의할 점은 y좌표와 x좌표가 반대로 되어있다는 것이다. #include #include #include #include using namespace std; int matrix[101][101]; int dp[101][101]; int dy[] = {0, 1}; in..

이 문제는 DFS를 이용하는 Level 3 문제이다. 이 문제에서 핵심은 티켓이 중복될 수 있다는 것과, 정점의 방문 여부와 상관없이 간선이 모두 소진되어야 DFS가 종료되어야 한다는 것이다. 또한 DFS 실행 도중 언제 result에 현재 정점을 넣을 건지도 굉장히 중요하다. 경로가 다양할 경우 알파벳 순서로 앞에 오는 경로부터 선택해야 하므로 ticket[1] 에 대해서 sort를 수행한 뒤 DFS를 실행한다. 보통은 인접 리스트로 그래프를 구현하지만, 이 문제의 조건인 간선의 모든 소진을 만족하도록 직관적으로 구현했다. 처음에는 dfs 초기에 result에 현재 노드를 삽입했지만, 이는 테스트 케이스 1번과 2번에서 오답이 나온다. 위상 정렬 알고리즘처럼 맨 마지막에 result를 삽입하고 그 결과..

이 문제는 BFS를 이용하는 Level 3 문제이다. 테두리를 따라서 가는 길을 구현하는 것이 어려웠는데, 입력받은 직사각형들의 내부를 모두 1로 만들고, 그 다음에 테두리만 남겨놓고 0으로 바꾸는 방식으로 구현했다. 그 다음에는 기본적인 BFS를 수행하는데, 이 때 문제가 발생한다. 1 1 1 1 1 1 이 표현은 사실 | ㄴㄱ 」 「 | 를 표현한 것이다. 그러나 BFS 를 수행하면 저 구석을 건너뛰고 바로 직진한다. 이를 해결하기 위해서는 좌표를 2씩 곱해서 BFS를 수행하고, 그 값을 2로 나누면 된다. #include #include #include #include using namespace std; int matrix[102][102]; int visited[102][102]; int dy[..

코딩테스트 고득점 Kit DFS/BFS Level 3 단어 변환 문제이다. 이 문제는 bfs를 이용해서 푸는데, 인접 리스트와 visited 배열을 맵으로 선언하는 것이 핵심인 문제이다. 또한 begin과 words 단어들 중에서 알파벳 하나만 다른 단어들끼리 인접하다는 생각을 해야 풀 수 있는 문제이다. #include #include #include #include using namespace std; map edges; map visited; int bfs(string begin, string target) { queue q; visited[begin] = 1; q.push(begin); while (!q.empty()) { string present = q.front(); q.pop(); if (..

코딩테스트 고득점 Kit 탐욕법(Greedy) Level 1 체육복 문제이다. 이 문제는 기초적인 그리디 알고리즘 문제로, 문제에서 제시한 그대로 구현하면 정답이 나온다. #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; vector students(n + 1, 1); for (auto i : lost) { students[i]--; } for (auto i : reserve) { students[i]++; } for (int i = 1; i

코딩테스트 고득점 Kit 완전탐색 Level 2 모음사전 문제이다. 이 문제는 a,e,i,o,u 다섯 모음으로 이루어진 모음 사전에서 어떤 단어가 몇번째 단어인지 알아내는 문제이다. 완전 탐색, 백트래킹으로 모든 단어의 조합을 구하는 연산의 수는 5^5 = 3125밖에 되지 않고, 모든 단어 조합의 수 또한 5 + 25 + 125 + 625 + 3125 = 3905개밖에 안되기 때문에 전역 배열에 담기에도 충분한 크기이다. #include #include using namespace std; vector words; char alphabet[5] = {'A', 'E', 'I', 'O', 'U'}; void func(int index, string temp) { if (index == 5) { return..

코딩테스트 고득점 Kit 완전탐색 Level 2 전력망을 둘로 나누기 문제이다. 나는 처음에 이 문제를 유니온 파인드를 이용해서 풀려고 했지만 구현이 쉽지 않았다. 입력 n 이 100으로 아주 작고, 트리로 주어지므로 시간 복잡도가 100 * 100 * 100 정도로 아주 작다. 따라서 이 문제는 완전 탐색, dfs를 이용해서 풀었다. dfs가 끝날 때마다 temp++를 실행함으로써 dfs가 최종 종료했을 때 몇개의 노드가 연결되어있는지 알수 있도록 구현했다. #include #include #include #include using namespace std; int ans = INT32_MAX; vector adj; vector visited; vector result; int temp; void df..

코딩테스트 고득점 Kit 완전탐색 Level 2 피로도 문제이다. 이 문제는 완전 탐색, 백트래킹을 이용한 기초적인 문제이다. 던전이 최대 8개까지밖에 없기 때문에, k가 충분히 커서 모든 던전을 다 돌수 있다고 가정해도 8! = 40320번 밖에 되지 않는다. #include #include #include using namespace std; int result; vector visited; void func(vector& dungeons, int k, int cnt) { for (int i = 0; i < dungeons.size(); i++) { if (!visited[i] && dungeons[i][0]