그래프 이론 서로소 집합 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온- 파인드 자료구조이다. 서로소 집합 자료구조 union 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find 특정 한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 정보가 주어졌을때 트리 자료 구조를 이용해서 집합을 표현한다. 서로소 집합 알고리즘 각 노드는 자기 자신을 부모 노드로 갖도록 초기화 한다. union을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노트 A'와 B'를 각각 찾는다. A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가르키도록 한다.) 트리가 한쪽으로 기울어지는 것을 방지하기 위해서..

동적계획법 (Dynamic Programming) 동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 분할 정복과 다른 점은 문제들이 서로 영향을 미치고 있다는 점이다. 동적 계획법의 경우 한 번 해결한 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 가져다 쓰는 것이다. 동적 계획법은 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 구현하는 방식에는 2가지가 있는데 탑 다운 방식과 바텀 업 방식이다. 탑다운 방식은 재귀 함수를 이용한다. 큰 문제를 해결하기 위해 작은 ..