Azza's Blog

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

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

그냥 다시 쓰자...

집합(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

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

이상 끝.

스택과 큐도 링크드 리스트만큼 쉽다.

컨셉만 이해하고 넘어가면 될듯.

스택(Stack)

( stack.h, stack.c )

스택은 자료를 LIFO(last-in, fist-out)방식으로 처리한다.

가장 쉬운 예로는 접시가 있겠다.

접시를 쌓고(push), 접시를 꺼내는(pop) 행동에서

일반적으로 가장 마지막에 쌓은 접시를 제일 먼저 사용한다.

이것이 LIFO 인 것이다.

대표적인 사용의 예는

C 에서 함수 호출, 추상 스택 머신 등이 있다.

큐(Queue)

( queue.h, queue.c )

큐는 스택과 반대로 FIFO(fist-in, first-out)방식으로 자료를 처리한다.

줄을 서서 서비스를 받기위해 기다리는 사람들을 생각하면 되겠다.

대표적인 사용의 예는

세마포어에서 자원을 기다리는 프로세스들을 큐로 관리하는 것,

이벤트 처리, 생산자-소비자 문제등이 있다.

기타

좀 더 확장된 자료구조로는 다음과 같은 것들이 있다.

데크(double-ended queues: deques)는 head / tail 양쪽에서 삽입과 삭제가 가능한 큐이다.

원형 큐(circular queues)는 tail을 갖지 않고 마지막 항목이 head 로 연결되는 큐이다.

결론

스택과 큐는 간단하지만 매우 중요한 자료구조이다.

큐의 경우, 일반적으로 프로세스/쓰레드 간 데이터를 주고 받는데 많이 사용하는데,

두 프로세스/쓰레드가 동시에 큐에 엑세스하지 않도록 하는 장치가 필요할 것이다.

별 내용이 없네... 머 쉬운거니깐.

1부 준비가 끝나고 2부 자료구조의 시작이다.

알고리즘과 자료구조는 뗄 수 없는 관계니깐...

그 첫 번째로 연결 리스트(linked list)다.

연결 리스트라니.. 번역이 좀 그렇다.. 한글+영어가 좀 어색하네..

그냥 아래에서는 영문 그대로 적겠다.

솔직히 전산쪽 용어들은 오히려 그게 더 명확하니깐...

이 책에서 사용하는 소스코드들은

http://www.hanb.co.kr/exam/1063/

에서 다운받을 수 있다. 각 장에서 사용하는 소스파일 명은 중간중간 적어 두겠다.

링크드 리스트에는 다음과 같은 것들이 있다.

• 싱글 링크드 리스트 (single-linked list)

단일 연결 리스트. 각 항목들이 하나의 포인터로 연결된 가장 단순한 리스트.

(출처: http://en.wikipedia.org/wiki/Linked_list )

• 더블 링크드 리스트 (double-linked list) - 이중 연결 리스트

각 항목들이 두개의 포인터로 연결된 리스트. 양쪽 방향으로 포인터를 가지고 있다.

(출처: http://en.wikipedia.org/wiki/Linked_list )

• 서큘러 리스트 (circular list) - 원형 리스트

마지막 항목의 포인터가 NULL 대신에 첫 항목을 가리키는 연결 리스트. 리스트를 원형으로 순회할 수 있다.

(출처: http://en.wikipedia.org/wiki/Linked_list )

링크드 리스트를 사용하는 예에는 다음과 같은 것들이 있다.

메일링 리스트, 리스트(GUI 컴포넌트), 다항식, 메모리 관리(할당 가능한 메모리 영역 관리), LISP,

다른 자료구조들의 구현(스택, 큐, 집합, 해시 테이블, 그래프 등...)

예제 파일들
( list.h, list.c / dlist.h, dlist.c / clsit.h, clist.c )

상황에 따라 적절한 인터페이스가 추가/삭제가 될 수 있겠지만,

예제의 헤더 파일에서 기본적으로 필요한 인터페이스를 확인할 수 있다.

결론

책에서는 꽤 길게 설명을 해 두었지만,

링크드 리스트는 제일 쉬운 자료구조이다.

딱히 장황하게 적을 필요가 없다고 본다.

여기서부터 각 인터페이스에 대한 복잡도를 표시해 두었는데,

비단 링크드 리스트 뿐만 아니라, 다른 자료 구조에 대한

인터페이스의 복잡도도 알아두면 효율적으로 프로그램을 작성하는데 도움이 될 것이다.

Linked List 는 종종 Array 와 같은 다른 형태의 리스트와 비교되는데,

http://en.wikipedia.org/wiki/Linked_list

위 사이트의 글을 참고하면 되겠다.