[TIL] Top-down과 Bottom-up

Top-down & Bottom-up

1. 개요

프로그래밍을 하다보면 본인도 모르게 Top-down방식과 Bottom-up 방식을 사용하고 있다.
Top-down은 말 그대로 위에서 아래로 문제를 해결하는 것이다.

피보나치 수열의 n번째 항을 찾는 문제로 예를 들어보자면 아래와 같다.

def fibonacci(n):
    if n == 0: return 0
    if n == 1: reutrn 1
    return fibonacci(n - 2) + fibonacci(n - 1)

재귀 깊이나 메모 등은 여기선 스킵

n번째 항에 대해 값을 구하고자 할 때,
n-2번째 항과 n-1번째 항에 대해 문제를 다시 만나는 방식이다.

이는 결과를 구하기 위해 구현한 코드가 문제를 해결하기 위해
더 작은 문제로 잘게 나뉘어지는 방식이다.


Bottom-up은 Top-down과 반대로 아래서부터 차근차근 해결하며 결과를 얻는 방식이다.

다시 한 번 피보나치 수열의 n번째 항을 찾는 코드이다.

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1
    old, new = 0, 1
    iter = 1
    while iter < n:
        iter += 1
        old, new = new, old + new
    return new

0번째 항부터 차근차근 값을 구해 원하는 n번째 값을 구할 수 있다.

2. 결론

항상 무엇이 더 좋은 코드인가? 라는 의문이 들 수 있다.
답부터 말하자면 당연하게도 정답은 없다.
인간의 사고 방식은 거의 Top-down 방식으로 일어나기 때문에
Top-down 방식의 코드 구현이 가독성이 높다.

또한 실제로 어떤 문제를 해결함에 있어서 큰 문제 정의를 하고
이에 대한 대응책을 하나씩 구현하고 나면 이미 Top-down 형식으로 해결됐을 수 있다.
사고 방식과 유사하게 해결하고자 하는 문제와 이에 대한 해결책을 추가하기 때문에
상대적으로 설계 난이도가 쉽다.

그렇다면 Bottom-up 방식의 문제 해결 방식은 어떨 때 진행될까?
크게 두 가지 경우가 있다고 생각한다.
하나는 문제에 대해 명확히 정의된 경우이다.
문제의 규모가 작거나 잘 알려진 문제의 경우 작은 부분부터 체계적인 설계를 통해 해결할 수 있다.

다른 하나는 문제가 해결할 수 없을 정도로 큰 경우이다.
정의할 수 없을 정도로 큰 문제가 발생한다면
해결 가능한 부분에 대해서 우선적으로 처리를 할 필요가 있다.
가능한 부분을 처리하며 결과적으로 문제 해결에 다가가는 방식이라 할 수 있다.


사실 Top-down과 Bottom-up은 대치되는 개념은 아니다.
상호 보완적인 개념으로 큰 틀에서와 그 요소 안에서는 다른 구조일 수도 있다.

중요한 것은 계획적인 설계로 상황에 맞는 방법을 사용하는 것이라 생각한다.