Concept메모이제이션의 위키피디아 사전정의는 다음과 같다.컴퓨터 프로그램이 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램의 실행 속도를 빠르게 하는 기술이다.재귀함수를 호출하는 알고리즘 문제를 메모이제이션으로 풀 수 있다.재귀 호출은 이미 계산한 적이 있는 것도 함수가 호출되면 무조건 또 계산해야하기 때문에 효율이 낮고 시간이 오래걸린다.메모이제이션은 값을 배열에 저장하는 방식으로 재귀 문제를 훨씬 효율적으로 풀 수 있다.재귀는 위에서 아래로 거꾸로 호출하면서, 스택을 쌓는 구조로 문제를 해결한다.(탑 다운 방식으로 볼 수도 있을 것 같다.)메모이제이션은 배열을 사용하기 때문에 당연히 (인덱스) 아래에서 위로 값을 쭉 채워가야한다...

다음 리스트를 버블 정렬로 오름차순으로 정렬해보자. 참고로 버블 정렬은 가장 효율적이지 않은 정렬 방식이기 때문에 실제로 잘 사용하지 않는다. list = [10, 3, 7, 5, 2] (리스트의 길이 -1)번만큼 다음 과정을 반복한다. 아이템과 다음 아이템을 비교해서, 다음 아이템이 더 작으면 자리를 바꾼다. [10, 3, 7, 5, 2] 10과 3을 비교한다. 자리를 바꿔준다. [3, 10, 7, 5, 2] 10과 7을 비교한다. 자리를 바꿔준다. [3, 7, 10, 5, 2] 10과 5를 비교한다. 자리를 바꿔준다. [3, 7, 5, 10, 2] 10과 2를 비교한다. 자리를 바꿔준다. 첫번째 턴을 마친 후 리스트 = [3, 7, 5, 2, 10] 이제 다시 처음부터 아이템을 비교하기 시작한다. [..

다음 리스트를 선택정렬로 오름차순으로 정렬해보자. list = [13, 4, 8, 20, 37, 17] How? 가장 작은 쪽, 즉 0번 인덱스부터 시작해서 해당 자리에 들어올 가장작은 값을 선택한 뒤, 자리를 바꾼다.  [13, 4, 8, 20, 37, 17]13에 들어올 값을 탐색한다. 1번 ~ 5번 인덱스 값 중 가장작은 값은 4이다.13과 4의 자리를 바꾼다.[4, 13, 8, 20, 37, 17]  [4, 13, 8, 20, 37, 17]13에 들어올 값을 탐색한다. 2번 ~ 5번 인덱스 값 중 가장작은 값은 8이다.13과 8의 자리를 바꾼다. [4, 8, 13, 20, 37, 17]   [4, 8, 13, 20, 37, 17]13보다 작은 값이 없으므로 이 자..

다음 리스트를 삽입정렬 방식으로 정렬해보자. list = [20, 18, 10, 3, 30, 9] How? : 리스트의 아이템을 하나씩 삽입하고, 정렬한다. 첫 아이템 20을 삽입한다. Sorted List = (20) 18을 삽입한다. Sorted List = (18, 20) 10을 삽입한다. Sorted List = (10, 18, 20) 3을 삽입한다. Sorted List = (3, 10, 18, 20) 30을 삽입한다. Sorted List = (3, 10, 18, 20, 30) 9를 삽입한다. Sorted List = (3, 9, 10, 18, 20, 30) 정렬된 리스트 : (3, 9, 10, 18, 20, 30) 시간 복잡도 (Time Complexity) O(n²) : 모든 아이템을 삽입..

Lecture 04 - Framework for solving Dp problem : Solve Dp basic problems & outline the basic steps required for a dynamic programming solution Recap ch.3) Idea of DP n = 5 1 + 2 + 3 + 4 + 5 f(n) = f(n-1) + n [0,1,3,6,10,15] *Core Idea of Dp : we don't want to recalculate things. We want to rely on existing solutions on the information that we already know. What if n = 6? sum = f(6) = f(5) + 6 = 1..

Lecture 03 - Elementary Problem Goal 1. how to spot dynamic programming problems 2. going over very basic problems Two types of DP problem 1. Combinatoric problem → how many? ex) How many ways to make a change? End goal : count something 2. Optimiaztion problem → max, min ex) What is the minimum steps to ~ ? End goal : minimize, maximize some functions Basic Example We need to calculate the sum ..