재원블로그 재원블로그

이 문제는 join과 where절 서브 쿼리를 이용해서 풀었다. where절 서브 쿼리를 사용할 때 주의할 점은 서브 쿼리가 반드시 컬럼 하나로만 이루어져야 한다는 것이다. 2개 이상의 컬럼을 select 하게 되면 오류가 발생한다. SELECT M.MEMBER_NAME, REVIEW_TEXT, DATE_FORMAT(REVIEW_DATE, '%Y-%m-%d') as REVIEW_DATE FROM MEMBER_PROFILE AS M INNER JOIN REST_REVIEW AS R ON M.MEMBER_ID = R.MEMBER_ID WHERE M.MEMBER_ID = (SELECT MEMBER_ID FROM (SELECT COUNT(MEMBER_ID) AS CNT, MEMBER_ID FROM REST_RE..

이 문제는 bfs를 이용한 문제이다. 최단 경로로 움직였을 때 1번 노드에서 가장 먼 노드의 개수를 구하는 문제로, bfs를 실행한 뒤 visited 배열에서 구하면 되는 간단한 문제이다. #include #include #include #include #include using namespace std; #define MAX 20000 vector edges[MAX + 1]; int visited[MAX + 1]; void bfs(int start) { queue q; visited[start] = 1; q.push(start); while (!q.empty()) { int present = q.front(); q.pop(); for (int i = 0; i < edges[present].size();..

이 문제는 다이나믹 프로그래밍으로 푸는 문제이다. 처음에는 (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..