[Algorithm]집합 - 1. 개념

집합이란?

• 집합은 순서와 중복이 없는 원소를 갖는 자료구조이다.
• 프로그래밍 언어의 Collection(Container) 중 Set이 집합이다.(집합을 영어로하면 Set이다.)
• 일반적인 집합이 필요할 때는 각 프로그래밍 언어에서 제공하는 Set Collection을 사용하면 되지만 특별한 경우 집합 알고리즘을 사용해야 될 경우가 있다.

상호배타적 집합

• 상호배타적 집합은 교집합이 없는 관계를 말한다.
• A의 원소 {1, 3, 4} B의 원소 {2, 5, 6}은 서로 같은 원소가 없기 때문에 상호 배타적 집합이다.
• A의 원소 {1, 3, 4} B의 원소 {1, 5, 6}은 {1} 이라는 교집합이 발생하기 때문에 상호 배타적 집합이 아니다.
• 상호배타적 집합은 그래프 관련 알고리즘을 사용할 때 사이클을 확인하기 위해 많이 사용되고 있으며 이 외에도 많은 알고리즘에 사용된다.
  • 이미지 분할 : 이미지의 영역을 나누는 데 사용.(물체와 배경을 분리할 때 좌표가 겹치지 않게 하기 위해)
  • 게임 개발 : 캐릭터들이 서로 겹치지 않도록 하는 데 사용.(스타크래프트1은 유닛이 겹쳐지지 않고, 스타크래프트 2는 유닛이 겹쳐진다. 스타2는 유닛에 상호배타적 집합 알고리즘을 사용하지 않았다.)
  • 이외에도 도로 네트워크 구성, 클러스터링 작업 등 특정 데이터가 겹치지 않아야 할 때 사용하면 유용하다.
• 서로 다른 집합을 합치기 위한 Union(합치기)과 대표 원소를 찾기 위한 Find가 집합 알고리즘의 필수 요소이다.

집합 표현하기

• 집합은 배열을 활용해 트리형태로 표현하고, 각 집합에는 대표 원소가 존재 한다.
• 대표 원소는 집합의 원소 중 집합을 대표하는 역할을 하고 트리로 구현했을 때 루트 노드가 대표 원소가 된다.
• 배열을 활용한 트리로 집합을 구현했을 때 배열의 인덱스가 원소의 값, 배열의 값은 부모 원소의 인덱스를 의미 한다. (배열의 인덱스 = 원소, 배열의 값 = 부모 인덱스, 즉 Array[원소4], Array[4] = 부모 인덱스)
• 배열에서 대표 원소(루트 노드)의 값은 자신의 인덱스 이다.

< 집합 A의 트리 >

< 배열로 표현된 집합 A의 트리 >

• 집합 A 설명
  • 집합 A는 { 2, 3, 4, 7, 8, 11, 6, 9 }의 원소를 가진다.
  • 집합 A의 대표 원소는 2이고 대표 원소의 값은 자기 자신이다. (인덱스도 빨강색, 값도 빨강색 즉, Array[2] = 2)
  • 원소3 = Array[3] 이고 Array[3]의 값은 부모 노드의 인덱스 2 이다. (배열의 인덱스 자체가 원소3 이고 배열의 값은 부모의 포인터다.)
  • 원소4 = Array[4] 이고 Array[4]의 값은 부모 노드의 인덱스인 3 이다. (Array[4] = 3)
  • 원소7 = Array[7] 이고 Array[7]의 값은 부모 노드의 인덱스인 3 이다. (Array[7] = 3)
  • 원소8 = Array[8] 이고 Array[8]의 값은 부모 노드의 인덱스인 7 이다. (Array[8] = 7)
  • 원소11 = Array[11] 이고 Array[11]의 값은 부모 노드의 인덱스인 8 이다. (Array[11] = 8)
  • 원소6 = Array[6] 이고 Array[6]의 값은 부모 노드의 인덱스인 2 이다. (Array[6] = 2)
  • 원소9 = Array[9] 이고 Array[9]의 값은 부모 노드의 인덱스인 6 이다. (Array[9] = 6)

배열 하나에 여러개의 집합 표현 하기

• 상호 배타적 집합일 경우 배열 하나에 여러개의 집합을 표현할 수 있다.

< 집합 A와 집합 B >

< 배열로 표현한 집합 A와 집합 B >

• 집합 A는 { 2, 6, 9 } 원소를 가지고, 집합 B는 { 3, 4, 7, 8, 11 } 원소를 가진다.
• 집합 A의 대표 원소는 { 2 }, 집합 B의 대표 원소는 { 3 } 이고 대표 원소는 자기 자신의 인덱스를 값으로 가진다.

집합 A의 배열

• [원소9 -> 원소2], [원소6 -> 원소2], [원소2 -> 원소2]-대표

집합 B의 배열

• [원소11 -> 원소8], [원소8 -> 원소7], [원소7 -> 원소3], [원소4 -> 원소3], [원소3 -> 원소3]-대표

다음 글

[Algorithm]집합 - 2. 구현