[백준 5859] 거짓말쟁이
문제 https://www.acmicpc.net/problem/5859 알고리즘 Union Find 풀이 쿼리를 순서대로 반영했을 때, 모순이 일어나지 않는 최대 갯수를 구하는 문제입니다. 유니온 파인드에서 종종 보이는 유형입니다. 하나의 사람을 두 가지 타입으로 나눕니다. $u$에 대해 참말을 하는 T(u)와 거짓말을 하는 F(u)로 나눕니다. 이에 따라 가능한 경우의 수를 묶고 모순이 발생하는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i > u >> v >> x; if (x == 'T') { uni(T(u), T(v)); u..
Algorithm
2021. 8. 22. 11:42
[백준 8895] 막대 배치
문제 https://www.acmicpc.net/problem/8895 알고리즘 DP 풀이 서로 다른 $N$개의 막대를 좌우로 쌓을 때, 옆에서 보이는 l, r의 경우의 수를 구하는 문제입니다. $cache[n][l][r]$을 선언하여 풀되, 다음 상태(n+1)를 갱신할 때는 기존 막대의 크기를 1씩 키우고 가장 작은 막대(높이 1)를 추가하는 것으로 생각하여 풀면 쉽게 풀 수 있습니다. 막대를 가장 왼쪽, 오른쪽에 배치하는 것은 직관적이나 막대를 막대들 사이에 넣을 때 가장 작은 막대를 추가한다면 기존 상태 $cache[n][l][r]$에서 $cache[n+1][l][r]$ 만 갱신하기 때문에 신경쓸 것이 적어집니다. 코드 #include #define rep(i, n) for (int i = 0; i..
Algorithm
2021. 8. 22. 10:14
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 세그먼트트리
- 동적계획법
- hld
- SCC
- spring boot
- Fenwick
- knapsack
- Oracle
- sorting
- dijkstra
- sweeping
- string
- 스위핑
- 트라이
- Suffix Array
- implementation
- bfs
- 이분탐색
- spring
- greedy
- 펜윅트리
- DP
- dfs
- kmp
- union find
- 이분매칭
- 좌표압축
- 2-SAT
- Segment tree
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함