꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2014 흥미로운 우선순위 큐 문제였습니다. 알고리즘은 아래와 같습니다.1. 숫자를 중복 삽입하는 것을 방지하기 위해 map을 이용합니다.2. 소수의 곱을 우선순위 큐에 입력하는데 우선순위 큐의 크기가 N을 초과하고 우선순위 큐 내 최댓값보다 현재 숫자가 더 크면 삽입하지 않습니다.-> 우선순위 큐 내 최댓값보다 현재 숫자가 작으면 현재 숫자가 더 먼저 등장하므로 우선순위 큐에 넣습니다.3. 반복문을 탈출한 뒤 우선순위 큐의 top을 출력합니다. #include #include #include #include #include #include using namespace std; const int MAX = 100; long lon..

문제 링크입니다: https://www.acmicpc.net/problem/2252 우선순위 큐 분류 문제를 풀고 싶어서 풀었던 문제였지만 사실 위상 정렬(Topological Sort) 문제였습니다. 알고리즘은 아래와 같습니다.1. 각 정점의 inDegree를 파악해줍니다.2. inDegree가 0이라는 것은 순위가 제일 높을 수 있다는 뜻이므로 큐에 미리 넣어줍니다.3. 이후로는 큐에 front와 연결되어 있는 정점의 inDegree를 업데이트하고 1번과 2번을 반복해줍니다. #include #include #include using namespace std; const int MAX = 32000 + 1; int N, M; int inDegree[MAX]; vector graph[MAX]; void..

문제 링크입니다: https://www.acmicpc.net/problem/16399 같은 학교 학우이신 Green55님(https://blog.naver.com/pasdfq/221395443305)의 도움으로 풀 수 있었던 문제였습니다.정해는 현재 보유하고 있는 기름의 양으로 갈 수 있는 주유소들 중 제일 멀리 있는 주유소에 가서 가득 채우고 움직이는 형식으로 그리디하게 접근하는 방식이라고 합니다.하지만 출제진의 의도와는 다르게 대부분의 사람들은 DP로 풀었다고 합니다. 알고리즘은 아래와 같습니다.1. 주유소의 위치가 주어진 것이 아니기 때문에 부분합으로 주유소의 위치를 저장해야합니다.2. idx 번째 주유소에서 gas만큼의 기름이 있을 때 아래와 같이 세 가지 조치를 취할 수 있습니다.i) 현재 지점..

문제 링크입니다: https://www.acmicpc.net/problem/16402 문자열 처리와 유니온 파인드 알고리즘을 이용해야 풀 수 있었던 문제였습니다.전형적인 유니온 파인드 알고리즘과 달리 집합의 root가 끊임 없이 바뀌기 때문에 parent 배열만 이용해서 집합을 표현했습니다.제국 간의 전쟁을 할 때 서로 다른 집합에 있는 나라끼리 싸우면 해당 집합의 root 즉, 종주국끼리 전쟁을 합니다.따라서, 주어진 문자열에 나와있는 그대로 전쟁하는 것이 아니기 때문에 다음과 같이 경우의 수를 나누어야합니다.i) 속국과 속국의 종주국끼리 전쟁을 할 때ii) 서로 다른 종주국끼리 전쟁을 할 때iii) 한 쪽은 종주국이고 다른 한 쪽은 다른 종주국의 속국일 때 사실 ii)와 iii)는 같은 경우라고 봐도..

문제 링크입니다: https://www.acmicpc.net/problem/16401 low는 1, high는 제일 긴 과자의 길이로 해서 이분 탐색을 통해 나누어줄 수 있는 최대 길이를 구하면 되는 문제였습니다. #include #include using namespace std; const int MAX = 1000000; int M, N; int snack[MAX]; bool possible(int len) { int cnt = 0; for (int i = 0; i = M) return true; return false; } int main(void) { ios_base::sync_with..

문제 링크입니다: https://www.acmicpc.net/problem/16400 에라토스테네스의 체를 이용하여 소수만 저장한 벡터를 구하고 해당 벡터를 이용하여 동전 DP를 적용하면 되는 문제였습니다.동전 DP가 익숙하지 않으신 분들은 백준 2293번 동전 1(https://www.acmicpc.net/problem/2293) 문제를 먼저 풀어보시는 것을 추천드립니다. #include #include #include using namespace std; const int MAX = 40000 + 1; const int MOD = 123456789; int N; int cache[MAX]; int minFactor[MAX]; vector prime; void eratosthenes(void) { mi..

문제 링크입니다: https://www.acmicpc.net/problem/16398 저는 아직 풀지 않았지만 백준에도 유사한 문제가 있는 것으로 알고 있습니다.전형적인 MST(Minimum Spanning Tree) 알고리즘 문제였고 최소 신장 트리를 구축하는데 드는 최소 비용을 Kruskal 알고리즘을 이용해서 구하면 되는 문제였습니다. #include #include #include using namespace std; const int MAX = 1000; int planet[MAX][MAX]; int parent[MAX], ranks[MAX]; //부모 찾는 함수 int findParent(int v) { if (v == parent[v]) return v; return parent[v] = f..

문제 링크입니다: https://www.acmicpc.net/problem/16397 전형적인 BFS(Breadth First Search) 알고리즘 문제였습니다.현재 2학년 스터디에서 BFS, DFS 알고리즘을 주제로 진행하고 있기 때문에 해당 문제는 주석을 상세히 달았습니다. #include #include using namespace std; const int MAX = 100000; //99999가 최대 int N, T, G; //시작점, 최대 시도 횟수, 도착점 bool visited[MAX]; int BFS(void) { queue q; //숫자, 시도 횟수 q.push({ N, 0 }); //시작하는 숫자는 N, 현재 시도횟수는 0 visited[N] = true; //N은 이미 확인한 숫자..

문제 링크입니다: https://www.acmicpc.net/problem/16396 주어진 선분들을 visited 배열에 표시해주고 표시된 길이의 합을 출력하면 되는 문제였습니다. #include using namespace std; const int MAX = 10000; bool visited[MAX][MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for (int i = 0; i > x >> y; //선분들을 표시 for (int j = x; j < y; j++) visited[j][j + 1] = true; } int result = 0; for (i..

문제 링크입니다: https://www.acmicpc.net/problem/16395 간단한 DP 문제였습니다. #include #include using namespace std; const int MAX = 30 + 1; int cache[MAX][MAX]; int comb(int n, int k) { if (n == k || k == 0) return 1; int &result = cache[n][k]; if (result != -1) return result; result = comb(n - 1, k - 1) + comb(n - 1, k); return result; } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, K; ci..