목록보텀업 (1)

Seok_In

[알고리즘/Algorithm]다이나믹 프로그래밍(Dynamic Programming)

🔷 다이나믹 프로그래밍 우리는 현실에서 컴퓨터를 활용할 때 공간적 제약과 시간적 제약을 받는다. 따라서 우리는 이러한 제약을 해결하기 위환 효율적인 알고리즘을 작성해야하는데 대표적인 방법이 다이나믹 프로그래밍 기법이다. 동적계획법이라고도 표현하기도 한다. 다이나믹 프로그래밍에는 두가지 방식이 있다. 바로 탑다운과 보텀업이다. 위 단순 피보나치 함수를 보자. x 값이 작다면 상관없지만 x값이 커지게 되면 밑에있는 하위의 연산들이 계속 진행되어야 한다. 이는 쓸데없는 연산이며 이 경우 를 해결하기 위해 우리는 아래와 같은 탑다운, 보텀업 방식을 이용할 수 있다. ◼탑다운 방식(Top Down) 재귀함수를 이용하며 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 하향식이라고도 한다. 메모이제이션 기법을..
Python/이것이 취업을 위한 코딩 테스트다 with 파이썬 2021. 8. 27. 22:01
이전 Prev 1 Next 다음