[붙끝코] 9일차 dp를 뿌숴,,,(1) (백준 2748)
오늘은 DP문제를 풀겁니다.🌝 dp는 정말 중요하므로!!! 개념도 정리하고 가겠음니다.
( 사실 중요한것도 중요한건데 dp 개념이 약하거덩요 ㅋㅋ)
갑오자구yo~
개념 부분은 인프런의 '개발남노씨' 슨상님의 강의를 참고하여씀다!!!
인프런 '코딩테스트 [ ALL IN ONE ]'
우선 dp 즉 "다이나믹 프로그래밍(Dynamic Programming)"란
큰 문제를 작은 문제들로 나누어 해결하고 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법을 의미합니다.
dp의 특징으로는
1. 중복 계산 감소: 이미 계산한 결과를 저장-> 필요할 때마다 재활용. 중복된 계산을 피할 수 있음!
2. 점화식: 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의.
점화식의 예로는
F(n) = F(n-1) + F(n-2) (for n>=2)이런게 있습니다!
3. 최적 부분 구조: 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 합니다. (최적해라는 것은 쉽게 말해서 각 문제의 최적의 해결책이라고 이해하면된다!)
그럼 문제 풀때도 1)크고 복잡한 문제를 작은 문제들로 나눈다. -> 2)하위 문제들의 답을 계산한다.(중복 하위 문제) -> 3)하위문제들의 답을 통해 원래 문제에 대한 답을 구한다. 로 풀면 되겠습니당
말은 쉽죠...ㅎㅎ😒
앞으로 4일 동안은 dp문제를 풀건데 매일매일 dp에 대한 개념, 주의해야하는 점들을 함께 가져와볼려구요! (아마ㄷ...겠돈~)
그럼 오늘의 문제를 보면서 더 내실을 다져볼게용
오늘은 초딩도 푸는 문제!
백준 2748
일반적인 피보나치 수열이긴한데 이 문제에서는 몇번째 피보나치 수열인지 input으로 주면 그에 대한 피보나치 수가 output으로 나와야하는 문제입니다.
에를 들어 n=17일때 까지 피보나치 수를 써보면
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597여기서 10이라고 input이 주어지면 output은 55가 출력되어야 합니다.
📌 문제 탐색하기
입력
n ->n은 90보다 작거나 같은 자연수
출력
n번째 피보나치 수
base case : 0번째 피보나치 수 0. 1번째 피보나치수:1
base case란 하위 문제로 나눌 필요없이 바로 답을 할 수 있는 case를 말합니다.
📌 코드 설계하기
정리
예를 들어 5번째 피보나치 수열를 구한다고 해봅시다.
우선, 완전탐색(재귀) 로 접근한다고 한다면 다음 그림과 같이 나타낼 수 있습니다.
다음 그림에서 보면 f(3), f(2) 같은 경우 중복돼서 계산되고 있죠?? 그림은 f(5)를 구하는거지만 n이 커진다면 중복 계산이 엄청 늘고 시간복잡도가 증가할 것 입니다.
완전탐색으로 구현한 코드를 보면
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)시간복잡도는 O(2^n) 입니다. 이 문제에서는 2^90이라고 한다면!!... 썩 유쾌하지는 않죠?
그래서 이런 문제를 보면 저희는 dp로 접근해야 한다고 캐치할 수 있습니다.
저희는 중복하위 문제에 대한 결과를 저장하여 중복된 문제에 사용할거에요!
코드로 보면
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]
시간복잡도는 O(n)이 됩니다!!!!! 이게 dp의 매직!!!
이제 문제를 풀건데 문제는 자바민국의 국민답게 자바로 풀어보겠습니다.
설계
- Main 메서드 : 입력갑과 출력값 받음-> BufferedReader && BufferedWriter
- Solutin 메서드 :
정수 n을 입력받아 n번째 피보나치 수를 계산해 BigInteger 타입으로 반환
base case -> n=0 이면 BigInteger.ZERO
-> n=1 이면 BigInteger.ONE
DP -> dp[i] = dp[i - 1].add(dp[i - 2]);📌 시도 회차 수정 사항
1) 역시 초심자 답게 자료형으로 엄청 해맸습니다... n=90일때 이미 int 자료형의 범위를 넘어가지만 계속되는 오류에...🥹 하..
자료형을 BigInteger 또는 long으로 바꾸어 구현 가능합니다!
📌 정답 코드
import java.io.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
BigInteger sol = solution(n);
bw.write(sol.toString());
bw.flush();
bw.close();
br.close();
}
static BigInteger solution(int n) {
if (n == 0) return BigInteger.ZERO;
if (n == 1) return BigInteger.ONE;
BigInteger[] dp = new BigInteger[n + 1];
dp[0] = BigInteger.ZERO;
dp[1] = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1].add(dp[i - 2]);
}
return dp[n];
}
}