[알고리즘] Set Cover

Set Cover

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Set Cover란?

Set cover는 특정 Set(=집합)이 존재한다고 가정했을 때, Sub sets(=부분 집합)들이 합쳐져 특정 set을 나타낼 수 있는지에 대해서 확인하는 과정을 Set cover라고 한다.

Set은 집합을 의미하고 Cover는 덮는다 또는 엄호한다 다른 표현으로는 대체할 수 있다는 의미로 사용된다.

따라서 Set cover는 말 그대로 여러 sets들이 합쳐져서 하나의 특정 Set를 나타낼 수 있는지에 대한 내용이다.

 

# Set Cover를 배우는 이유

Set cover라는 표현이 어색할 따름이지 이미 대부분 Bro들은 수학 시간에 배웠던 내용이다.

이렇게 간단해 보이는 내용을 다시 살펴보는 이유는 언제나 그랫듯이 최종적인 목적은 알고리즘의 이해다.

Set cover에 대한 원리를 이해하고 Set cover problem을 살펴보며, 이를 통해 computing 과정에서 사용할 수 있는 알고리즘에 대해서 이해하고 활용이 가능하다.

예를 들자면, Set cover에 대한 이해를 통해 programming에서 응용이 가능하다면, 특정 결괏값을 산출한다고 했을 때 모든 과정을 구현할 필요 없이 필요한 과정만 골라서 결과 산출이 가능하다.

이때 모든 조건이 충족되거나 모든 노드들 간의 데이터 송수신이 완료되지만 효율적인 프로세스 작업을 골라서 실행시킬 수 있다.

이것을 이해하는 과정 중에 하나가 바로 Set cover이며, Set cover를 통해 Set cover problem을 이해하고 최종적으로 Set cover의 특징을 활용한 알고리즘을 활용하는 것이다.

사실상 대부분의 컴퓨팅 문제 원리는 효율적인 알고리즘 사용과 연구 개발을 하기 위한다고 이해하면 된다.

 

# Set Cover 예시

본론으로 돌아와서 Set cover에 대한 예시를 살펴보며 과거에 배운 기억을 더듬어 보자.

예를 들어서 아래와 같은 특정 Set이 존재한다고 가정해보자.

U = {1,2,3,4,5,6,7,8,9}

S1 = {1,2,3}
S2 = {1,4,5,8}
S3 = {2,3,4,5}
S4 = {6,7,8,9}
S5 = {2,3,5,8,9}

 

여기서 U라는 Set를 S1부터 S5까지의 Set들을 통해 나타낸다고 한다면 아래와 같은 결과를 얻을 수 있다.

OPTION A: {S1, S2, S4} IS A SET COVER.
OPTION B: {S2, S3, S4} IS A SET COVER.
OPTION C: {S3, S4, S5} IS NOT A SET COVER.

 

OPTION A 와 OPTION B는 각각의 SUB SET들을 합쳤을 때 U SET을 나타낼 수 있다.

반면에 OPTION C는 ELEMENT 중에서 1이 빠졌기 때문에 U SET을 나타낼 수 없다.

따라서 OPTION A와 OPTION B는 SET COVER에 해당하지만, OPTION C는 SET COVER가 아니다.

---

# In conclusion, 3줄 요약

1. SET COVER는 수학에서 집합을 생각해보면 이해하기 쉽다.

2. SET COVER의 원리를 이해하여 알고리즘으로 활용해보자.

3. SET COVER는 특정 SET에 대한 모든 ELEMENTS를 나타낼 수 있어야 한다.

---