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

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

이번엔 4장 알고리즘 분석 복습...

아마도 '재귀' 알고리즘 이후에 알고리즘 분석 챕터가 있는 것은,

이 챕터를 좀 더 이해하기 쉽게 하기 위해서인가 보다.

그렇다 하더라고 학교 수업에 들었던 기억을 떠 올리면, 꽤 지루했던게 기억난다.

알고리즘을 사용할 때, 그 알고리즘의 성능을 이해하는 것은 중요하다.

문제를 해결하기 위해 여러가지 알고리즘을 선택할 때도 효율적인 알고리즘을 선택할 수 있고,

또한, 어떻게 적절하게 사용할 것인지 계획을 세우는 데도 도움이 된다.

(책에서는 Garbage Collection 을 예로 들고 있다. 여기에 사용되는 알고리즘은 많은 시간이

 필요하기 때문에, 적당한 순간에만 사용하도록 해야한다. )

최악분석

알고리즘의 최악의 경우에 대한 성능을 분석하는 것이다.

여기에는 4가지 이유가 있는데,

1. 많은 알고리즘이 대부분의 실행에서 최악의 성능을 보인다. 예를들면, 탐색에서 원하는 자료를 찾지 못하는 경우...

2. 많은 알고리즘이 최상의 경우에 똑같은 성능을 보인다.

3. 평균 성능을 계산하는 것이 쉽지 않은 경우가 있다.

4. 최악의 경우는 성능의 상위 한계를 의미한다. 즉 분석 결과보다 더 나쁘게 실행되지는 않는다는 것을 보장한다.

   (내 생각에는 1, 4번이 제일 중요한듯...)

예외적으로 평균 성능을 근거로 해야 하는 경우는 있다. (예를들면, 퀵 정렬 같은 무작위 알고리즘)

O-표기법

이것은 알고리즘의 성능을 정형적으로 표현하는 가장 일반적인 표기법인다.

이것은 알고리즘의 복잡도(complexity)를 표현한다.

자료가 커짐에 따라, 성능이 어떻게 나빠지는지 나타내는지 보여준다고 생각하면 될 듯.

일반적으로 단순하게 아래와 같이 알고리즘의 복잡도를 표시한다.

(실제로는 상수를 포함한 식으로 표시된다. )

( 일반적인 복잡도와 거기에 해당하는 예. 복잡도가 낮은 순으로. n 은 자료의 갯수. )

(증가율을 표한한 그래프. 가로는 n = 자료의 크기, 세로는 T(n) = 알고리즘의 실행 시간을 나타냄.)

* 적절한 그래프 이미지를 찾지 못해 엑셀에서 직접 작업.

  가로/세로 축, 각 그래프 선에 대해서 레이블을 쓰고 싶은데, 옵션을 못 찾겠음.. (없는건지..)

결론

특이한 경우가 아니면, 현업에서 이미 알려진 알고리즘에 대해서 알고리즘 복잡도를 분석할 이유가 없다.

각 알고리즘에 대해서 어느 정도의 성능을 나타내는가를 알고 있으면 된다고 생각한다.

우리가 할 수 있는것은 저 복잡도 계산에서 과다한 상수를 포함하지 않도록 하여

알고리즘이 효율적으로 동작하도록 하는 정도?

중요한 것은 위에서도 언급했듯이, 적절한 알고리즘을 적절하게 사용하는 것이다.

(적어놓고 나니 애매한데, 어쨌거나 현업에서는 여러가지 변수가 존재하니깐...)

최근에 어떤 계기로 미루고 미뤄왔던 알고리즘 공부를 시작했다.

대학 다닐 때 알고리즘 수업 2번 연속 출석미달로 'F' 받았던터라, 늘 찜찜했는데...

알고리즘을 공부하기 위해 선택한 책은 "C 로 구현한 알고리즘" 이다.

왜냐하면... 나름 오라일리 책인데다가... 회사에 굴러다녀서 살 필요가 없어서...;

대충 1장 소개랑 2장 포인터 다루기는 패스하고

3장 재귀부터 복습 겸 글을 남겨본다.

개본적 재귀(recursion)

문제를 자신보다 점점 더 작은 인스턴스들로 정의할 수 있게 하는 강력한 원리이다.

전산에서는 자신을 호출하는 재귀 함수를 사용해서 재귀적으로 정의된 문제들을 해결한다.

Depth 가 깊어지면 스택 오버플로우의 위험이 크다.

현업에서 실제로 이런 형태를 쓰면 안되겠지.

꼬리 재귀(tail recursion)

컴파일러가 최적의 코드를 만들어 낼 수 있는 재귀의 형태이다.

재귀 호출이 함수 몸체의 제일 마지막에 실행되는 문장이고,

리턴값이 다른식에 사용되지 않는 형태이다.

다시 말해면 재귀함수 호출한 뒤에 수행할 명령이 없어야 한다는거?
(이런 형태는 굳이 Iteration 하게 정의해서 풀 수도 있지만,

 재귀 형태가 머랄까.. 좀 더 문제를 푸는 방법을 명확히 나타내는 듯 하다.

 요새는 컴파일러가 똑똑해져서 최적화 옵션을 주면

 꼬리 재귀도 알아서 Iteration 하게 만들어 준다니깐.. 머.)

팩토리얼 값을 구하기 위한 기본적 재귀와 꼬리 재귀

(빨갛게 표시한 부분을 주목)

따로 부연설명은 하지 않겠다.

주의사항

재귀함수는 반드시! 하나 이상의 종료조건이 있어야 하며,

재귀호출이 이 종료조건에 도달할 수 있어야 한다.

그렇지 않다면 스택 오버플로우~

결론

꼬리 재귀에 대한 좀 더 명확한 이해를 할 수 있었고,

이제 더 정확히 알고 사용할 수 있을꺼 같다.

이상 끝.