[서울대학교 논자시 준비] 알고리즘 : chapter 8 집합의 처리

문병로 교수님의 '관계 중심의 사고법 쉽게 배우는 알고리즘 개정판'을 보고 작성합니다. 1. 연결리스트를 이용한 집합의 처리 연결리스트를 이용해 집합을 처리하면 각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다. 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두개의 포인터가 있습니다. 각 집합의 대표원소는 연결 리스트의 맨 앞에 있는 원소가 된다. 각 집합은 tail이라는 변수를 갖고 있다. 상호배타적 집합의 관리를 위해 세가지 연산이 필요하다. 1. Make-Set(x) : 원소 x로만 구성된 집합을 만든다 - 상수시간이 든다 2. Find-Set(x) : 원소 x를 가진 집합을 알아낸다 - 역시 상수 시간이 든다. (정상수) 왜 상수 시간이 드냐면 Find-Set은 ..

2023.08.17