피보나치수열

동적 프로그래밍이란? 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다. 네 맞습니다. DFS와 같은 개념입니다. 기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가?? 결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. DFS와 동적프로그래밍의 차이점!! 여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다. 문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다. DFS로 접근하게 되면, 7+3+8+2+..

재귀 알고리즘이란? 재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다. 재귀 함수는 반복문(for, while문)으로도 충분히 대체 가능하다. 재귀 함수는 언제 사용할까? - 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 - 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우 - 변수의 사용을 줄여 메모리를 비교적 간소화하고 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우 - 단, 재귀함수가 모든 경우에서 반복문보다 좋은 것은 아니다. 대표적인 예로는 피보나치 수열, 팩토리얼 계산, 탐색 트리의 순회 등이 있다. 재귀 알고리즘의 사용 1. 피보나치 수열 피보나치 수열이란, F(0) = 0 F(1) = 1 F(2) = F(0) + F(1) F(3)..