코딩테스트 - 패스트캠퍼스 챌린지 11일차

수강한 강의
Chapter 13 재귀 용법
- 알고리즘 해결에 중요한 재귀 호출 이해
Chapter 14 동적 계획법과 분할 정복
- 동적 계획법과 분할 정복

학습 후기
재귀 용법 recursive call
재귀 호출로도 불리며 함수 안에서 동일안 함수를 호출하는 형태를 말한다. 저번 08일 차 강의 공간 복잡도에서 factorial을 구하는 함수를 작성할 때 for문으로 작성한 forFactorial 함수와 recursiveFactorial 함수를 볼 수 있다. 재귀 호출은 스택의 전형적인 예이다.
아래 그림은 재귀 호출을 실행하고 intellij에서 debug모드로 함수 콜을 확인한 모습이다.
HeapLecture[1]에서 n = 4,
HeapLecture[2]에서 n = 3,
HeapLecture[3]에서 n = 2,
HeapLecture[4]에서 n = 1까지 호출되어 스택으로 쌓인 뒤 return 하며 호출 스택에서 사라지는 그림이다.

recursive 4번째 call

recursive 3번째 call

recursive 2번째 call

recursive 1번째 call

동적 계획법(Dynamic Programming)과 분할 정복(Divide and Conquer)
동적 계획법(DP)은 작은 문제들을 해결하여 그 해를 가지고 보다 큰 문제의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘으로 Memoization 기법을 사용하는 게 특징이다.
분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하여 문제의 답을 얻는 알고리즘이다. 일반적으로 재귀 함수로 구현한다.
두 알고리즘의 공통점은 문제를 잘게 쪼개서 문제 풀이의 기반을 마련하는 데 있고 차이점은 동적 계획법만이 Memoization 기법을 사용하여 문제를 푼다.
Memoization 기법을 사용한 피보나치 함수와 재귀 함수를 이용한 피보나치 함수의 프로그래밍 예시로 동적 계획법과 분할 정복의 차이점을 강의에서 보여주었다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.