문제 www.acmicpc.net/problem/11963 알고리즘 greedy 풀이 2$N$개의 카드를 나누어 가져 게임을 진행할 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $N$/2 이전 라운드는 큰 수를 내는 사람이 이기고, 이후 라운드는 작은 수를 내는 사람이 이깁니다. 큰 수 게임에서 bessie가 이길 수 있는 카드들이 있을 때, 최대한 작은 수를 내야 나중의 라운드를 준비할 때 유리합니다. 이를 위해 큰 수 게임을 진행할 때, elsie카드들 중 큰 수부터 처리해 나갑니다. 작은 수 게임도 마찬가지 이유로 elsie카드들 중 작은 수부터 처리해 나갑니다. 이 때 큰 수게임 중 카드를 낼 때, 이길 수 있는 카드들 중에서 작은 카드를 내게 되면 작은 수 게임에서 불리해질 수 도 있습니..
문제 www.acmicpc.net/problem/18874 알고리즘 segment tree 풀이 $j$보다 긴 머리카락들이 $j$가 될 때, badhair의 수를 구하는 문제입니다. 관찰이 조금 필요한 문제입니다. 우선 머리카락 길이가 변하는 것을 생각하지 않고 counting inversion을 할 때 브루트포스로 하면 $N^2$이 필요하고 문제에서 $N$제한은 10만이므로 $NlogN$에 inversion을 셀 수 있는 세그먼트 트리를 이용해야합니다. 쿼리($j$)마다 머리카락 길이를 업데이트를 하려면 아무리 빨리한다 하더라도 $O(N)$보다 빠를 순 없고 inversion을 세면 결국 시간초과입니다. 문제의 핵심은 $j$보다 긴 머리카락들이 $j$가 될 때, badhair을 발생시키는 머리카락들은 ..
문제 www.acmicpc.net/problem/3032 알고리즘 DP 풀이 선영이와 정인이가 게임을 합니다. 번갈아 숫자를 골라가며 고른 수의 인접한 수를 고를 때, 선영이가 이길 수 있는 경우를 세는 문제입니다. 인접한 수를 골라나가며 범위를 좁히는 것에서 DP를 떠올릴 수 있습니다. $solve(l,r,t)$= $l, r$부터 범위를 골라나갈 때, 선영이 차례에서 얻을 수 있는 최대 점수 ($t$가 짝수일 때 선영이 차례) 정인이의 차례($t$가 홀수일 때)에는 최악의 플레이를, 선영이의 차례에서는 최선의 플레이를 하면 선영이가 최대한 이길 수 있게 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..
문제 www.acmicpc.net/problem/14450 알고리즘 DP 풀이 소와 존이 가위바위보를 진행합니다. 소는 가위바위보 전문가라 존이 무엇을 낼지 미리 알고 있지만, 게을러서 연속적인 모션을 취합니다. 최대 $K$번 내기 시작하는 것을 바꿀 수 있을 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $i$번째의 결과가 바로 뒤의 $i+1$번의 결과에 영향을 미친다는 점에서 다이나믹 프로그래밍을 떠올릴 수 있습니다. 우리는 현재 가위바위보 단계에서 저장해야할 정보는 다음 세가지 입니다. 현재 몇 번째 가위바위보를 진행하고 있는지, $K$를 몇번 사용했는지, 현재 단계에서 소가 내고 있는 제스쳐는 무엇인지 입니다. 이를 위해 총 3차원의 배열을 사용하며 $cache[i][j][k]$가 영향을 미..
문제 www.acmicpc.net/problem/14169 알고리즘 BFS 풀이 레이저를 시작점에서 농장까지 비추도록 거울을 설치해야 합니다. 이때 필요한 최소의 거울 수를 묻고 있습니다. 좌표가 작다면 이 문제처럼 2차원 배열을 만든 후 BFS를 수행하면 됩니다. 하지만 이 문제는 좌표의 범위가 10억 이하이므로 배열을 선언할 수 없을 뿐더러 거울을 설치할 수 있는 장소의 개수인 $N$이 최대 10만이므로 좌표압축을 해도 2차원 배열안에는 넣을 수 없습니다. 핵심은 주어진 좌표를 BFS를 사용할 수 있도록 적절하게 자료구조에 넣는 것 입니다. 이를 위해 $adj$를 사용했습니다. 인접한 좌표끼리 연결할 때(인접하는 것은 x좌표가 동일한 좌표끼리 묶고 y좌표가 동일한 좌표끼리 묶는 것 입니다), 바로 근..
문제 www.acmicpc.net/problem/19606 알고리즘 BFS 풀이 격자판마다 양수가 쓰여있습니다. 양수를 V라고 가정할 때, r X c = V 에 해당하는 (r, c)로 이동이 가능합니다. (1, 1)에서 시작하여 (M, N)으로 이동 가능한지 판별하는 문제입니다. (1,1)에서 BFS를 수행하려면 조금 까다롭습니다. 가능한 (r, c)를 조사를 해야하는데 이 과정이 시간이 걸립니다. 역으로 (M, N)에서 (1,1)로 이동하면 비교적 간단해집니다. V값을 담고 있는 좌표들을 조사하는 방법으로 수행하면 되기 때문입니다. V마다 좌표를 담기 위해 2차원 배열을 사용했고 BFS를 수행해 나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n..
문제 www.acmicpc.net/problem/2487 알고리즘 union find 풀이 섞기 수열이 주어질 때, 원래의 카드 순서로 돌아오기 위한 궤적을 구하는 문제입니다. 카드들이 턴마다 어디로 움직이는지 파악해야합니다. 카드들이 섞기 수열에 따라 움직이며 각 카드마다 제자리로 돌아와야합니다. 같은 사이클을 사용하는 카드들의 크기들을 파악한 후 사이클의 최소 공배수를 구하면 궤적이 나오게 됩니다. 아래 유니온 파인드에서 $p$는 자신의 부모를 나타내며, 만약 $p$값이 음수라면 그 인덱스가 부모임을 나타내며 절댓값은 해당 사이클의 크기를 나타내도록 구현했습니다. 코드 #include #include #define rep(i, n) for (int i = 0; i < n; ++i) #define RE..
문제 www.acmicpc.net/problem/14168 알고리즘 DP 풀이 H종류의 소와 G종류의 소가 주어집니다. 순차적으로 (연속될 필요는 없음) 방문했을 때 최소의 에너지 구하기. 시작은 H종류의 1번소에서 시작해 H종류의 h번소에서 끝나야합니다. 경찰차와 비슷한 문제입니다. $cache$를 다음과 같이 선언합시다. $cache[i][j][k]$ = H종류의 $i$번째 소, G종류의 $j$번째 소까지 방문이 끝났을 때, 필요한 에너지 최솟값. $k$는 $i, j$ 소중에서 현재 위치의 소를 알기 위함입니다. $k$값이 0이면 H종류의 소에 있음을 나타내고 $k$값이 1이면 G종류의 소에 위치함을 나타냅니다. $cache[i][j][k]$가 갱신할수 있는 상태는 $cache[i+1][j][k]$와..
- Total
- Today
- Yesterday
- Suffix Array
- DP
- dfs
- sorting
- 이분탐색
- bfs
- spring boot
- sweeping
- 동적계획법
- greedy
- implementation
- 2-SAT
- hld
- 세그먼트트리
- 스위핑
- spring
- 이분매칭
- string
- 펜윅트리
- kmp
- Fenwick
- dijkstra
- union find
- 정렬
- 좌표압축
- knapsack
- SCC
- Oracle
- 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 |