기맹기 개발 블로그

BOJ 17143 낚시왕 난이도 : 골드 1 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 전략 구현문제이지만 시간초과가 나지 않도록 해야한다. R, C c) { shark.dir = opposite(shark.dir); ny = shark.y + dy[shark.dir]; nx = shark.x + dx[shark.dir]; } shark.y = ny; shark.x = nx; } } 상어의 위치 갱신을 O(1)만에 할 ..

BOJ 26157 즉흥 여행 (Hard) 난이도 : 플래 3 https://www.acmicpc.net/problem/26157 26157번: 즉흥 여행 (Hard) 첫째 줄에 나라의 개수 $ N $과 항공편의 개수 $ M $이 주어진다. $( 1 \le N \le 200\,000; $ $ 0 \le M \le 500\,000 )$ 둘째 줄부터 $ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 $ v $ $ w $로 주어진다. 이는 $ v $ www.acmicpc.net 전략 SCC에 속한 임의의 두 정점은 방문할 수 있다. 위의 예시에서는 그래프 전체가 하나의 SCC이므로 모든 정점이 결과가 된다. 위의 예시에서는 SCC는 [1], [2, 3, 4] 두 개이며 SCC로 그래프를 압축하면 [1] -> [..

BOJ 2150 Strongly Connected Component 난이도 : 플래 5 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 전략 SCC를 공부하면서 종만북의 타잔 알고리즘으로 구현해보았다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

BOJ 2473 세 용액 난이도 : 골드 3 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전략 생각할 수 있는 가장 간단한 방법은 세 용액의 모든 조합을 찾는 것이다. 3중 for문으로 세 용액의 조합을 만든다면 O(N^3)이다. N의 범위는 [3, 5000] 이므로 N^3은 5^3 * 10억이다. 따라서 다른 방법을 찾아야 한다. 만약 두 개의 용액 조합을 찾는다면 나머지 하나의 용액은 모두 찾을 필요 없이 이진 탐색..

BOJ 12100 2028 (Easy) 난이도 : 골드 2 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 전략 각 라운드마다 위 / 아래 / 왼쪽 / 오른쪽 4방향으로 이동시킬 수 있다. 문제에서 최대 5번으로 제한을 뒀으므로 모든 경우의 수는 4^5 = 1024이다. 브루트포스로 가능하기 때문에 구현에 초점을 둬서 진행한다. 시행착오 셀 충돌하고 병합하는 과정을 구현하면서 루프의 범위가 잘못된 경우가 있었다. 이..

BOJ 2623 음악프로그램 난이도 : 골드 3 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 전략 위상정렬을 사용하여 풀 수 있는 문제임을 알 수 있다. 2252 줄세우기 문제와 비슷하지만 다른 점이 있다. 예제의 입력을 보면 이렇게 각 PD별로 가수의 순서를 정할 수 있는데, 1:1이 아니라 여러명의 가수의 순서를 정하는 것이다. 이로 인해 하나의 노드에서 여러 개의 링크를 가질 수 있다. 따라서 링크를 배열로 저장하여..

BOJ 14238 출근 기록 난이도 : 골드 3 https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 전략 S의 길이가 최대 50이므로, 모든 경우의 수를 다 탐색하면 안된다. 메모이제이션을 사용해서 중복된 연산을 제거해야 한다. 불가능한 것이 계산된 (방문된) 상태는 bool 타입의 dp 배열을 통해 검사하여 제거할 수 있다. 경우의 수 탐색은 재귀 호출로 구현된 dfs로 이루어진다. 시행착오 처음에는 dp의 기준을 dp[현재 idx]..

BOJ 12969 ABC 난이도 : 골드 1 https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net 전략 'A'의 개수 a, 'B'의 개수 b로 이루어진 길이가 len인 문자열에서 조건을 만족하는 쌍이 pair만큼 있다면 len + 1 길이의 문자열에서의 pair은 다음과 같다. 1. 'A' 선택 : pair 2. 'B' 선택 : pair + a 3. 'C' 선택 : pair + a + b 이전 길이의 문자열에서의 'A', 'B', 'C'의 위치와 관계 없이 개수 a, b에 따라..