기맹기 개발 블로그

BOJ 1766 문제집 난이도 : 골드 2 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 전략 위상정렬 문제이므로 문제집 순서를 그래프로 잘 표현해야 한다. 처음 접근했던 방법은 다음과 같다. 우선 입력을 바탕으로 방향 그래프를 생성한다. (그림에서 검은색 화살표) 그리고 노드 번호를 오름차순으로 탐색하면서 자신보다 높은 번호를 가진 노드를 가리키는 간선을 추가한다. (그림에서 파란색 화살표) 이 때 사이클이 생..

BOJ 3665 최종 순위 난이도 : 골드 1 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 전략 1. 각 팀의 기존 순위를 그래프로 표현 2. 변경된 순위로 간선의 방향을 반대로 변경 3. 위상 정렬을 통해 최종 순위 출력 시행착오 처음에는 위처럼 일방향으로 그래프를 이어줬는데 위 상태에서는 순위 변경에 따라 간선 방향을 변경할 수 없다. 따라서 자신보다 뒷 순위 팀을 모두 가리키도록 그래프를 구성하고, 변경된 순서에 따라 간선 방향..

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..