0. 0/1 Knapsack배낭에 물건을 쪼개지 않고 담는 문제를 0/1 Knapsack이라고 한다.이 문제를 부분집합으로 풀게 되면 시간 복잡도가 O(2^n)이므로, DP로 접근하는 것이 효율적인 문제가 된다.1. 0/1 Knapsack 정의W = 배낭의 용량(v_i, w_i) = (물건의 가치, 물건의 무게)K[i, w] = 물건 i까지 고려했을 때, 배낭의 용량이 w일 때의 최대 가치 1-1. K[i, w] 수식 정의1-2. i번째 물건을 고려할 때1-3. 의사 코드배낭의 용량 Wn개의 물건과 각 물건 i의 무게 w_i와 가치 v_i, (단, i = 1, 2, ..., n)K[n, W]For i in 0 -> n : K[i, 0] W : K[0, w] n For w in 1 -> W If..

0. 메모이제이션(memoization)메모이제이션(memoization)이전에 계산한 값을 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다.동적 계획법의 핵심이 된다. 순수함수만 메모이제이션이 가능하다.순수함수란?1. 함수의 실행이 부수효과를 일으키지 않는 함수2. 동일한 input에 대해 동일한 output을 반환하는 함수3. 매개변수 이외에 함수 외부의 것들을 사용하지 않는 함수 메모이제이션은 추가적인 메모리 공간이 필요하다.추가로 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 됨에 따라 실행 속도 저하 또는 오버 플로우가 발생할 수 있다.0-1. 예시가장 일반적인 피보나치 수열 알고리즘 코드이다.fibo(n) { if (n  피보나치 수열 알고리즘에 메..

0. 최단 경로최단 경로간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(Dijkstra) 알고리즘음의 가중치를 허용하지 않음벨만-포드(Bellman-Ford) 알고리즘음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워셜(Floyd-Warshall) 알고리즘이번에는 이 중에서 다익스트라( Dijkstra) 알고리즘을 알아본다.1. 다익스트라(Dijkstra) 알고리즘시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.그리디 기법을 사용한 알고리즘으로 정점 중심 그래프로 표현한다.프림(Prim) 알고리즘과 ..

0. 힙(Heap)완전 이진 트리에 있는 노드에서 가장 큰 키 값이나 가장 작은 키 값을 찾기 위해서 만든 자료구조이다.중복 값도 가능하다.힙의 특징으로는 노드의 삽입 혹은 삭제 연산이 발생할 때만, 해당 노드가 옳바른 자리를 찾아간다.0-1. 최대 힙(Max Heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 >= 자식 노드의 키 값루트 노드: 키 값이 가장 큰 노드0-2. 최소 힙(Min Heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 루트 노드: 키 값이 가장 작은 노드1. 힙 연산최대 힙을 기준으로 설명을 할 예정이며, 최소 힙의 경우도 동일하게 동작한다.노드 하나의 삽입 / 삭제 연산은 시간 복잡도가 O(lonN)이고 최대값/최소값을..