C 로 구현한 알고리즘 - 2부 자료 구조, 7장 집합(Set)

후... 파폭 버그인지 글쓰다가 날려먹었다.

게다가 실수로 임시저장본까지 날려먹었다.

그냥 다시 쓰자...

집합(Set)

( set.h, set.c )

고등학교 수학시간에 배운 집합을 기억한다면 기본은 다 되었다.

그래도 일단 굳이 정의를 하자면 아래와 같다.

"집합은 서로 다른 원소들의 순서 없는 모임이다."

필요한 인터페이스도 수학시간에 다 배운것들이다.

교집합, 합집합, 차집합, 부분집합인가?, 같은집합인가? 등...

예제에서는 집합을 LInked List 로 구현을 했다.

이러면 탐색에 시간이 많이 걸린다.

(책에서도 예제의 구현은 많이 않은 자료의 집합에 적당하다고 한다)

집합을 구현하는 방법으로 해쉬테이블이나 이진트리를 사용하면

탐색에 걸리는 시간을 줄일 수 있을것이다.

집합의 인터페이스

http://en.wikipedia.org/wiki/Set_%28computer_science%29#Operations

위 링크에서 집합에 필요한 인터페이스를 확인할 수 있다.

집합을 사용하는 것

- 집합 커버(set covering)

이름만으로는 무엇인지 이해하기 어렵다. 책에는 다음과 같이 적혀있다.

조합론(combinatorics)와 자원 선택 등 많은 문제들을 잘 모델링하는 최적화 문제이다.

이 말도 어렵기는 마찬가지이다. 책에서 설명하는 예를 보자.

여러 명의 선수들이 있다. 이 선수들은 각각 임의의 기술들을 가지고 있다.

기술의 종류는 기술1 ~ 기술n 까지 있으며, 이 모든 기술들을 커버(covering)할 수 있는 팀을 구성하고자 한다.

위 문제를 일반화 시켜보면,

집합 S 는 커버할 원소의 집합(기술1 ~ 기술n)이다.

집합 P 는 S 의 부분집합의 집합(선수1 ~ 선수m)이다. 각 선수는 임의의 기술들을 가지고 있다.

집합 C 는 커버집합(모든 기술을 커버할 수 있는 팀)이다.

위와 같이 집합이 사용된다.

여기에서 좀 더 나아가, Set Covering Problem 에 대해서 이야기 해 보자면,

이 문제는 NP-complete 문제이다.

그래서 예제( cover.h, cover.c )에서는 Greedy 알고리즘으로 문제를 해결한다.

- 그래프

그래프를 표현하는 가장 일반적인 방법은 인접한 점들의 리스트를 사용하는 데,

이 인접한 점들의 리스트를 표현하는 한 가지 방법이 인접한 점들을 집합으로 표현하는 것이다.

- 그 외

자료 상관 관계(두 자료의 교집합, 차집합 등을 파악...)

집합에 대한 수학(큰 수에 대한 수학 연산들...)

그래프 알고리즘(정점이나 에지(edge)들을 함께 모으는데 사용...)

관계 대수(데이터베이스 시스템의 이론적인 질의(query) 언어이다...)

기타 등등...

관련 주제들

- 벤 다이어그램

집합의 연산의 결과를 시각적으로 결정하는 데 도음이 되는 그림 표현

- 비트 벡터(Bit-vector) 표현

전체집합이 작고, 그냥 알수 있는(?) 경우에 유용한 집합 표현이다.

전체집합에서 각 원소를 한 비트로 표현하는 것이다.

( 원소의 값을 가지고 있는게 아니고 0/1 로만 표현되므로, 그냥 알수 있는(?) 경우라는 표현을 쓴 것이다 )

- 다중집합(multisets)

원소의 중복을 허용하는 집합이다.

결론

위에서도 말했듯이 고등학교 수학시간에 배운 집합을 기억한다면,

수학적 이론에 대한 것은 더 공부할 필요가 없다.

( 졸업한지가 벌써 ...년이 지났어도 기억하는 걸 보면 어렵지도 않은 내용이다 )

집합은 여러가지 방법으로 구현할 수 있으므로,

해당 상황에 가장 효율적인 방법을 사용하면 되겠다.

http://en.wikipedia.org/wiki/Set_%28computer_science%29#Implementations_2

위 링크에서 집합의 구현에 대한 이야기를 추가로 볼 수 있다.

이상 끝.