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. 최소 신장 트리(MST)신장 트리n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리 (MST, Minimum Spanning Tree)무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 최소 신장 트리를 구하는 대표적인 알고리즘인 Kruskal과 Prim에 대해 알아보자.1. Kruskal 알고리즘크루스칼 알고리즘은 간선 중심 그래프이며, 그리디 알고리즘이다.1-1. 알고리즘간선을 하나씩 선택해서 MST를 찾는 알고리즘모든 간선을 가중치에 따라 오름차순으로 정렬가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴사이클이 발생하면 MST에 포함시키지 않음사이클이 발생하지 않는 경우 MST에 포함n-1개의 간선이 선..
0. 서로소 집합서로소(상호배타) 집합은 서로 중복 포함된 원소가 없는 집합이다. 즉, 교집합이 없는 집합을 의미한다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분하며 이를 대표자(representative)라 한다.서로소 집합을 표현하는 방법연결 리스트트리 → 구현이 쉬움서로소 집합 연산Make-Set(x) - 유일한 멤버 x를 포함하는 새로운 집합을 생성 (서로소 집합 초기화 작업)Find-Set(x) - x를 포함하는 집합을 찾는 연산 (대표자 탐색)Union(x, y) - x와 y를 포함하는 두 집합을 통합하는 연산1. 서로소 집합 표현1-1. 연결 리스트같은 집합의 원소들은 하나의 연결 리스트로 관리한다.연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.각 원소는 집합의 대표원소..
