오늘의 dp 이론 부분은 bottom-up vs top-down 입니다. 각설하고 가보겠습니다!!
오늘도 강의 내용은 인프런 '개발남노씨' 강사님의 강의 내용을 참고하였습니다.
우선 저번 시간에 저희가 구현했던 피보나피 수열을 한번 떠올려 볼까요??
memo = {}
def fibo(n):
if n == 1 or n == 2:
return 1
if n not in memo:
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]다음 코드를 보면 f(n)부터 f(1)로 접근하고 있습니다! 이런 방식을 top-down 방식이라고 합니다.
*사진에 memo 부분에 f(7)=13이 빠졌네요!! 참고 부탁드려요:)
접근 방식은 위에서부터 아래 모양으로 하나하나 잘게 쪼개는 모양이지만 계산은 Base Case에서 시작되며 작은 문제에서 큰 문제로 해결해나가고 있습니다!
반대로 f(1)부터 f(n)까지 접근하는 방식을 보겠습니다.
memo = {}
def fibo(n):
for i in range(3, n + 1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]다음 큰문제를 잘게 쪼개는 top down과 다르게 밑에서 부터 차근차근 계산해 나가는 bottom up 방식입니다.
예시를 보면 f(7)에서 f(1)까지 재귀를 이용해서 위에서 아래로 접근하는 top-down과 달리 bottom-up은 base-case부터 시작해 반복문을 돌면서 차근차근 f(7)까지 접근하고 있네요!
오늘의 문제는 부녀회장이 될테야 입니다.
📌 문제 탐색하기
입력
- 가장 첫 줄에 테스트 케이스
- 테스트 케이스에 해당하는 첫번째 줄 다음부터 두 줄씩 두줄씩 k(층) 와 n(호) 이 주어진다.
- 아파트에는 0층부터 있고, 각 층에는 1호부터 시작
- 0층은 i호에는 i명에 해당하는 사람들이 산다.
출력
- 테스트 케이스에 해당하는 k층 n호에 사는 거주민 수
📌 코드 설계하기
k층 n호에는 한층아래에(k-1층)1호부터 n호까지 사는 사람들의 총합이 살고 있습니다!
정말 끔찍하네요
k 층 n 호 = ( k - 1 ) 층 1 호 + ( k - 1 ) 층 2 호 + ⋯ + ( k - 1 ) 층 n 호요렇게 볼 수 있는데요!
문제에서 조건은 1 ≤ k, n ≤ 14 이렇게 주어져 있습니다.
층수도 최대 14층까지 호수도 최대 14호까지 있음을 확인 가능하네요.
문제 상황을 토대로 우선 표를 작성해봤습니다!
예를 들어 3층에 4호사는 사람 수는 2층에 1호 인원+2호+3호+4호가 되고 2층의 1호 사는 사람=1층의 1호, 2층의 2호는 1층의 1호+2층의 2호.... 여러개의 중복 하위문제...dp의 냄새가 물씬 풍깁니다. 층수와 호수로 나누어져있을 뿐 어제 풀었던 피보나치 수열 문제와 거의 똑같음을 확인할 수 있습니다!
설계 1) 최대 크기에 해당하는 배열 한번 생성 후 재사용
int [][] apt= new int [15][15]설계2) dp 구현
- base case
이 문제에서 base case 두가지로 볼 수 있습니다!- 0층 i호에는 i명이 산다.
- 모든 층에 1호에는 1명이 산다.
apt[i][1] = 1; // 전층 1호
apt[0][i] = i; // 0층 i호- 점화식
i 층의 바로 직전의(i-1)층의 (j-1) 호수 사람과 j 호의 바로 아래층인 (i-1)층 j호 사람수 합이 되겠습니다!!
apt[i][j] = apt[i][j - 1] + apt[i - 1][j];점화식부분 구현할때 base case에 해당하는 부분을 제외한 층수는 1층부터 14층까지 (0층 i호) 호수는 2호부터 14호까지 (전층 1호)이중 for문으로 감싸면 되겠습니다!
오늘 이론부분과 함께 보자면 먼저 0층과 각 층의 1호에 해당하는 base case들을 채워넣은 후 반복문을 통해 차례대로 나머지 값을 계산하고 있으니 bottom-up 방식으로 구현하고 있음을 볼 수 있습니다!
이제 끝입니다! 입력값 받는 부분은 생략하도록 하겠습니다! 늘 그랬듯이 BufferedReader와 StringBuilder를 이용했어요!!
그리고 아실랑가 모르겠지만 요즘 주요로직은 따로 클래스로 빼서 작성 중입니다!! 저도 이제 가독성을 생각하는 단계라구요(?)ㅎㅎ
📌 시도 회차 수정 사항
설계 1번 포인트에서 처음에서는 테스트케이스 마다 배열을 생성하다가 최대 크기에 해당하는 배열을 먼저 만들고 사용하는 방식으로 바로 바꿨습니다!
테스트 케이스마다 k층n호에 대한 배열을 각각 생성시 공간 복잡도 최악...임을 깨닫고 바로 gg쳤습니다!!
before
...
int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력
for (int i = 0; i < T; i++) {
int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
int[][] apt= solution(k, n);
sb.append(apt[k][n]).append('\n');
}
System.out.println(sb);
}
public static int[][] apt(int k, int n) {
int[][] apt= new int[k + 1][n + 1];
after
int [][] apt= new int [15][15]📌 정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static int[][] apt = new int[15][15];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
solution();
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int k = Integer.parseInt(br.readLine());
int n = Integer.parseInt(br.readLine());
sb.append(apt[k][n]).append('\n');
}
System.out.println(sb);
}
public static void solution () {
for (int i = 0; i < 15; i++) {
apt[i][1] = 1; // i층 1호
apt[0][i] = i; // 0층 i호
}
for (int i = 1; i < 15; i++) { // 1층~14층
for (int j = 2; j < 15; j++) {// 2호~14호
apt[i][j] = apt[i][j - 1] + apt[i - 1][j];
}
}
}
}