[Algorithm] D.P Top-Down vs Bottom-up

Dynamic Programming에서 최적의 값을 찾기 위해 두 가지의 방법을 사용한다.

 

바로 Top-Down 방식과 Bottom-Up 방식!

 

오늘은 이 둘의 차이점에 대해 Deep 하게 파헤쳐 보자.

 

레츠 기릿!

 

Difference Between Top-Down and Bottom-up Approach

 

 

알고리즘은 탑다운과 바텀업 접근법으로 나뉘어 디자인된다. Top-down 접근법에서는 복잡한 모듈이 작은 모듈로 나누어진다. 반면에 Bottom-up 접근법에서는 기초적인 모듈을 점점 합쳐나가는 방식을 이용한다. 알고리즘의 최우선 목표는 데이터 구조 속 데이터를 작동시키는 것이다. 다른 말로 설명하자면, 알고리즘은 데이터 구조속의 데이터 연산을 실행하기 위해 사용된다. 

 

복잡한 알고리즘은 모듈이라고 부르는 작은 조각들로 나뉘어 지는데, 이러한 작업을 '모듈화'라고 한다. 모듈화는 알고리즘의 복잡성을 눈에 띄게 줄이고 과정을 더욱 디자인하거나 실행하기 편하게 만들어 준다. Modular Programming은 각각의 함수들이 서로 독립적이며 각자가 독립적으로 작동하는 함수를 만드는 기술을 말한다. 

 

Comparison Chart

 

비교 항목	Top-Down 접근법	Bottom-Up 접근법
기본	큰 문제를 작은 하위 문제로 나눈다.	최하위 문제를 해결하고 크게 합친다.
과정	하위 모듈은 독립적으로 실행된다.	어떤 데이터를 은닉화 할지 고안하고 정보 은닉을 암시한다.
커뮤니케이션	필요하지 않다.	필요하다.
중복	중복정보가 포함된다.	중복정보는 삭제될 수 있다.
프로그래밍 언어	구조/절차 지향 프로그래밍 언어는 Top-Down 접근법을 따른다.	객체지향 언어는 Bottom-Up 접근법을 따른다.
주요사용	모듈 문서, 테스트 케이스 생성, 코드 실행 및 디버깅	테스팅

 

Definition of Top-Down Approach

 

탑다운 접근법은 기본적으로 복잡한 문제나 알고리즘을 다량의 작은 파트(모듈)로 나눈다. 이 모듈은 결과 모듈이 더이상 분해될 수 없고 필수적으로 인식되어야 할 근본적 프로그램이 될 때까지 분해된다. 특정 모듈화 단계가 되면 분해는 멈추게 된다. Top-Down 접근법은 큰 프로그램 모듈을 간단하고 작은 모듈들로 효율적으로 나누어 정리하는 절차적 분해과정을 거친다. 흐름은 한상 하향식이다. Top-Down 방식은 C 프로그래밍 언어에서의 함수 사용에 적용된다.

 

따라서 Top-Down 방식은 추상적인 디자인에서 시작해서 더이상의 정렬이 필요하지 않은 구체적 수준까지 점차 점차 다듬어진다. 

 

Definition of Bottom-Up Approach

바텀업 접근법은 탑다운 접근법의 정반대로 작동한다. 초기에는 가장 기초적인 파트로 시작하여 상위 레벨의 모듈로 합쳐진다. 하위 모듈의 통합과 상위 모듈로의 통합이 완전한 알고리즘 결과가 도출될 때까지 반복된다.

 

바텀업 접근법은 추상화 레이어로 동작한다. 기본적인 바텀업 접근법 애플리케이션으로는 기초 모듈을 테스트하고 상위 모듈을 테스트하는 테스팅이 있다. 테스팅은 저 레벨의 함수들을 작동하며 이루어 진다.

 

 

Top-Down VS Bottom-Up (Time Complexity)

 

그렇다면 DP에서 top-down과 bottom-up 접근법 둘 중 계산 속도가 더 빠른 접근법은 어디일까?

정답은 Bottom-Up!

이유는 Bottom-up은 함수 호출이 필요하지 않기 때문이다. Bottom-up은 테이블 항목을 이용하는 반면 Top-Down 접근법은 함수 호출이 필요하기 때문에 암묵적 Stack 정보가 발생되기 때문이다. 

 

 

출처: https://techdifferences.com/difference-between-top-down-and-bottom-up-approach.html#ComparisonChart

Difference between Top-down and Bottom-up Approach (with Comparison Chart) - Tech Differences