[백준/C++] 7662번: 이중 우선순위 큐
2022. 11. 16. 15:59
문제 풀이/백준
문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. ..
[백준/C++] 1436번: 영화감독 숌
2022. 2. 28. 10:56
문제 풀이/백준
문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..
[알고리즘 문제] 76. 이항계수(메모이제이션)
2020. 10. 27. 18:33
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int dy[21][21]; int DFS(int n, int r) { if (dy[n][r] > 0) return dy[n][r]; if (r == 0 || n == r) return 1; else return dy[n][r] = DFS(n - 1, r) + DFS(n - 1, r - 1); } int main(void) { int n, r; cin >> n >> r; cout
[알고리즘 문제] 75. 최대 수입 스케쥴(priority_queue 응용문제)
2020. 10. 26. 22:26
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; struct Data { int money; int when; Data(int a, int b) : money(a), when(b) {} bool operator b.when; } }; int main(void) { int n, m, d, i, j, res = 0, max = -2147000000; vector T; priority_queue pQ; cin >> n; for (i = 0; i > m >> d; T.emplace_back(Data(m, d)); if (d > max) max = d; } sort(T.begin(), T.e..
[알고리즘 문제] 74. 최소힙(priority_queue : 우선순위 큐)
2020. 10. 25. 22:18
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int input; priority_queue PQ; while (true) { cin >> input; if (input == -1) break; else if (input == 0) { if (PQ.empty()) cout
[알고리즘 문제] 73. 최대힙(priority_queue : 우선순위 큐)
2020. 10. 25. 21:53
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int input; priority_queue PQ; while (true) { cin >> input; if (input == -1) break; else if (input == 0) { if (PQ.empty()) cout
[알고리즘 문제] 72. 공주 구하기(큐 자료구조로 해결)
2020. 10. 25. 21:41
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int main(void) { int n, k, i; cin >> n >> k; queue Q; for (i = 1; i
[알고리즘 문제] 71. 송아지 찾기(BFS : 상태트리탐색)
2020. 10. 23. 23:48
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int ch[10001], d[3] = { -1, 1, 5 }; int main(void) { int s, e, x, pos, i; cin >> s >> e; queue Q; ch[s] = 1; Q.push(s); while (!Q.empty()) { x = Q.front(); Q.pop(); for (int i = 0; i < 3; ++i) { pos = x + d[i]; if(pos 10000) continue; if (pos == e) { // 출발 지점을 1로 잡았기 때문에 이전 지점 출력 cout
[알고리즘 문제] 70. 그래프 최단거리(BFS)
2020. 10. 21. 20:34
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int ch[21], dis[21]; int main(void) { int n, m, i, a, b, x; vector map[21]; queue Q; cin >> n >> m; for (i = 1; i > a >> b; map[a].push_back(b); map[b].push_back(a); } Q.push(1); ch[1] = 1; while (!Q.empty()) { x = Q.front(); Q.pop(); for (i = 0; i < map[x].size(); ++i) { if (ch[map[x][i]] == 0) { ch[map[x][i]] = 1; Q.push(map[x][i]); dis[map[x]..
[알고리즘 문제] 69. 이진트리 넓이우선탐색(BFS)
2020. 10. 20. 12:30
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int Q[100], front = -1, back = -1, ch[10]; vector map[10]; int main(void) { int i, a, b, x; for (i = 1; i > a >> b; map[a].push_back(b); map[b].push_back(a); } Q[++back] = 1; ch[1] = 1; while (front < back) { x = Q[++front]; cout
[알고리즘 문제] 68. 최소비용(DFS : 가중치 방향그래프 인접리스트)
2020. 10. 20. 12:18
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int n, cost = 2147000000; int ch[21]; vector map[21]; void DFS(int v, int sum) { if (v == n) { if (cost > sum) cost = sum; } else { for (int i = 0; i > n >..
[알고리즘 문제] 67. 최소비용(DFS : 인접행렬)
2020. 10. 19. 14:57
문제 풀이/알고리즘 문제풀이
코드 #include #include using namespace std; int arr[21][21]; int ch[21]; int n, min = 2147000000; void DFS(int v, int sum) { int i; if (v == n) { if (sum > n >> m; for (i = 0; i > a >> b; cin >> arr[a][b]; } ch[1] = 1; DFS(1, 0); ..
[알고리즘 문제] 66. 경로 탐색(DFS : 인접리스트 방법)
2020. 10. 19. 14:40
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int n, cnt = 0; int map[21][21]; int ch[21]; void DFS(int L) { int i; if (L == n) { ++cnt; } else { for (i = 1; i > n >> m; for (i = 1; i > a >> b; map[a][b] = 1; } ch[1] = 1; DFS(1); cout n >> m; for (i = 0; i > a >> b; map[a].push_back(b); } ch[1] = 1; DFS(1); cout
[알고리즘 문제] 65. 미로탐색(DFS)
2020. 10. 19. 14:33
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int arr[8][8], ch[8][8]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; int cnt = 0; void DFS(int x, int y) { int i, xx, yy; if (x == 7 && y == 7) { ++cnt; } else { for (i = 0; i 7 || yy 7) continue; if (arr[xx][yy] == 0 && ch[xx][yy] == 0) { ch[xx][yy] = 1; DFS..
[알고리즘 문제] 64. 경로 탐색(DFS)
2020. 10. 18. 23:45
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int n, cnt = 0; int map[21][21]; int ch[21]; void DFS(int v) { // 종료 지점이라면 if (v == n) { cnt++; } else { for (int i = 1; i > n >> m; int p1, p2; for (int i = 1; i > p1 >> p2; map[p1][p2] = 1; } ch[1] = 1; DFS(1); cout
[알고리즘 문제] 63. 인접행렬(가중치 방향그래프)
2020. 10. 16. 13:25
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; int map[21][21]; int main(void) { int n, m; cin >> n >> m; int p1, p2, p3; for (int i = 1; i > p1 >> p2 >> p3; map[p1][p2] = p3; } for (int i = 1; i
[알고리즘 문제] 62. 병합정렬
2020. 10. 16. 13:11
문제 풀이/알고리즘 문제풀이
코드 #include #include #include using namespace std; vector vInt; vector vTemp; void divide(int left, int right) { int mid; int p1, p2, p3; if (left < right) { mid = (left + right) / 2; divide(left, mid); divide(mid + 1, right); p1 = left; p2 = mid + 1; p3 = left; while (p1