탐욕 알고리즘(greedy algorithm)

반복(iteration) 과 재귀(recursion)

반복과 재귀는 유사한 작업을 수행

반복은 수행하는 작업이 완료될 때까지 계속 반복, 단위 반복

같은 내용, 같은 작업을 일반화를 통해서 단위 반복

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법

하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다.

반복문이 아닌 재귀 함수 구현으로 메소드 호출

재귀 함수(recursive function)

함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수

자신을 통해 자신을 정의한다.

일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현

기본 부분(basic part)와 유도 부분(inductive part)로 구성

재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.

함수 호출은 프로그램 메모리 구조에서 스택을 사용

재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도의 성능저하 발생 가능

1. 함수에 대한 정의를 명확히 하라
2. Flat : 평평하게 로직을 바라보기
3. 각 재귀의 실행을 결정하는 결정요인(값)은 매개변수로 선언

해결할 문제를 고려해서 반복이나 재귀의 방법을 선택

재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽다.

추상 자료형(List, tree 등)의 알고리즘은 재귀적 구현이 간단하고 자연스러운 경우가 많다.

일반적으로 재귀적 알고리즘(recursion)은 반복 알고리즘(iterative)보다 더 많은 메모리와 연산을 필요로 한다.

입력 값이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다.

피보나치 수열

재귀함수로 구현할 경우 엄청난 중복 호출이 존재

fibo(n)
    IF n < 2 : RETURN n
    ELSE     : RETURN fibo(n - 1) + fibo(n - 2)

메모이제이션(memoization)

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술

동적 계획법의 핵심 기술

메모이제이션을 적용한 피보나치 수열

피보나치 수를 구하는 알고리즘에서 fibo1(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 O(n)으로 줄일 수 있다.

memo를 위한 배열을 할당하고, 모두 0으로 초기화

memo[0] <- 0
memo[1] <- 1
fibo1(n)
    IF n >= 2 AND memo[n] = 0
        memo[n] <- fibo1(n - 1) + fibo1(n - 2)
    RETURN memo[n]

하노이 탑

n개의 원판에서

1. 위의 n-1개의 원판을 들어내기(임시 기둥으로)
2. n 원판을 목적 기둥으로
3. 임시 기둥에 n - 1개의 원판을 목적 기둥으로