재원블로그 재원블로그

이 문제는 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]

코딩테스트 고득점 Kit 완전탐색 Level 2 카펫 문제이다. 이 문제는 완전 탐색으로 푸는 문제지만, 완전 탐색을 하는 기준이 중요한 문제이다. 처음에는 가로와 세로의 길이에 대한 완전 탐색으로 풀려고 했지만, 이는 최악의 경우 5000 * 2000000 = 100억번의 연산을 할 수도 있으므로 시간 초과가 난다. 그래서 yellow의 개수를 알고 있고, 이 안에서 가로 세로 길이를 정해놓으면 자연스럽게 brown의 개수도 나오므로 이를 통해 문제를 풀었다. #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; for (int i = yellow; i >= 1; i--) { int wi..