문제 https://www.acmicpc.net/problem/5909 알고리즘 DP 풀이 주어진 건초더미를 세 개 공평하게 나누는 문제입니다. 이 문제와 매우 매우 유사합니다. $cache[k][i][j]$를 k번째 건초더미까지 분배했을때 i가 B_1, j가 B_2라고 해석하여 가능하다면 1, 불가능하다면 0을 저장하여 풀면 됩니다. 나머지 세 번째 곳간에 저장될 양은 $psum-i-j$를 통해 알아 낼 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { cin >> arr[i]; sum += arr[i]; } cache[0][0][0] = 1..
문제 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..
문제 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..
문제 https://www.acmicpc.net/problem/1856 알고리즘 DP 풀이 주어진 문자열을 단어 리스트를 조합하여 만들기 위한 최소 제거 횟수를 묻는 문제입니다. 2차원 배열의 구간DP를 선언하여 $i~j$까지 만들기 위한 최소 제거 횟수를 구하여 풀었지만 2차원 배열 대신 1차원 배열로도 풀 수 있습니다. 주어진 단어 w를 사용할 때, 중간에 끊는 것 없이 한번 사용하면 무조건 끝까지 매칭하여야 하기 때문입니다. cache[i] = 문자열 S의 $i$번째까지 만들기 위한 최소 제거 횟수 주어진 단어 w를 전부 매칭했다면 (idx값이 -1) 제거한 문자 수를 계산하여 cache값을 업데이트하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i ..
문제 https://www.acmicpc.net/problem/20366 알고리즘 정렬 풀이 서로 다른 네 수를 뽑아 두 개씩 짝지었을 때, 차이를 최소화 하는 문제입니다. NC2를 통해 가능한 조합을 뽑고 나서 인덱스들이 가리키는 수들의 합을 기준으로 정렬한 후 풀면 됩니다. 정렬된 배열(벡터)에서 각 수의 조합이 서로 다른 인덱스로 이루어졌는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x; cin >> x; vt.emplace_back(x); } for (int i = 0; i < vt.size() - 1; ++i) { ..
문제 https://www.acmicpc.net/problem/1398 알고리즘 DP, Greedy 풀이 최소 동전의 수를 묻는 문제입니다. 주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다. (1 10 25), (100 1000 2500), (10000 100000 ...) 즉 DP를 100씩 끊어서 사용하면 됩니다. 코드 #include ..
문제 https://www.acmicpc.net/problem/5900 알고리즘 DP 풀이 1비트를 k개 사용했을 때, n번째 비트를 구하는 문제입니다. 일단 n번째 비트의 자릿수 먼저 구해야 합니다. 만약 자릿수가 5이고 사용한 k가 3일 때 5자리로 나타낼 수 있는 가짓수는 4C2입니다. 왜냐하면 맨 처음 1은 무조건 나와야 하기 때문입니다. 그렇다면 자릿수를 구하기 위해서는 2C2 + 3C2 + 4C2.. 와같이 세 자리에서 k 3개일 때 경우의 수 + 네 자리에서 k 3개 일 때 경우의 수 + 다섯 자리에서 k 3개일 때의 경우의 수처럼 앞에서부터의 누적합을 구해야 nth가 몇 번째 자릿수인지 구할 수 있습니다. 하지만 굳이 누적합을 구하지 않더라도 이미 누적합이 구해져 있습니다. 5C3은 2C2..
- Total
- Today
- Yesterday
- spring boot
- union find
- 펜윅트리
- Fenwick
- bfs
- 정렬
- Segment tree
- 이분매칭
- 동적계획법
- sweeping
- 세그먼트트리
- implementation
- DP
- 좌표압축
- 스위핑
- sorting
- Suffix Array
- SCC
- spring
- greedy
- 2-SAT
- dijkstra
- Oracle
- 이분탐색
- knapsack
- kmp
- hld
- 트라이
- string
- dfs
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |