문제https://www.acmicpc.net/problem/1328설명접근 방법만 잘 찾으면 어렵지 않은 문제라고 생각한다. 개인적으로 bottom-up 접근법보다 top-down 접근법으로 생각하는 것이 도움이 되었다. 물론 후술할 풀이는 bottom-up으로 접근하던 top-down으로 접근하던 충분히 떠올릴 수 있는 풀이이다. 단, 높이가 N인 빌딩보다 1인 빌딩을 움직이는 것이 도움이 될 것이다.N개의 빌딩이 랜덤하게 배치되었다고 가정하자. 왼쪽에서 봤을 때 빌딩의 수를 L, 오른쪽에서 봤을 때 빌딩의 수를 R이라고 하자. 이제 높이가 1인 빌딩을 제외하자. N은 N - 1이 될 것이며, L, R은 높이가 1인 빌딩에 기존에 어디에 있었는지에 따라 달라진다.높이가 1인 빌딩이 가장 왼쪽에 위치했..

문제https://www.acmicpc.net/problem/3665설명 위상 정렬 알고리즘을 사용해야 하며, 각 팀의 순위에 대한 선후 관계를 어떻게 관리할지, 상대적인 등수가 바뀐 팀들을 어떻게 처리할지, 확실한 순위를 찾을 수 없거나 순위를 하나로 정하지 못하는 경우는 어떤 경우인지 고려해야 한다.  첫 번째 예제를 통해 살펴보자. 팀의 수 n은 5이고, 작년 팀의 순위는 5, 4, 3, 2, 1이다. 한 번 팀의 관계를 그래프로 나타내보자.  위와 같이 팀의 관계를 그래프로 표현하였다. a->b는 a 팀이 b 팀보다 순위가 더 높다는 것을 의미한다. 첫 번째 예제에서 상대적인 등수가 바뀐 팀들은 (2, 4), (3, 4)이다. 먼저 단순히 두 팀의 위치 관계를 바꿔보는 것으로 생각해보자.  2번 ..

문제https://www.acmicpc.net/problem/1194설명 전형적인 BFS 문제이나, 고려할 점이 많다. 미로에는 벽이 존재하며, 이 곳에는 이동할 수 없다. 추가로 열쇠와 문도 존재하는데, 열쇠는 소문자, 문은 대문자로 표시된다. 열쇠와 대응하는 문에 도달하면 지나갈 수 있다. 예를 들어 'a'를 가지고 있으면 'A'로 이동할 수 있다. 열쇠는 'a'부터 'f'까지 존재하며, 문 또한 'A'부터 'F'까지 존재한다. 시작 좌표는 0, 도착 좌표는 1로 표시된다. 1은 최소 한 개 존재하며, 여러 개 존재할 수 있다. visited 배열에 이동 횟수까지 기록하여 구현할 예정이다. 단순히 이차원 배열로 visited를 선언해도 될까? 그렇지 않다. 열쇠를 얻기 위해 중복 좌표를 방문해야 할 ..

문제https://www.acmicpc.net/problem/1640설명 N * M 크기로 동전을 배치한다. 앞면을 0, 뒷면을 1이라고 할 때, 행 또는 열에 있는 동전들을 뒤집어서 행과 열에 위치한 모든 동전의 뒷면(1)의 개수를 짝수로 바꾸는 최소 횟수를 구하는 문제이다. 처음에는 무슨 알고리즘을 써야 할지 감이 안 잡혔는데, 역시 애드 혹 문제였다.코드더보기#include #include #include using namespace std;int col[1001];int row[1001];// 1. 행 또는 열을 짝수 또는 홀수로 통일한다.// 2. 홀수 개로 통일한 경우 다른 행 또는 열의 짝수 개를 뒤집는다.// 3. 짝수 개로 통일한 경우 그 반대int main() { int n, m; ci..

문제https://www.acmicpc.net/problem/10800설명  공이 다른 공을 사로잡을 수 있다. 사로잡기 위한 조건은 색이 다르거나, 크기가 더 작을때이다. 공에 대한 정보를 배열에 저장하고 브루트포스로 일일히 계산하게 되면 $O(N^2)$로 시간 초과가 발생하게 된다. 정렬과 누적 합 개념을 사용해야 한다. 공에 대한 정보를 저장하는 구조체 Ball을 선언한다. 공의 색, 크기, 인덱스 정보를 기록한다. 그 다음 공을 크기 순으로 오름차순 정렬한다. 크기가 같다면 색을 기준으로 정렬한다. 중복된 공이 들어올 수 있으며, 이에 대한 처리를 효율적으로 하기 위함이다. 정렬된 배열에 접근하면서 공이 사로잡을 수 있는 크기를 효율적으로 구한다. 이때 누적 합 개념이 사용된다.코드더보기#incl..

