woody

문제소개 해결과정 Dynamic Programming 연습문제이다. 문제를 간단하게 바꿔보면 단순히 N개 중에 R개를 순서를 고려하지 않고 뽑아야하는 조합 문제이다. 어떻게 조합을 DP에 적용할 수 있을까? 조합은 다음과 같은 점화식을 갖는다. 따라서 DP에 적용해보면 아래와 같은 식을 만들 수 있다. dp[N][R] = dp[N-1][R-1] + dp[N-1][R] DP 연산을 위해 배열에 초기값을 세팅해주고 결과를 확인하면 정답이 나온다. 솔루션 package DP.백준1010_다리놓기; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringToke..

- 문제설명 - 예시 - 해결과정 크기가 n X n 으로 주어졌을 때, 우선 이차원 배열을 생성하고 모든 인덱스에 ' * ' 을 채워넣었다. 제한시간은 1초, 최대 입력인 3^8 X 3^8 크기여도 약 4300만으로 배열을 ' * '으로 초기화 시키는 과정 자체가 문제가 되진 않는다. 전체를 9개의 블럭으로 쪼개어 생각할 수 있다. 이제 가장 가운데 블럭을 모두 공백으로 바꿔주고, 둘러싸고 있는 블럭으로 재귀함수를 호출해 다시 가운데 블럭을 없애주는 과정을 반복할 것이다. 첫 번째로 가운데 블럭을 지우는 방법은 입력이 n 일때 x,y좌표값 모두 n/3 부터 2 * n/3까지 배열을 순회하며 공백으로 바꿔주면 된다. 다음으로 둘러싸고 있는 8개의 블럭을 처리하기 위해 입력값 n을 n/3으로 줄여서 재귀함수..

- 문제설명 & 제한사항 - 예시 - 해결과정 1. 입력으로 자연수가 들어온다면 우선순위 큐(최대힙)에 넣는다. 2. 입력으로 0이 들어온다면 우선순위 큐의 최상단 노드값을 출력한 후 제거한다. 3. 만약 입력으로 0이 들어왔는데 최상단 노드값조차 없다면(큐에 아무것도 없다면), 0을 출력한다. 3번만 해결하면 간단한 문제였다. queue.poll()메소드는 해당 값을 꺼내면서 동시에 출력해주는데, 큐에 값이 없다면 null을 반환한다. poll() 메소드로 출력된 값을 int형 변수에 담아둔다. 참고로 int형 변수는 null값을 포함할 수 없기 때문에 만약 3번의 상황이 발생한다면 NullPointException이 터질 것이다. 이 점을 이용했다! 고의적으로 NullPointException을 발생..

- 문제설명 & 제한사항 - 예시 - 해결과정 입출력으로 Scanner를 사용하지 않고 시간적 효율이 더 좋은 BufferdReader와 BufferdWriter를 사용했다. 모든 입력을 다 받고, 그 중 N번째로 큰 숫자를 얻어야한다. 입력을 한 줄씩 받아서 최소힙을 사용한 우선순위 큐에 넣는다. 큐의 사이즈가 N을 넘어가게 된다면 큐에서 하나씩 제거한다. 이렇게 되면 현재까지 들어온 입력 중에 가장 큰 N개의 숫자만 남게된다. 모든 입력값을 처리하면, 우리가 원하는 N번째로 큰 수가 최상단 노드에 있으므로 바로 꺼내오면 된다! - 솔루션 import java.util.*; import java.io.*; public class Main { public static void main(String[] a..