문제 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..
문제 www.acmicpc.net/problem/20968 알고리즘 Dijkstra 풀이 소의 품종마다 서로 연락할 수 있는 관계가 주어졌을 때, 첫 번째 소가 맨 마지막 소에게 메시지를 전달하기 위한 최솟값을 구하는 문제입니다. 일반적으로 PQ를 이용한 다익스트라의 시간복잡도는 $O(ElogV)$입니다. 문제에서 $N$제한이 50000이므로 무작정 다익스트라를 사용하게 되면 시간 초과를 받게 됩니다. 빨간색 원이 현재 PQ에서 꺼낸 소라고 하겠습니다. 녹색은 빨간색 품종이 연락할 수 있는 품종을 의미합니다. 만일 위와 같이 녹색품종들이 모두 빨간색에서 메시지를 받을 수 있다면 굳이 첫 번째를 제외한 2, 3, 4번째들을 검사할 필요는 없습니다. 즉 현재 소에서 연락 가능한 품종들마다 가장 가까이 있는 ..
문제 www.acmicpc.net/problem/3015 알고리즘 stack 풀이 $N$명이 사람이 서있을 때, 서로 볼 수 있는 쌍을 구하는 문제입니다. 서로 보기 위해선 각 사람 사이에 그 사람들보다 큰 키가 존재해서는 안됩니다. 문제의 단순화를 위해 모든 키가 유니크하다고 가정하겠습니다. 파악해야할 것은 키의 구간이 내림차순으로 존재한다면 해당 구간은 추후에 매칭이 될 가능성이 있는 사람들입니다. 아래 그림은 이에 대한 예시로써, 흰색사람의 키가 내림차순인 형태입니다. 이후에 나오는 주황색 사각형과 흰색 사각형들이 매칭이 됩니다. 또한 빨간색 사각형처럼 자신의 왼쪽에 있는 사람이 자신보다 키가 크다면 무슨일이 있어도 주황색 사각형의 왼쪽부분과는 매칭이 될 수 없습니다. 이러한 특징을 파악해 오름차순..
문제 www.acmicpc.net/problem/20971 알고리즘 DP 풀이 특정 구간을 칠하지 않은 상태로 할 때, 남은 구간들을 칠하기 위한 최솟값을 구하는 문제입니다. 문제의 가장 큰 특징은 페인트를 칠하는 순서가 정해져 있다는 것입니다. 이를 유의하며 풀도록 합시다. 쿼리를 빠르게 처리하기 위해 DP 아이디어를 떠올렸습니다. 특정 구간에 대한 DP를 사용하기 위해선 $cache[i][j]$와 같은 배열을 사용할 수 있는데, 구간의 길이가 100,000 이라는 점에서 해당 2차원 배열을 사용하기는 어렵습니다. 하지만 문제를 자세히 보면 특정 구간을 칠하기 위한 최솟값이 아닌 특정 구간을 제외한 나머지 구간을 칠하기 위한 최솟값을 묻고 있습니다. 이는 DP의 정의가 "앞에서부터 길이 $N$인 구간을..
문제 www.acmicpc.net/problem/18320 알고리즘 이분탐색 풀이 갚을 금액, 기한, 하루에 최소 갚을 금액이 주어졌을 때, 조건을 충족하는 $X$를 구하는 문제입니다. 문제를 풀기 위한 첫 번째 단계는 $X$를 결정해야하는 것입니다. 결정문제는 이분탐색으로 바꿀 수 있습니다. 이 문제가 어려운 이유는 $X$를 결정했을 때, 그대로 시뮬레이션하여 $K$일 이내에 돈을 갚을 수 있는지 계산하게 되면 시간초과가 발생하기 때문입니다. 이유는 $N$제한이 $10^{12}$이기 때문입니다. $X$를 결정하는 시간복잡도는 $O(logN)$에 해당하는데 그대로 시뮬레이션 하게 되면 $X$마다 선형시간이 요구되기 때문입니다. 한가지 할 수 있는 관찰 중 하나는 John이 갚아나가는 금액은 비오름차순의 ..
문제 www.acmicpc.net/problem/9376 알고리즘 01BFS 풀이 한 사람이 두 죄수를 탈옥시키기 위한 최소 문의 수를 구하는 문제입니다. 3인 통화문제와 마찬가지로 세 사람의 위치를 구한 후 다익스트라를 세번 사용하면 풀 수 있는 문제입니다. 죄수의 위치는 주어지지만 구출하는 사람의 위치는 주어지지 않습니다. 주어지는 공간(N X M)을 테두리를 확장하여 (N+2 X M+2)로 만듭니다. 이렇게하면 구출하는 사람의 위치를 임의로 (0,0)으로 설정해도 됩니다. BFS는 이동에 사용하는 값이 모두 동일할 때, queue를 사용해서 원하는 목표까지의 거리를 구하게 됩니다. 다익스트라는 이동에 사용하는 값이 다를 때 사용하는데, 가중치가 0과 1로만 주어져 있을 때는 다익스트라보다 더 빠르게..
- Total
- Today
- Yesterday
- string
- 동적계획법
- sorting
- Oracle
- 트라이
- 2-SAT
- implementation
- 이분매칭
- 스위핑
- 좌표압축
- 정렬
- dijkstra
- spring
- DP
- 펜윅트리
- Suffix Array
- SCC
- Fenwick
- 세그먼트트리
- dfs
- 이분탐색
- greedy
- knapsack
- kmp
- union find
- spring boot
- hld
- Segment tree
- sweeping
- bfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |