728x90
반응형
백준
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
- 오늘의 학습 키워드 : DP
- 공부한 내용 본인의 언어로 정리하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[][] call;
static int[] topDown_memo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int i=0; i<T; i++) {
int N = Integer.parseInt(br.readLine());
topDown_memo = new int[N+1];
call = new int[N+2][2];
fibonacci(N);
sb.append(call[N][0]).append(" ").append(call[N][1]).append("\n");
}
System.out.println(sb);
}
public static int fibonacci(int N) {
// 기저 상태 도달 시, 값 초기화 및 호출 횟수 저장
if (N == 0) {
call[0][0] = 1; // 0 값은 1개
call[0][1] = 0; // 1 값은 0개
return topDown_memo[0] = 0;
}
else if (N == 1) {
call[1][0] = 0; // 0 값은 0개
call[1][1] = 1; // 1 값은 1개
return topDown_memo[1] = 1;
}
// 저장된 값이 있는 경우 그대로 사용
if (topDown_memo[N] > 0) {
return topDown_memo[N];
}
// 재귀 함수로 값 저장
topDown_memo[N] = fibonacci(N-1) + fibonacci(N-2);
call[N][0] = call[N-1][0] + call[N-2][0];
call[N][1] = call[N-1][1] + call[N-2][1];
return topDown_memo[N];
}
}
- 오늘의 회고 : 피보나치 수열의 값을 구할 때, 재귀 함수로 다 돌리는 방법도 있지만, 비슷한 값을 반복해서 사용할 경우에 값을 저장하는 DP 방법을 사용해서 O(N^2) -> O(N)으로 시간 복잡도를 줄일 수 있다.
0과 1의 호출 값을 찾으려고 할 때는 [N][0] 호출 값이 [N-1][0] + [N-2][0] 호출 값을 더한다는 패턴을 파악함으로써 문제를 해결할 수 있었다.
99클럽 1기를 수강하면서 작성한 글입니다.
99클럽-1기 모집 중
현직 개발자와 함께하는 코테 스터디
99club.oopy.io
728x90
반응형
'Blog > Education' 카테고리의 다른 글
99클럽 코테 스터디 17일차 TIL + stream (0) | 2024.04.10 |
---|---|
99클럽 코테 스터디 16일차 TIL + DP 리팩토링 (0) | 2024.04.09 |
99클럽 코테 스터디 14일차 TIL + Map key 사전순 정렬 (0) | 2024.04.07 |
99클럽 코테 스터디 13일차 TIL + 해시를 사용한 집합과 맵 (0) | 2024.04.06 |
99클럽 코테 스터디 12일차 TIL + Set (0) | 2024.04.05 |
댓글