[백준 5849] Cow Crossings
문제 https://www.acmicpc.net/problem/5849 알고리즘 stack 풀이 inversion을 만들지 않는 소의 개수를 구하는 문제입니다. $a_i$를 u, $b_i$를 v라고 하겠습니다. inversion을 만들지 않기 위해서는 u를 기준으로 정렬했을 때, v가 오름차순의 형태를 가져야만합니다. 오름차순을 유지하기 위해 스택을 사용해서 문제를 풀면 됩니다. 스택의 top이 현재 보고 있는 소의 v보다 크다면 이는 inversion을 만들기 때문에 계속 pop을 해주고, 지금까지 확인한 v값들보다 현재 v값이 작다면 현재 v는 inversion을 만들지 않으므로 스택에 push 해주면 됩니다. 아래 코드는 이 해설과는 다른 코드입니다. 풀이만 참고하세요. 코드 #include #de..
Algorithm
2021. 7. 22. 14:45
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 동적계획법
- SCC
- 트라이
- implementation
- Suffix Array
- dijkstra
- string
- 정렬
- 펜윅트리
- 세그먼트트리
- kmp
- bfs
- union find
- 이분탐색
- 이분매칭
- spring boot
- DP
- 2-SAT
- knapsack
- greedy
- sorting
- Fenwick
- 스위핑
- spring
- Segment tree
- Oracle
- sweeping
- dfs
- 좌표압축
- hld
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함