종만북

문제 링크 1. 분할 정복 문제 입력의 최대 크기가 20,000이므로 완전 탐색으로 풀기에는 시간 초과가 날 것. 2. 자세한 풀이는 책 참고 (p.196) $n$개의 판자를 절반으로 나눠 두 개의 부분 문제를 만들자. 최대 직사각형은 다음 세 가지 중 하나에 속할 것 1. 왼쪽 부분 문제에 존재 2. 오른쪽 부분 문제에 존재 3. 왼쪽과 오른쪽 부분 문제에 걸쳐서 존재 1번과 2번은 어렵지 않으나 3번의 경우 왼쪽, 오른쪽 부분을 높이가 높은 쪽으로 한 칸씩 확장하면서 찾자. 3. import java.util.Scanner; public class FENCE { static int[] h; public static void main(String[] args) { Scanner sc = new Scan..

문제 링크 1. 분할 정복 문제 완전탐색으로 풀 수 있지만, 효율적으로 문제를 풀기 위한 방법을 고안하자. 2. 자세한 풀이는 책 참고 (p.193) 무식한 방법은 쿼드 트리 압축을 풀어 실제 그림을 만들고 이를 반전하고 다시 압축하는 것 그러나, N이 엄청 클 때 점 하나만 다른 색이라면 매우 비효율적 압축을 다 풀지 않고 뒤집는다면? 1, 2, 3, 4분면이 3, 4, 1, 2사분면으로 바뀌는 아이디어 문자열 입력 부분에서 에러가 나서 뭐가 문제인지 고민을 많이 했다. sc.nextInt()에서 정수를 입력받은 뒤 엔터를 입력하면 개행 문자가 다음 sc.nextLine()의 입력으로 들어가 버린다. 이를 해결하기 위해 정수를 입력받고 나서 sc.nextLine()을 한번 실행 해주자. 3. impor..

문제 링크 1. 완전탐색(브루트포스) 문제 이것으로 완전탐색 문제는 마무리가 되는데, 뭔가 대략적인 틀이 보이는 것 같으면서도 여전히 어렵다. 2. 자세한 풀이는 책 참고 (p.170) 스위치를 누르는 횟수의 모든 조합을 열거하면 무한할 것이다. 12시간 지나면 제자리로 돌아온다는 점을 이용해 유한하게 한정시키기 각 스위치를 누르는 횟수는 0에서 3번 사이이므로 전체 경우의 수는 $4^{10}=1,048,576$개 문제의 조건을 문자열로 표현하는 방법도 익히자 3. import java.util.Scanner; public class CLOCKSYNC { static final int INF = 9999, SWITCHES = 10, CLOCKS = 16; static final String linked[..

문제 링크 1. 완전탐색(브루트포스) 문제 2. 자세한 풀이는 책 참고 (p.161) 블록 한 개를 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하기 빈칸 중 좌상단을 기준으로 블록을 두기 (즉, 기준점 위와 왼쪽은 검은 칸) 그렇게 되면 기준 점에서 블록을 놓을 수 있는 경우의 수는 4가지 3. import java.util.Scanner; public class BOARDCOVER { static int height, weight, wall; static int dir[][][] = { { { 0, 0 }, { 0, 1 }, { 1, 0 } }, { { 0, 0 }, { 0, 1 }, { 1, 1 } }, { { 0, 0 }, { 1, 0 }, { 1, -1 } }, { { 0, 0 }, { ..

문제 링크 1. 종만북 초반 4장까지 개념만 보면서 지루했었는데, 드디어 문제 풀이에 들어갔다. 근데 난이도 '하'인데 뭐가 이렇게 어렵지.. 종만북 완독 가능할지 모르겠다. 완전 탐색 기법을 재귀적으로 풀어보라는 문제여서 그렇게 풀어보려고 노력했다. 그런데, 잘 떠오르지 않아 나만의 방식으로 조합 등을 써서 풀어보려고 했으나, 풀지 못했다. 2. 자세한 풀이는 책 참고 (p.157) 각 답을 만드는 과정을 여러 개의 조각으로 나누기. 서로 친구인 배열을 만드고 거기서 친구인 두 학생을 찾아 짝짓고, 남은 학생들을 짝짓자. 중복 체크! 3. import java.util.Scanner; public class PICNIC { static int n, m; static boolean[][] areFrien..