전체 글71 ABC 453 C-F 풀이 [관련 문제 링크] C - Sneaking Glances 이동 거리가 주어질 때, 0 을 몇 번 통과하는지 구한다. 풀이: 20개의 이동거리가 주어지므로 각 이동에 대해 왼쪽, 오른쪽인 경우를 모두 세면 \( 2^{20} \) 정도의 경우의 수가 나오므로 완전 탐색한다. D - Go Straight 격자판에서 벽이 있고 빈칸이 있고 목적지, 시작지가 있을 때 목적지까지 가는 경로를 구한다. 풀이: 진행 방향을 유지하거나 바꿔야 하는 특수한 칸들이 있기 때문에 상태를 (위치, 이동 방향)으로 잡는다. bfs를 한다. E - .. 2026. 4. 12. minimum cost flow 알고리즘 🔗 G - Domino Covering SUM (AtCoder Beginner Contest 407) 그래프에서 최대 유량을 찾는 알고리즘이 있다. 이 때는 그냥 찾으면 되지만, 간선에 비용이 딸려있는 경우가 있다. 각 유량에 대해 최소 비용을 찾고자할 때 minmum cost flow알고리즘을 사용한다. 앳코더 라이브러리에 잘 정리가 되어 있는데, .slope(시작, 도착)를 사용하면 \( (\text{flow, cost}) \) vector가 반환된다. 시간 복잡도는 \( \text{유량} \times (\text{정점} + \text{간선}) \) 정도이다. 아래 문제를 통해 이 알고리즘을 더 이해해보자. [G.. 2026. 4. 8. ABC 398 D-F 풀이 🔗 Tasks - UNIQUE VISION Programming Contest 2025 Spring (ABC 398) [이미지 설명] D - Bonfire \( (0, 0) \)에 화톳불이 있고, 현재 사람의 위치는 \( (r, c) \)이다. 바람의 방향에 따라 연기의 위치가 변한다. 바람의 방향을 문자열로 알려줄 때 각 시점에 \( (r, c) \)에 연기가 도달하는지 구하라. 풀이: 시간 상 모든 연기를 시뮬레이션할 수는 없다. 사람을 기준으로 생각해보면, 모든 연기가 움직이는 것은 연기의 위치는 그대로고 사람의 위치만 움직이는 것으로 대응 가능하고, 화톳불과 사람의 상대적인 위치는 변하지 않아야 하므로, 화톳.. 2026. 4. 8. ABC 383 D-F 풀이 🔗 AtCoder Beginner Contest 383 대회 링크D - 9 Divisors\(n\)이 주어질 때 약수가 9개인 수를 구하라.풀이: \((p_1 \cdot p_2)^2\), \(p^8\) 꼴의 수가 약수를 9개 가지므로 완전 탐색한다.E - Sum of Max Matching그래프와 수열 \(a, b\)가 주어진다. \(f(u, v) =\) 정점 \(u, v\)를 잇는 경로 위의 최대 edge라고 할 때 \(\sum f(a_i, b_i)\)가 최소가 되도록 \(b\)를 permute하라.풀이: 간선을 가중치 오름차순으로 검사한다. 양 끝 점이 같은 요소라면 넘어가고 다른 요소라면 한쪽의 \(a\)와 다른 한 쪽의 \(b\)를 연결한다.F - Diversity가치 \(p\), 값 \(u\).. 2026. 4. 7. suffix array & lcp array 🔗 https://atcoder.jp/contests/abc452/tasks/abc452_g Suffix Array와 LCP Array의 활용 부분 문자열은 문자열의 연속적인 부분을 의미한다. prefix는 문자열의 앞부분으로, \(prefix(i)\)는 1부터 \(i\)번째 까지의 부분 문자열을 의미한다. suffix는 문자열의 뒷부분으로, \(suffix(i)\)는 \(i\)번째부터 끝까지의 부분 문자열을 의미한다. suffix array는 문자열의 모든 suffix를 정렬했을 때 \(i\)번째에 오는 suffix가 무엇인지를 저장한다. lcp array.. 2026. 4. 6. ABC 452 A-F 풀이 AtCoder Beginner Contest 452 - AtCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp A - Gothec\(1.7, 3.3, 5.5, 7.7, 9.9\)는 특별한 날이다. 월, 일 \(A, B\)가 주어질 때 특별한 날인지 판단하라.B - Draw Frame\(H, W\)가 주어진다. \(H \times W\)의 격자판 중 가장자리를 #으로 채운 문자열을 출력하라.C - Fishbones\(a_i, b_i\)가 주어진다. 문자열 \(s_j\)에 대해 길이가 \(a_i\)이고, \(b_i\)번 .. 2026. 4. 4. 이전 1 2 3 4 ··· 12 다음