문제 링크 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..
Algorithm
문제 링크 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..
0. 본 게시물은 자료구조프로그래밍 수업의 과제로 사용되었던 자료입니다. 참고용으로만 보시길 권장드리며, 코드 복제 시 본인에게 불이익이 따를 수 있음을 알려드립니다. 1. 문제 min leftist tree 합병(meld) 하기 (최소 좌향 트리) - min leftist tree의 정수 key값이 입력 파일에서 순서대로 주어짐 - 정수 4개로 min leftist tree를 생성하여 queue에 삽입 - 정수 key를 하나씩 삽입하면서 tree 생성 (마지막에는 4개 이하로 된 min leftist tree 생성) - queue에서 leftist tree 2개를 가져와서 합병하여 다시 queue에 삽입하는 과정을 반복하여 하나의 min leftist tree 생성 - 정수는 파일에서 입력 (개수 정해..
문제 링크 1. 기본적인 그래프 문제였지만 요즘 문제 풀기가 너무 싫어서 뭉그적거리면서 풀었던 문제 2. BFS를 이용하여 문제를 해결하였다. 나이트가 이동할 수 있는 8가지 방향을 배열로 만들어준다. int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 }; int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 }; 조건에 맞으면 queue에 넣는데, 중요한 점은 cnt 2차원 배열을 만들어 해당 위치까지 몇 번을 이동했는지를 저장한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n; static Pos now..
문제 링크 1. 골드 5 문제로 분류되어있던데, 그 정도 난이도는 아닌 것 같다. 정답률도 $58\%$로 다소 높은 편. 여느 문제와 비슷하여 쉽게 풀었다. 다만 조금 더럽게 푼 듯하다. 2. flag 변수를 이용해 적록색맹 일 때 아닐 때를 구분하여 if 문 처리를 하였다. 아스키코드 값을 통해 'R' - 'G' = 11 임을 이용하였다. 다른 사람의 풀이를 보니 적을 녹으로 바꿔서 bfs 한 번 더 돌리던데 그게 좀 더 깔끔한 코드인 것 같다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n; static char[][] data; public ..
