문제 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
- 세그먼트트리
- kmp
- DP
- string
- bfs
- SCC
- 스위핑
- Fenwick
- dfs
- Suffix Array
- 이분탐색
- dijkstra
- knapsack
- 펜윅트리
- hld
- Segment tree
- union find
- 2-SAT
- Oracle
- 동적계획법
- 정렬
- sorting
- 이분매칭
- sweeping
- spring boot
- spring
- 트라이
- implementation
- 좌표압축
- greedy
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |