항해99 온보딩 9일차

1. 오늘 진행한 것

알고리즘 문제풀이
다리놓기 - https://www.acmicpc.net/problem/1010
피보나치 함수 - https://www.acmicpc.net/problem/1003
신나는 함수 실행 - https://www.acmicpc.net/problem/9184

2. 새로 알게 된 점

동적계획법 (Dynamic Programming)

최적화 이론의 한 가지이다.

해결해야 할 문제의 패턴을 파악하고 기존에 했던 계산을 변수나 자료구조에 저장해두고 그걸 호출하면서 연산량을 줄이는 방식이다.

대표적인 문제로 피보나치 수열 구하기가 있다.

int[] fibo = new int[max+1]; // 피보나치 배열
fibo[0] = 1;
fibo[1] = 1;
int top = 1;

이런 식으로 피보나치 수열 값을 저장하는 배열을 만들고

if (arr[i] > top) {
	// 피보나치 배열 채우기
	// for i top부터 arr[i]
	int n = top + 1;
	for (int j = n; j <= arr[i]; j++) {
		fibo[j] = fibo[j-1] + fibo[j-2];
	}
	top = arr[i];
}

찾으려는 값이 배열에 없는 경우 기존에 찾은 값의 최대값부터 찾으려는 값까지 피보나치 배열을 채운다.