Theory 이론

[메모이제이션 - Memoization] 메모이제이션이란?

메모이제이션이란? 메모이제이션이란 입력값에 대한 결괏값을 저장해둠으로써 같은 입력값에 따른 함수의 실행이 중복해서 일어나지 않도록 해주는 기법이다. DP로 문제를 풀 때 자주 등장하며, 함수의 중복 호출을 방지해 효율을 높여준다. 왜 쓰는가? 첫 번째와 두 번째가 1인 피보나치 수를 예로 들어보자. 피보나치 수를 재귀적으로 구한다면 위에서 볼 수 있듯이 fib(3), fib(4)등 앞선 피보나치 수가 여러 번 호출된다. 이때 fib(3), fib(4)이 각각 2, 3인 것을 저장해 두지 않는다면, fib(5), fib(6)이 무엇인지 구하기 위해 fib(3), fib(4)를 다시 구해야 한다. 이때 배열을 하나 만들어 이미 구해진 피보나치 수를 저장해둔다면 이 수고를 덜을 수 있다. 구하려는 수가 작다면..

[동적 계획법 - Dynamic Programing] DP란?

DP란? DP, Dynamic Programming(동적 계획법)은 무엇일까? DP란, 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 특정한 알고리즘을 지칭하는 것이 아니라, 기법 그 자체를 의미한다. 같은 DP로 문제를 풀어도 다른 알고리즘을 이용할 수도 있다는 것이다. DP가 무엇인지 처음 듣는 사람은 문제를 작은 문제로 나누어 해결하는 기법이 왜 Dynamic Programming이라 불리는 것일까, 하고 궁금증을 가질 수도 있다. 이에 대한 대답은 그저 '멋있어서'이다. Dynamic Programming이란 명칭을 고안한 Richard Bellman에 따르면 말이다. DP는 왜 중요할까? 백준, 코드포스 등 PS(Problem Solving) 사이트에서 문제를 풀다 보면 DP로..