문제 https://www.acmicpc.net/problem/5917 알고리즘 Dijkstra 풀이 최단거리 중 하나의 간선의 값을 두배로 하였을 때의 최댓값을 구하는 문제입니다. 다익스트라임은 최단거리임을 보고 알 수 있습니다. 문제 제한은 $N$이 100 이하, $M$은 10000 이하입니다. 단순한 접근으로는 $M$의 간선들을 하나씩 두배로 만든 후 그때마다 새로이 다익스트라를 사용하는 것입니다. 하지만 $M$제한이 10000이므로 이 방법은 무리가 있습니다. 이 방법에는 불필요한 부분이 있습니다. 바로 최단거리에 포함되지 않는 간선들 또한 두 배로 바꾸는 것입니다. 이는 아무런 의미가 없는 행동입니다. $N$개로 이루어진 노드에서 최단거리는 최대 $N-1$개의 간선을 통해 이루어져 있습니다. 즉..
문제 https://www.acmicpc.net/problem/17612 알고리즘 Priority queue 풀이 문제에서 정의한 계산 순서를 구하는 문제입니다. 우선순위 큐를 이용한 구현문제에 가깝습니다. 빈 계산대가 여러 개 있다면 번호가 작은 계산대부터 계산해야 하므로 빈 계산대를 저장하는 $counter$변수, $info$ 클래스를 정의하여 각 아이디와 계산시간 및 카운터 정보를 기록하고 해당 클래스 객체의 우선순위를 위한 $compareInfo$ 클래스를 정의합니다. 다만, 우선순위큐를 통해 카운터에서 계산될 순서를 저장하게 될 때, 가장 빠르게 계산이 끝나는 $info$ 객체를 우선순위 큐에서 뽑았다면, 나머지 우선순위 큐 안에 있는 $info$ 객체의 $time$ 변수 또한 업데이트를 모두 ..
문제 https://www.acmicpc.net/problem/10652 알고리즘 Dijkstra, BFS 풀이 Bessie와 Elsie가 돌아다닐때 드는 에너지와 Piggy Back 상태에서 드는 에너지가 주어졌을 때, $N$까지 도달하기 위한 최소에너지는 구하는 문제입니다. 3인통화 문제와 굉장히 유사합니다. 도착지도 하나의 소처럼 취급을 하여 세 마리의 소에서 각각 다익스트라를 사용하면 문제가 해결됩니다. 다만, 각 소마다 그래프를 이동할 때 드는 비용은 동일하므로 다익스트라 대신 BFS를 사용하면 더 빠르게 문제를 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i..
문제 https://www.acmicpc.net/problem/9869 알고리즘 Greedy 풀이 소마다 우유생산량과 수명이 주어질 때, 최대 우유생산량을 구하는 문제입니다. 자주 보이는 그리디 테크닉입니다. 시간을 0부터 접근하는 대신, 가장 마지막 시간부터 0까지 역순으로 소들을 고려합니다. T에 해당하는 시간에 젖을 짤 수 있는 소들을 PQ에 넣습니다. 이렇게 하면 현재 젖을 짤 수 있는 소들이 PQ에 담기게 됩니다. 이 가운데 우유 생산량이 높은 소부터 젖을 짜나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; vector vt; rep(i, N) { int..
문제 https://www.acmicpc.net/problem/18785 알고리즘 DFS 풀이 Bessie가 트리위에 주어진 맵을 이동해가며 시계를 조정할 때, 모든 시계가 가르키는 시간이 12시가 되도록 할수 있는 방의 시작갯수를 구하는 문제입니다. 임의의 출발지에서 모든 노드가 12가 될 수 있는지를 확인하는 것이 목표입니다. $N$제한이 2500이므로 $O(N^2)$에 근접하는 알고리즘을 떠올려봅시다. 첫 번째로는 리프노드의 시간을 12시로 맞추기 위해서는 무조건 리프노드와 리프노드의 부모를 계속해서 왔다갔다 해야지만 리프노드를 원하는 숫자 12로 맞출 수 있습니다. 12로 설정된 리프노드는 우리의 관심사 밖이므로 제거되고 리프노드의 부모였던 노드는 새로운 리프노드가 됩니다. 위 시뮬레이션을 계속 ..
문제 https://www.acmicpc.net/problem/20970 알고리즘 Graph 풀이 $N$마리의 소가 $K$번 자리를 바꾸는 것을 계속 반복할 때, 각 소가 차지했던 위치의 수를 구하는 문제입니다. $K$번 자리를 바꾸는 것을 한 사이클이라고 하겠습니다. 하나의 사이클을 반복하면 아래와 같은 결과를 얻을 수 있습니다. 1번째 있는 소는 3, 3, 2 번째를 들른 후 한 사이클이 끝나면 4번째에 있는 곳에 위치하게 됩니다. 아래 2,3,4,5 번째 소들도 마찬가지로 그림을 해석하면 됩니다. 이 사이클을 계속 반복했을 때 원래 자리로 돌아오도록 시뮬레이션하면 답을 구할 수 있습니다. 아래 사진은 1번째소를 시뮬레이션한 결과입니다. 파란색 원들이 각각 시작점과 끝점입니다. 그 사이에 들렀던 노란..
문제 https://www.acmicpc.net/problem/20649 알고리즘 DP, Sorting 풀이 x, y 좌표가 모두 다른 소들의 좌표가 주어졌을 때, 각 소들의 잘못 점수(?)를 구하는 문제입니다. 문제를 관찰하면 동쪽으로 이동하는 소들 $A$는 북쪽으로 이동하는 소들 $B$중에서 $A$보다 오른쪽에 있으면서 아래 있는 소들에게 막히는지 안 막히는지 확인해야 하고 반대로 $B$는 $B$보다 왼쪽에 있으면서 위에 있는 소들에게 막히는지 안 막히는지 확인해야 합니다. 그래프가 DAG의 형태를 띠는 것에서 DP를 착안합시다. 이차원 포문을 통해 모든 소들의 쌍을 검사하며 각 소들의 관계를 따져보도록 합시다. 하지만 소들을 정렬하지 않은 채 무작정 이차원 포문을 통해 각 소들의 관계를 따지게 되면..
문제 www.acmicpc.net/problem/6068 알고리즘 Greedy 풀이 일을 처리하는데 걸리는 시간, 일의 마감기한이 주어졌을 때 일을 시작해야하는 가장 늦은 시간을 구하는 문제입니다. 일을 마감기한에 딱 맞춰서 끝내는 것이 일을 가장 늦게 시작할 수 있을 것입니다. 마감기한이 가장 늦은 일부터 마감시간에 딱 맞게 일을 역순으로 처리해나가며 현재시간과 다음으로 처리해야할 일의 마감기한중 작은 값을 현재시간으로 취해나가며 시뮬레이션 하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int a, b; cin >> a >> b; vt.e..
- Total
- Today
- Yesterday
- sweeping
- 펜윅트리
- 좌표압축
- 스위핑
- knapsack
- SCC
- Suffix Array
- 트라이
- 정렬
- kmp
- string
- sorting
- union find
- spring
- 이분탐색
- 이분매칭
- hld
- dijkstra
- spring boot
- Fenwick
- bfs
- implementation
- 동적계획법
- Segment tree
- 2-SAT
- DP
- greedy
- 세그먼트트리
- Oracle
- dfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |