[백준 3015] 오아시스 재결합
문제 www.acmicpc.net/problem/3015 알고리즘 stack 풀이 $N$명이 사람이 서있을 때, 서로 볼 수 있는 쌍을 구하는 문제입니다. 서로 보기 위해선 각 사람 사이에 그 사람들보다 큰 키가 존재해서는 안됩니다. 문제의 단순화를 위해 모든 키가 유니크하다고 가정하겠습니다. 파악해야할 것은 키의 구간이 내림차순으로 존재한다면 해당 구간은 추후에 매칭이 될 가능성이 있는 사람들입니다. 아래 그림은 이에 대한 예시로써, 흰색사람의 키가 내림차순인 형태입니다. 이후에 나오는 주황색 사각형과 흰색 사각형들이 매칭이 됩니다. 또한 빨간색 사각형처럼 자신의 왼쪽에 있는 사람이 자신보다 키가 크다면 무슨일이 있어도 주황색 사각형의 왼쪽부분과는 매칭이 될 수 없습니다. 이러한 특징을 파악해 오름차순..
Algorithm
2021. 5. 5. 13:54
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- string
- 트라이
- spring
- 동적계획법
- union find
- DP
- spring boot
- implementation
- kmp
- Fenwick
- bfs
- 정렬
- dfs
- hld
- knapsack
- sorting
- greedy
- dijkstra
- 좌표압축
- Suffix Array
- sweeping
- 이분매칭
- SCC
- Segment tree
- Oracle
- 세그먼트트리
- 이분탐색
- 펜윅트리
- 스위핑
- 2-SAT
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함