문제https://www.acmicpc.net/problem/1103설명 전형적인 그래프 탐색 문제이지만, 사이클이 발생한 경우를 탐지해야 하므로 BFS 대신 DFS를 사용하는 것이 효율적이다. 그러나 단순히 DFS를 수행하며 동전이 움직일 수 있는 최대 횟수를 구하려고 하면 시간 초과가 발생하게 된다. 이미 방문한 지점인 경우, 추가적인 탐색을 진행하면 안 된다. 따라서 DP 배열을 추가로 선언해야 한다.코드더보기#include #include using namespace std;int ans = 0;bool cycleFlag = false;int n, m;int board[50][50];int visited[50][50];int cnt[50][50];int dx[4] = { -1,0,1,0 };int..

문제https://www.acmicpc.net/problem/5015설명 단순히 문자열 관련 알고리즘을 사용해야하는 줄 알았는데, DP와 재귀를 사용하는 문제였다. 패턴 pattern과 문자열 s를 입력받고 pattern의 pidx번 째 인덱스와 s의 sidx번 째 인덱스끼리의 문자열을 비교해서 매칭된다면 1, 아니면 0을 리턴하는 함수 solve()를 선언하였다.코드더보기#include #include using namespace std;int dp[101][101];string pattern;string s;// dp의 초기값을 -1로 설정void init() { for (int i = 0; i = pattern.length()) return 0; // 현재 패턴의 문자가 *가 아닌데 s가 끝난 경..

문제https://www.acmicpc.net/problem/1621설명 원숭이가 N개의 바나나를 가져간다. 두 가지 선택지가 있는데, 바나나 하나만 가져가거나 K개를 한꺼번에 가져가는 방법이 있다. 하나만 가져가는 경우 바나의 무게만큼 시간이 걸리며 K개를 한꺼번에 가져가면 C의 시간이 걸린다. 원숭이가 바나나를 모두 옮기는 데 걸리는 최소 시간과 한꺼번에 옮기는 행위의 횟수, K개 묶음의 왼쪽 위치를 오름차순으로 출력해야 한다. 답이 여러 개인 경우 한꺼번에 옮기는 행위가 최소가 되는 상황을 선택해야 한다.  N개의 바나나를 옮기는 데 최소 시간을 구해야 하므로 DP를 사용한다. 또한 K개 묶음의 왼쪽 위치를 출력해야 하므로 이를 역추적하는 배열(route) 또한 추가로 필요하다.  dp 배열은 현재..

문제https://www.acmicpc.net/problem/1753설명가장 대표적인 다익스트라 문제이다. 우선순위 큐를 통해 구현하였다.코드더보기더보기#include #include #include #define INF 300001using namespace std;int main() { int v, e, k; cin >> v >> e >> k; vector> nodes[20001]; // {도착 노드, 가중치} for (int i = 0;i > x >> y >> w; nodes[x].push_back({ y,w }); } vector cost(v + 1); for (int i = 1;i , vector>, greater>> pq; pq.push({ 0, k }); while (!pq.empty())..

문제https://www.acmicpc.net/problem/2533설명DFS로 트리를 순회하며 가능한 얼리 어답터의 수를 구하는 문제이다. 최소 얼리 어답터의 수를 구하기 위해 DP를 사용한다. 먼저 노드 연결 관계를 vector 배열 nodes에 저장한다. DFS로 순회하며 DP 배열을 초기화한다. 사용할 DP 배열은 이차원 배열이다. dp[i][j]는 i번 째 노드가 얼리 어답터(j == 1) 또는 얼리 어답터가 아닐 때(j == 0) 가능한 최소 얼리 어답터의 수이다. 현재 참조하는 노드를 node, 자식 노드를 child라고 할 때 child의 DFS 순회를 마치고 node에 대한 DP배열을 초기화한다. node가 얼리 어답터가 아닐 때 자식 노드는 무조건 얼리 어답터여야 한다. 즉, dp[no..