문제 www.acmicpc.net/problem/20968 알고리즘 Dijkstra 풀이 소의 품종마다 서로 연락할 수 있는 관계가 주어졌을 때, 첫 번째 소가 맨 마지막 소에게 메시지를 전달하기 위한 최솟값을 구하는 문제입니다. 일반적으로 PQ를 이용한 다익스트라의 시간복잡도는 $O(ElogV)$입니다. 문제에서 $N$제한이 50000이므로 무작정 다익스트라를 사용하게 되면 시간 초과를 받게 됩니다. 빨간색 원이 현재 PQ에서 꺼낸 소라고 하겠습니다. 녹색은 빨간색 품종이 연락할 수 있는 품종을 의미합니다. 만일 위와 같이 녹색품종들이 모두 빨간색에서 메시지를 받을 수 있다면 굳이 첫 번째를 제외한 2, 3, 4번째들을 검사할 필요는 없습니다. 즉 현재 소에서 연락 가능한 품종들마다 가장 가까이 있는 ..
문제 www.acmicpc.net/problem/3015 알고리즘 stack 풀이 $N$명이 사람이 서있을 때, 서로 볼 수 있는 쌍을 구하는 문제입니다. 서로 보기 위해선 각 사람 사이에 그 사람들보다 큰 키가 존재해서는 안됩니다. 문제의 단순화를 위해 모든 키가 유니크하다고 가정하겠습니다. 파악해야할 것은 키의 구간이 내림차순으로 존재한다면 해당 구간은 추후에 매칭이 될 가능성이 있는 사람들입니다. 아래 그림은 이에 대한 예시로써, 흰색사람의 키가 내림차순인 형태입니다. 이후에 나오는 주황색 사각형과 흰색 사각형들이 매칭이 됩니다. 또한 빨간색 사각형처럼 자신의 왼쪽에 있는 사람이 자신보다 키가 크다면 무슨일이 있어도 주황색 사각형의 왼쪽부분과는 매칭이 될 수 없습니다. 이러한 특징을 파악해 오름차순..
- Total
- Today
- Yesterday
- 이분매칭
- implementation
- dijkstra
- 이분탐색
- Segment tree
- SCC
- sorting
- spring boot
- union find
- 세그먼트트리
- 2-SAT
- spring
- string
- dfs
- kmp
- Fenwick
- 트라이
- greedy
- Suffix Array
- knapsack
- 동적계획법
- sweeping
- Oracle
- 정렬
- 펜윅트리
- hld
- bfs
- DP
- 좌표압축
- 스위핑
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |