Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- List.of
- OOP
- 스택
- 성능테스트툴
- 코드스테이츠
- 프로그래머스
- 자바
- 재귀와반복문
- MySQL
- 코딩테스트
- 재귀함수
- 클라우드에서 도커 실행하기
- 알고리즘
- 투포인터알고리즘
- 싱글톤패턴
- Spring Web MVC
- 백준
- Array.asList
- Spring MVC 구성요소
- vm인스턴스생성
- Spring MVC 동작원리
- 버블정렬
- 백준 11659
- 11659
- 코드스테이츠 백엔드
- 구간합구하기
- String.valueOf()
- GCP
- java
- 인텔리제이
Archives
- Today
- Total
순간을 기록으로
백준 자바 2748 피보나치 수2 본문
문제
https://www.acmicpc.net/problem/2748
느낀점
동적프로그래밍에 대해 알게 되었다. 최대한 쉽게 말하자면 재귀적을 값을 구할 때 이전에 구했던 값이라면 다시 연산할 필요 없이 배열에 저장한 값을 꺼내는 방식이다.
해결방법
일반적으로 피보나치의 수는 재귀함수를 통하여 구할 수 있다. 여기서 동적계획법을 사용하면 더 빠르게 값을 구할 수 있다. 동적계획법이란 재귀적으로 함수를 작은 단위로 들어갈 때 값을 저장하여 이전에 저장한 값이 나오면 다시 연산하지 않고 배열에서 꺼내는 방법이다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class 문제_2748 {
static long[] dp; // 동적 프로그래밍에서 값을 저장하기위해(메모이제이션) 배열 선언
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
dp = new long[n+1]; // 크기는 구하는 순서까지만 할당.
for(int i=2; i<n+1; i++) {
dp[i] = -1; // 값 -1은 사용하지 않았다는 의미
}
dp[0] = 0; // 피보나치 초기값 설정
dp[1] = 1;
System.out.println(fibo(n));
}
public static long fibo(int N ) {
if(dp[N] != -1) // 값을 저장한 적이 있다면
return dp[N];
return dp[N] = fibo(N-1) + fibo(N-2); // 없다면
}
}
'Problem Solving' 카테고리의 다른 글
[자바] 11729번 하노이 탑 이동 (0) | 2021.12.09 |
---|---|
[프로그래머스] 내적 (0) | 2021.12.02 |
[자바] 3진법 뒤집기 (0) | 2021.11.11 |
[코딩테스트] 상위 n개 레코드 (0) | 2021.11.11 |
[JAVA] 좌표 압축 18870번 (0) | 2021.11.10 |
Comments