알고리즘19 [알고리즘] [19] 동적 계획법 1. 메모이제이션 (Memoization) 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 다시 계산하지 않도록 하는 기술 동적 계획법의 핵심이다. 추가적인 메모리 공간이 필요하다. 2. 동적 계획법 적용 요건 중복 부분 문제 구조 : 동일한 부분 문제들로 구성되어 있는가? 최적 부분 문제 구조 : 최적을 구하는 문제인가? 중복 부분 문제 구조 DP는 큰 문제를 이루는 작은 문제를 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. 순환적 관계를 명시하기 위해 주로 점화식을 사용한다. 이전에 계산된 작은 문제의 해가 다음 문제에서 필요하게 되므로(Overlapping subproblems) 이전의 작은 문제의 해들을 저장 공간에 저장한다. 이전의 해 얻기 위.. 2024. 2. 27. [알고리즘] [18] 최소신장트리 1. 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 신장 트리 : n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리 최소 신장 트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 2. KRUSKAL 알고리즘 간선을 하나씩 선택해서 MST를 찾는다. >> 간선 중심으로 해결하는 알고리즘이므로 간선 리스트로 그래프를 표현한다. 초기에 모든 간선을 가중치 오름차순으로 정렬한다. 가중치가 낮은 간선부터 선택하며 트리를 증가시킨다. >> 사이클이 존재하면 남은 간선 중 그 다음으로 가중치가 낮은 간선을 선택한다. n - 1개의 간선이 선택될 때까지 반복한.. 2024. 2. 22. [알고리즘] [17] 서로소 집합 1. 서로소 집합 (disjoint set) 서로소 (상호 배타)집합은 교집합이 없는 집합들이다. 집합에 속한 특정 멤버를 통해 각 집합을 구별하며 이를 대표자 (representative)라고 한다. 서로소 집합은 연결 리스트 또는 트리로 구현할 수 있다. MakeSet, FindSet, UnionSet 연산을 구현한다. MakeSet(x) // 유일한 멤버 x를 포함하는 새 집합 생성 MakeSet(x) { p[x] 트리를 이용한 서로소 집합 구현에서 사용 >> 두 트리의 depth가 동일하다면 합친 후 전체 트리의 depth += 1이다. Path Compression : FindSet 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다. >> 특정 노드에서 루트까지의 경로를 찾아.. 2024. 2. 21. [알고리즘] [16] 그래프 순회2 1. DFS 시작 지점의 한 방향으로 갈 수 있는 경로까지 깊이 탐색하다가 더 이상 갈 수 없을 때 이전 갈림길 간선으로 되돌아가 다른 정점을 탐색하는 순회 방법 재귀적으로 혹은 스택 자료구조를 이용하여 구현한다. 인접 행렬 또는 인접 리스트를 적절히 사용하여 DFS를 구현한다. 2. Flood Fill 알고리즘 플러드 필 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림 프로그램에서의 '채우기' 도구 또는 지뢰 찾기 등에 사용된다. 4방향 델타 배열 혹은 8방향 델타 배열을 사용할 수 있다. DFS 혹은 BFS로 구현된다. 3. 위상 정렬 (Topology Sort) 유향 그래프의 정점들을 간선의 방향을 거스르지 않도록 나열하는 것 순서가 정해진 작업들.. 2024. 2. 20. 이전 1 2 3 4 5 다음