RUBY

다이나믹 프로그래밍(=동적계획법) - 배경) 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적 - 메모리 공간을 약간 더 사용하면 연산속도를 증가시킬 수 있는 방법 - 큰 문제를 작게 나누고, 같은 문제라면 한번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘 - 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치는 점 - 만족해야하는 조건 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 - 구현 방식 1) TOP-DOWN(탑다운)방식 = 하향식 = 메모이제이션 : 큰 문제를 해결하기 위해 작은 문제를 호출 - 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작..