Bottom-up ? Top-down?

오늘 프로그래머스의 레벨2 점프와 순간이동을 풀었고, 다른 분들의 풀이를 보았습니다.
Bottom-up 이 아니라 Top-down 으로 풀어야 한다는 글이었죠.

......?
전 둘다 뭔지 몰라요...^^ 그래서 알아봤습니다.

먼저, Bottom-up 과 Top-down 은 DP 문제를 푸는 방식입니다.

Bottom-up ?

• 아래에서 위로! 상향식 입니다.
• 가장 작은 문제부터 답을 찾아가는 방식입니다.
• DP 테이블을 활용합니다.
• 단순 반복문을 이용해 문제를 해결합니다.
• DP의 전형적인 형태이며, 메모이제이션을 하지 않아 오버헤드 위험이 줄어듭니다.

// 피보나치 수로 보는 Bottom-up 예시

guard n > 4 else { return n - 1 }
var dic = [0: 1, 1: 1, 2: 1, 3: 2, 4: 3]
    
for i in  5...n {
	dic[i] = (dic[i - 1]! + dic[i - 2]!) % 1234567
}
    
return dic[n]!

Top-down ?

• 위에서 아래로! 하향식 입니다.
• Bottom-up과는 다르게, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식입니다.
• 메모이제이션을 활용합니다.
• 재귀 함수를 이용해 문제를 해결합니다.
• 메모이제이션을 활용하기 때문에, 오버헤드가 발생할 수 있습니다.
  때문에, 가급적 Bottom-up 으로 푸는게 좋습니다.

✔️ 메모이제이션이란 ?
이미 구한 결과를 메모리에 저장해두고, 호출 시 메모(저장)한 결과를 그대로 가져오는 기법으로
동일 계산의 반복 수행 제거해 프로그램의 성능을 향상시킵니다.

// 피보나치 수로 보는 Top-down 예시

func fibo(_ n: Int) -> Int {
    guard n > 1 else { return n }
    return fibo(n - 1) + fibo(n - 2)
}

DP와 재귀를 학습했음에도 몰랐다니..
이제라도 알았으니, 앞으로 문제를 풀 때 더 적절한 방식을 대입할 수 있겠네요! ㅎ_ㅎ