분류 전체보기45 [알고리즘] [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. [BOJ] [JAVA] 31423번 신촌 통폐합 계획 31423번: 신촌 통폐합 계획 첫 번째 줄에 대학교의 개수 $N$이 주어진다. $(2 \leq N \leq 500 \, 000)$ 다음 $N$개의 줄의 $i$번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 $s_i$가 주어진다. 주어지는 대학교 www.acmicpc.net Union Find에서 Path Compression과 방식이 유사한 것 같아 작성한다. (아닐수도,,,) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static String[] str; public.. 2024. 2. 21. 이전 1 2 3 4 ··· 12 다음