기맹기 개발 블로그

BOJ 2252 줄 세우기 난이도 : 골드 3 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 전략 문제 이름만 봤을 때는 7568 덩치 랑 비슷해보이지만, 자세히 읽어보면 그래프 문제라는 것을 알 수 있다. 일부 학생들에 대해서만 키 비교가 있고 이에 따라 순서가 정해지므로 방향 그래프인데 물리적인 키를 서로 비교한 것이기 때문에 사이클이 생길 수 없는 조건이다. 이는 위상 정렬로 간단하게 풀 수 있..

BOJ 16724 피리 부는 사나이 난이도 : 골드 3 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 전략 처음에는 단순히 dfs로 탐색해서 연결된 노드들 단위로 개수를 세면 안될까?라고 접근했다. 하지만 이렇게 하면 탐색 순서에 따라 문제가 생길 수 있다. 문제에서 제시된 예시만 보면 dfs로 탐색해도 괜찮을 것 같지만 이런 경우를 보자 (row, col)로 좌표를 나타내었을 때 (1, 1)을 먼저 탐색했..

BOJ 1208 부분수열의 합 2 난이도 : 골드 1 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 전략 BOJ 1806 부분합처럼 연속된 부분 수열의 합을 구하는 문제는 누적합과 투포인터를 사용해서 풀 수 있다. 하지만 이 문제는 연속이라는 조건이 없기 때문에 모든 조합을 확인해야 한다. 수열의 크기 N은 최대 40으로 O(2^N)으로는 풀 수 없다. 이런 문제는 다항시간으로 줄일 수는 없지만 meet..

BOJ 1987 알파벳 난이도 : 골드 4 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전략 주어진 조건을 만족하도록 DFS로 탐색하면서 가장 많이 이동한 칸을 저장하면 된다. 시행착오 간단한 문제로 시행착오는 없었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { stati..

BOJ 10775 공항 난이도 : 골드 2 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 전략 비행기가 순서대로 주어지고, 중간에 한 비행기가 게이트와 연결되지 않으면 이후 비행기들이 연결될 수 없으므로 그리디 형태로 생각해야 한다. 각 비행기는 1

BOJ 9527 1의 개수 난이도 : 골드 2 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 전략 A, B 두 수의 최대 범위가 매우 크므로 무조건 패턴을 찾아서 공식을 만들어야 한다고 접근했다. 1자리 : 0 1 => 1 2자리 : 00 01 10 11 => 4 3자리 : 000 001 010 011 100 101 110 111 => 12 4자리 : 0000 0001 0010 0011 0100 0101 0110 01..

BOJ 10986 나머지 합 난이도 : 골드 3 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 전략 수열의 길이 N은 최대 10^6이므로 모든 부분 구간을 탐색하는 O(N^2)으로는 풀 수 없다. 누적 합을 이용하면 두 지점 사이의 부분 배열의 합을 구할 수 있다. 나는 누적합 % M이 반복되었을 때 해당 구간의 합 % M은 0이 되는 것을 주목했다. 문제의 예제를 예로 들어보자. N = 5, ..

BOJ 2143 두 배열의 합 난이도 : 골드 3 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 전략 처음에는 prefix sum을 구해놓고 포인터를 움직여가는 방식은 어떨까 생각해봤는데 배열이 두개라서 상당히 복잡할 것 같았다. 따라서 부배열 합들을 모두 저장해놓고 탐색하는 것이 좋겠다고 생각했다. 길이가 N인 배열에서 모든 부배열의 합을 구하는 것은 O(N^2..