알고리즘 강좌

 

2004-10-29 오후 5:22:51   /  번호: 6962  / 평점:  (8.1) category: VC++ 일반  /  조회: 7,257

알고리즘 강좌(1) 입니다. 볼만한지...ㅡㅡ;? 이승우 / sunmind

목차 1) Introduction 1.1) Mathematical definition 1.1.1) logarithm, factorial 1.1.2) Time complexity 1.1.3) C/C++ example 1.2) Data structures 1.2.1) Stack 1.2.2) Queue 1.2.3) Linked list 1.2.4) Binary tree 1.2.5) Priority queue 1.2.6) Binary heap 1.2.7) Heapsort 1.2.8) Disjoint set 1.3) C++ Standard Template Library 2) Searching 2.1) Searching 2.1.1) Data Representations 2.1.2) Binary Search 2.1.3) DFS 2.1.4) BFS 2.2) Topological Sort 2.3) Backtracking 3) Divide and Conquer 3.1) Examples 3.1.1) Example : A Tiling Problem 3.1.2) Example : Finding a Closest Pair of Points 3.2) Implementations 3.2.1) Mergesort 3.2.2) Strassen's Matrix Product Algorithm 4) Sorting and Selection 5) Greedy Algorithms 6) Dynamic Programming 7) Text Searching 8) P and NP 9) Heuristic Algorithms Chapter 1) Introduction 그동안 알고리즘과 자료구조에 대해 배우면서 느낀 것은 국내에서 넷상으로 배우기가 매우 어렵다는 것이었습니다. 지식의 파편은 많이 널려있었습니다만, 체계적으로 종합해서 강좌를 올려놓은 사이트는 없었습니다. 서적도 마찬가지입니다. Sorting이면, Sorting만 따로, 자료구조면 자료구조만 따로. 이런 식으로 되어있는 서적이 대부분이더군요. 정렬하는 알고리즘이라고 한데 묶어 같은 카테고리에 넣으면 안됩니다. Divide and Conquer냐, Greedy Algorithm 이냐에 따라, 문제를 풀기 위한 접근 방식에 따라 알고리즘을 구분지어야 하며, 자료구조는 알고리즘에서 제시하는 문제를 효율적으로 해결하기 위한 방법으로 배워야 합니다. 단지 for와 if만 써서 잘 알려진 Shortest path problem을 푸는 게 아니라, Binary min heap 자료구조를 쓰면 이 문제를 훨씬 빠르게 풀 수 있음을 알아야 합니다. 이제부터 제가 올릴 강좌는 알고리즘의 Time complexity 계산부터 시작해서 제가 배웠던 내용해 대한 것입니다. 내용에 오류가 있다면 E-mail로 알려주시기 바랍니다. 1.1) Mathematical definition 1.1.1) logarithm, factorial 알고리즘의 증명에 사용되는 로그는 거의 2를 밑으로 하는 로그라 보시면 됩니다. 이 강좌에서 Time complexity를 증명하는데 쓰는 로그는 lg라고 정의하고, 이는 2를 밑으로 하는 로그라고 하겠습니다. 그냥 log라고 쓰면 상용 로그를 의미하는 겁니다. (하지만 상용로그는 거의 쓰이지 않습니다.) 로그의 정의는 아래와 같지요. a^x = b <==> log_a(b) = x factorial은 n!와 같이 나타내며, n!의 계산법은 아래와 같습니다. n! = n * (n-1) * (n-2) * ... * 1 알고리즘에서 logarithm과 factorial이 중요한 이유는 생각보다 lg와 n!의 Time complexity를 가지는 알고리즘이 많기 때문입니다. 알아두시는게 좋죠. 1.1.2) Time complexity 어떤 Algorithm의 효율성을 논할 때 쓰이는 개념입니다. quicksort의 time complexity를 제외하곤 대부분의 경우 신뢰할 수 있는 개념이지요. 일반적으로 Time complexity가 개선되면 이를 프로그램으로 코딩하고 실행해보면 대부분 실행속도가 나아짐을 알 수 있습니다. Time complexity 계산을 위해선 먼저 Algorithm의 lower bound와 upper bound를 알아야 합니다. lower bound는 일반적인 문제를 풀기 위해 '최소한' 걸리는 시간을 의미하며, upper bound는 그 문제를 풀기 위해 '최대한' 걸리는 시간을 의미합니다. Time complexity를 구하기 위해선 알고리즘의 lower bound와 upper bound가 얼마나 되는지 증명해야 합니다. 만약, 어떤 문제를 풀기위해 n^2 + 60 * n 만큼의 루프를 돌아야 하는 알고리즘이 있다고 가정해봅시다. (단, n은 풀어야 할 문제의 요소의 갯수라고 가정합니다.) 이 알고리즘이 문제를 풀기 위해선 n이 1일때 1 + 61 만큼의 루프를 돌아야 하지만, n이 100일 경우엔 10,000 + 6000, n이 10000일 경우엔 100,000,000 + 60,000의 루프를 돌아야 합니다. 즉, 뒤에 붙는 60 * n의 루프는 이 알고리즘에서 n이 무한히 커질수록 상대적으로 의미가 없어진다고 할 수 있습니다. y = nx + a 함수의 기울기는 절대로 y = nx^2 + a 함수의 기울기를 넘어설 수 없다는 의미입니다. 결론적으로 알고리즘의 lower bound와 upper bound 그리고 Time complexity를 구하려면 중첩된 루프에 대한 복잡도만 고려하면 된다는 의미입니다. 그렇다면 이 알고리즘의 lower bound는 얼마일까요? 알고리즘의 lower bound에 대한 정의는 다음과 같습니다. - 모든 n >= x 을 만족하는 n에 대해, f(n) >= x * g(n) 인 관계를 만족하는 함수 f(n)은 lower bound로 g(n)을 가진다. 이 정의에 따라 위 알고리즘의 식 n^2 + 60 * n 은, 아래와 같은 식을 만족합니다. - 모든 n >= 1인 정수 n에 대해, n^2 + 60 * n >= n^2 upper bound에 대한 정의는 아래와 같습니다. - 모든 n >= x 을 만족하는 n에 대해, f(n) <= x * g(n) 인 관계를 만족하는 함수 f(n)은 lower bound로 g(n)을 가진다. 이 정의에 따라 위 알고리즘의 식 n^2 + 60 * n 은, 아래와 같은 식을 만족합니다. - 모든 n >= 1인 정수 n에 대해, n^2 + 60 * n <= n^2 + 60 * n^2 = 61 * n^2 즉, lower bound와 upper bound 모두 n^2가 되므로, 이 알고리즘의 Time complexity는 O(n^2)가 됨을 알 수 있습니다. 여기서 짚고 넘어가야 할 것은, 알고리즘의 Time complexity 계산에 있어 앞에 붙는 계수는 신경쓸 필요가 없으며 기울기의 증감을 나타내는 지수가 중요하다는 것입니다. 모든 알고리즘의 Time complexity에는 계수가 붙지 않습니다. 아래는 보통 알고리즘이 보여주는 Time complexity 표입니다. 1.1.3) C/C++ example Time Complexity C++ code O(1) n = x; O(lg(n)) int i = n; while(i >= 1) { x = x + 1; i = i / 2; } O(n) for(i = 0; i < n; i++) { x = x + 1; } O(n2) for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { x = x + 1; } } O(cn), c > 1 void loop(int i, int n) { if(i < n) { i++; loop(i, n); loop(i, n); } } O(n!) void loop(int n) { for(i = 0; i < n; i++) { loop(n - 1); } } 1.2) Data structures 여기서 설명하는 자료구조는 간단한 것들이지만, 앞으로 설명할 알고리즘에서 자주 등장하게 되고 또 써먹게 될 자료구조들 이므로 꼭 알아두셔야 합니다. 1.2.1) Stack Stack은 나중에 들어간 것이 먼저 나오는 자료구조 형태입니다. 1 <- 23 1,23 <- 45 1,23,45 위와 같은 순서로 데이터가 입력되었다면, 1,23,45 1,23 -> 45 1 -> 23 위와 같은 순서로 데이터가 빠져나가는 자료구조입니다. 그러면 지금부터 간단하게 구현해보도록 하겠습니다. 언어는 pseudo code입니다. stack_init() { stack_pointer = -1 } 스택을 초기화하는 stack_init 함수입니다. -1은 스택에 아무것도 쌓이지 않은 상태를 의미합니다. 여기서 init_stack라고 하지 않고 stack_init라 붙인 이유는 무엇일까요? 그것은 stack라고 앞에 씀으로서 헷갈리지 않고 한데 모아서 관리하기 위함입니다. init_stack() pop_stack() push_stack() 위 선언과 비교해 볼때, stack_init() stack_pop() stack_push() 이쪽이 훨씬 보기 좋음을 알 수 있습니다. 얘기가 잠깐 딴데로 샜는데요, 다음 코드를 보겠습니다. stack_empty() { return stack_pointer == -1 } 스택이 비었는지 알려주는 함수입니다. 이렇게 하면 stack이 비었을 경우 1을 리턴하며 그렇지 않으면 0을 리턴합니다. stack_push(val) { stack_pointer = stack_pointer + 1 data[stack_pointer] = val } 스택에 데이터를 하나 삽입하는 함수입니다. 스택 포인터가 1 증가하면서 데이터를 저장하게 됩니다. stack_pop() { stack_pointer = stack_pointer - 1 } 스택에서 데이터를 하나 꺼내서 버리는 함수입니다. stack_top() { return data[stack_pointer] } 현재 스택이 가리키고 있는 데이터 하나를 받아올 수 있는 함수입니다. 항상 stack에선 맨 마지막에 삽입된 데이터를 가져옴을 알 수 있습니다. stack의 장점은 모든 함수의 Time complexity가 O(1)이므로 대단히 빠른 자료구조라는데 있습니다. 그리 어렵지 않은 자료구조이므로 이만 하고 넘어가도록 하겠습니다. 1.2.2) Queue Queue는 먼저 들어간 것이 먼저 나온다는 개념의 자료구조입니다. Stack보다는 구현하기가 조금 더 복잡하지만 역시 그리 어렵지 않습니다. 1 <= 23 1,23 <= 45 1,23,45 위와 같은 형태로 자료가 입력되었다고 할 때, 아래와 같이 데이터가 빠져나오게 됩니다. 1,23,45 => 1 23,45 => 23 45 개념은 매우 쉽지요? 이제 pseudo code로 구현해 보도록 하겠습니다. queue_init() { queue_sp = queue_fp = -1 } Queue는 꺼내올 데이터가 있는 주소와 데이터가 저장되는 주소가 다르므로 주소를 가리키는 번호 또한 두 개가 있어야 합니다. queue_fp는 데이터가 저장될 주소를, queue_sp는 데이터를 꺼내올 주소를 나타냅니다. stack과 마찬가지로 비었을 경우 초기값으로 -1로 정해둡니다. queue_empty() { return queue_fp == -1 } queue_empty()는 Queue가 비었다면 1을 리턴하고, Queue에 데이터가 하나라도 있다면 0을 리턴하게 됩니다. enqueue(val) { if(queue_empty()) queue_sp = queue_fp = 0 else { queue_fp = queue_fp + 1 if(queue_fp == SIZE) queue_fp = 0; } data[queue_fp] = val } dequeue() { if(queue_sp == queue_fp) queue_sp = queue_fp = -1 else { queue_sp = queue_sp + 1 if(queue_sp == SIZE) queue_sp = 0 } } Queue에 데이터를 삽입하거나 버리는 enqueue, dequeue 함수입니다. enqueue 할 때는 데이터를 저장하는 주소가 하나 증가하고, 반대로 데이터를 버릴 땐 데이터를 꺼내올 주소를 하나 증가시킴을 알 수 있습니다. 마지막으로 Queue의 현재 포인터가 가르키고 있는 데이터를 읽어오는 queue_front 함수입니다. queue_front() { return data[queue_sp] } Queue는 구현하기가 stack 보다는 약간 까다롭지만, 유용한 자료구조 입니다. Queue도 모든 함수의 Time complexity 가 상수가 됨을 알 수 있습니다. 1.2.3) Linked list list는 배열과 비슷한 자료가 주욱 나열되어 있는 형태 (linear하다고 합니다.) 의 자료구조입니다. 다만, 배열보다 공간 활용도에 있어 보다 효율적입니다. 예를 들어, data : 1 2 3 4 5 6 index : 1 2 3 4 5 6 위와 같은 형태의 배열이 있다고 가정해 봅시다. 위 배열에서 4번째 인덱스에 있는 4를 삭제하고 싶을 때, 배열이라면, data : 1 2 3 -1 5 6 index : 1 2 3 4 5 6 위와 같이 없애고 싶은 인덱스를 특정한 숫자로 표기하거나, data : 1 2 3 5 6 x index : 1 2 3 4 5 6 위와 같이 뒤에 있는 데이터를 앞으로 쭉 복사하는 방법이 있지만, 둘 다 이미 잡아놓은 인덱스 하나를 낭비하는 결과를 초래합니다. 그러나 list를 사용하게 될 경우 아래와 같이 4와 5, 5와 6사이의 연결을 끊고 새로 4와 6사이의 연결을 만들면 되므로 이러한 불필요한 낭비를 없앨 수 있습니다. data : 1 -> 2 -> 3 -> 4 ------> 6 index : 1 2 3 4 5 6 이제 list의 pseudo 코드를 봅시다. list_insert(val, pos) { temp = new node temp.data = val temp.next = pos.next pos.next = temp } 함수의 argument로 들어오는 val과 pos는 각각 새로 들어올 데이터와 list를 의미합니다. 정확하게 말하자면 pos는 새로 데이터를 입력시킬 list가 현재 가리키고 있는 포인터를 의미하죠. list_insert 함수를 사용할 경우 list는 아래와 같은 과정을 거쳐 데이터를 삽입시킵니다. pos(1) -> pos(2) -> pos(3) -> ... -> NULL 위와 같은 list에 val 값을 입력시키기 위해 temp를 메모리 상에 새로 만들어서 여기에 val값을 데이터로 삽입하고, 원래 있던 pos를 링크시킵니다. 그러면 아래와 같이 됩니다. pos(1) -> temp -> pos(2) -> pos(3) -> ... -> NULL 이것이 singly linked list의 기본 원리입니다. 데이터의 삭제는 매우 쉽습니다. stack와 마찬가지로 마지막에 입력된 데이터 하나만 삭제할 수 있습니다. list_delete(pos) { pos.next = pos.next.next } delete되는 과정은 위에서 설명했으므로 생략하도록 하겠습니다. list_print(start) { while(start != null) { println(start.data) start = start.next } } 위는 list의 포인터를 받아서 내용을 출력해주는 함수입니다. 위에서 바로 원래 사용하고 있는 리스트의 포인터를 argument로 넣었다간 list에 든 내용이 모두 날아갈 수가 있으므로 start = pos 와 같이 복제한 포인터를 argument로 넣어야 하겠죠? singly linked list 말고도 양방향으로 연결된 doubly linked list와 list의 처음과 끝 포인터가 서로 연결된 circular linked list도 있으나 여기선 설명을 생략하겠습니다. singly linked list를 완벽히 이해하셨다면 응용하는 건 식은 죽 먹기나 다름이 없으니까요. 다음 강좌는 시간 나는대로 올리도록 하겠습니다. 생각보다 쓰는게 쉽지 않네요. ------------------------------------------------------------------------------------------------- 이 강좌는 거의 Richard Johnsonbaugh, Marcus Schaefer 공저 Algorithms 책(엄청 좋은 책입니다 ㅡㅡ;) 을 기본으로 해서 만들어졌음을 미리 밝혀둡니다. 다만 번역서는 아닙니다. 이 책을 보고 필자가 이해한 것에 관해서 적은 것이며, 따라서 저작권은 필자에게 있습니다. (1) 특정 단체의 무단 복제를 금합니다. (2) 개인이 복제할 경우, 출처를 표기해주셔야 합니다. (3) 어떠한 경우라도 글 전체 내용에 대한 수정을 가하는 것은 금지합니다.

이 글에 평점 주기: 0점 1점 ■ 2점 ■■ 3점 ■■■ 4점 ■■■■ 5점 ■■■■■ 6점 ■■■■■■ 7점 ■■■■■■■ 8점 ■■■■■■■■ 9점 ■■■■■■■■■

2004-10-29 17:37:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...  junnyrocker / gash400         1장은 완전히 수치해석학같네여~~^^ ln(자연로그)의 밑은 2가 아니라 e입니다...다..아시는거겠지만요~~

2004-11-01 01:10:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...   이재익 / shell         만화로 풀어가는 알고리즘강좌는 안나올까요? 흐흑..ㅠ_ㅠ

2004-11-04 15:40:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...  정민성 / jms7446         위에 나온 로그는 자연로그를 의미하지 않는것 같은데요.. 그래서 ln이 아니라 lg라고 표현하시었고.. time complexity에서 로그의 밑은 큰 의미를 지니지 못하는데다, 보통 바이너리로 커지는 알고리즘이 많은 관계로 편이상 2를 밑으로 하는 로그를 쓰는것이라고 이해하고 있습니다...

2004-11-05 17:27:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...   canelia / j3969         n-log-n 도.. C 코드 예문 좀 들어주세요 ㅠㅠ

2004-11-12 17:03:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...  홍승환 / hshthsh         n-log-n for(j=0; j<n; j++) for(int i = n; i>=1; i = i / 2){ }

2005-04-08 17:03:00  Re:  알고리즘 강좌(1) 입니다. 볼만한지...  미누푸 / zzabcd         한번 이해해보려구 보고있습니다. 시작은 이해가 잘되어서 다행인데....끝까지 잘 이해가 되었으면....^^;;;

 

2004-10-31 오후 7:14:07   /  번호: 6963  / 평점:  (8.4) category: VC++ 일반  /  조회: 5,075

알고리즘 강좌(2) 이승우 / sunmind

목차 1) Introduction 1.1) Mathematical definition 1.1.1) logarithm, factorial 1.1.2) Time complexity 1.1.3) C/C++ example 1.2) Data structures 1.2.1) Stack 1.2.2) Queue 1.2.3) Linked list 1.2.4) Binary tree 1.2.4.1) Preorder traversal 1.2.4.2) Postorder traversal 1.2.4.3) Inorder traversal 1.2.4.4) Stack calculator 1.2.4.5) Binary search tree 1.2.5) Heap 1.2.5.1) Heapsort 1.2.6) Disjoint set 1.2.6.1) Improvement 1.3) C++ Standard Template Library 2) Searching 2.1) Searching 2.1.1) Data Representations 2.1.2) Binary Search 2.1.3) DFS 2.1.4) BFS 2.2) Topological Sort 2.3) Backtracking 3) Divide and Conquer 3.1) Examples 3.1.1) Example : A Tiling Problem 3.1.2) Example : Finding a Closest Pair of Points 3.2) Implementations 3.2.1) Mergesort 3.2.2) Strassen's Matrix Product Algorithm 4) Sorting and Selection 5) Greedy Algorithms 6) Dynamic Programming 7) Text Searching 8) P and NP 9) Heuristic Algorithms 1.2.4) Binary Tree Tree는 앞으로 가장 많이 접하고, 또 자주 쓰이게 될 자료구조입니다. 이곳 저곳 쓰이는 곳도 많고 성능도 뛰어나기 때문입니다. 여기선 Tree 중 하나인 Binary Tree에 대해 알아 보겠습니다. Binary Tree를 구성하는 단위를 parent와 child라고 하는데, parent는 위쪽에 있는 데이터를, child는 parent에 딸려 있는 데이터를 의미합니다. 하나의 parent는 하나 혹은 둘의 child를 가지거나, 아예 child를 가지고 있지 않을수도 있습니다. 아래 그림을 보면 무슨 말인지 이해가 가실 겁니다. 이 Binary Tree의 데이터를 추적하는 방법에는 세 가지가 있습니다. preorder, postorder, inorder이 그것인데요, 이것을 알아야 되는 이유는 이를 활용하여 계산기나 컴파일러를 만들 수 있기 때문입니다. 예를 들어, 연산자 우선 순위에 따라 계산식을 scanning 하며, 이 식으로 구성된 Binary Tree를 만들고 이를 postorder로 추적하며 계산하면 계산된 결과가 나오고, 계산식을 inorder 방식으로 추적하면 원래의 식이 나오죠. 이래저래, 배울 것도 참 많지 않습니까? 그럼 부가 섹션을 통해 이 방식들에 대해 알아봅시다. 1.2.4.1) Preorder Traversal Preorder Traversal은 Binary Tree에서 먼저 parent의 데이터를 탐색하고, 그 다음에 좌측의 child, 우측의 child 이런 식으로 탐색해가는 추적법입니다. 아래 그림을 보면 쉽게 이해가 가실 겁니다. 대응되는 pseudo code는 아래와 같습니다. preorder(root) { if(root != null) { // visit root preorder(root.left) preorder(root.right) } } 1.2.4.2) Postorder Traversal Postorder Traversal은 Binary Tree에서 좌측의 child, 우측의 child, parent 순으로 탐색을 해나가는 방법입니다. 아래 그림을 보면 이해가 쉬울 것 입니다. 대응되는 pseudo code는 아래와 같습니다. postorder(root) { if(root != null) { postorder(root.left) postorder(root.right) // visit root } } 1.2.4.3) Inorder Traversal Inorder Traversal은 Binary Tree에서 좌측의 child, parent, 우측의 child 순으로 탐색을 합니다. 아래 그림을 보면 이해가 쉬울 것 입니다. 대응되는 pseudo code는 아래와 같습니다. inorder(root) { if(root != null) { inorder(root.left) // visit root inorder(root.right) } } 1.2.4.4) Stack calculator 앞서 소개한 Postorder, Inorder traversal을 이용하면 간단한 스택 계산기를 구현할 수 있습니다. 수식의 Parsing tree에서 Postorder traversal을 수행하면 우리가 실제로 하는 계산 순서대로 토큰들이 추출되며, Inorder traversal을 수행하면 원래의 식이 나오게 됩니다. 이번 섹션에선 간단한 사칙연산을 수행하는 스택 계산기를 구현하는 방법에 대해 알아 보도록 하겠습니다. 원래 수식을 Scanning 하고 Parsing 해서 Tree를 만들기 위해선 lex, yacc가 있어야 하나 이것을 소개하는 건 이 강좌의 범위를 벗어나므로 생략하고 이미 Binary Tree가 만들어져 있다고 가정하고 스택 계산기를 만들어 보겠습니다. 2 * 3 + 8 / 4 를 Tree로 만들어 이를 Array에 삽입하면 아래와 같이 됩니다. 이제 Postorder 순서대로 Tree에서 데이터를 추적해서 스택에 삽입합니다. 그러면 스택에는 데이터가 아래와 같이 쌓이게 됩니다. - Step 1 stack_num = {2} stack_chr = {} - Step 2 stack_num = {2,3} stack_chr = {} - Step 3 stack_num = {2,3} stack_chr = {*} stack_chr에 연산자 *가 들어오게 되었다면 stack_num에서 이미 삽입된 숫자 두 개와 이 연산자를 사용하여 결과값을 냅니다. 그러면 2*3해서 결과가 6이 나오는데요, 이를 다시 스택에 삽입합니다. - Step 4 stack_num = {6} stack_chr = {} - Step 5 stack_num = {6,8} stack_chr = {} - Step 6 stack_num = {6,8,4} stack_chr = {} - Step 7 stack_num = {6,8,4} stack_chr = {/} /연산자가 들어오게 되었다면 다시 stack에서 이전에 입력된 데이터 2개를 꺼내서 계산, 결과값 2를 얻어냅니다. 그리고 이를 다시 stack_num에 삽입합니다. - Step 8 stack_num = {6,2} stack_chr = {} - Step 9 stack_num = {6,2} stack_chr = {+} 마지막으로 + 연산자가 스택에 쌓이면 이전과 마찬가지로 stack_num에서 데이터를 두 개 꺼내와 계산하고 끝냅니다. 연산을 마치면 스택은 모두 비워지게 됩니다. 여기선 간단한 사칙 연산을 수행하는 계산기를 예로 들었습니다만 (,) 혹은 unary minus (ex:-1)와 같이 복잡한 계산을 수행할 때도 유용하게 이런 방법이 쓰일 수 있습니다. 실제로 HP머신에 탑재된 계산기가 스택을 이용한 계산기라고 하더군요. 실제로 구현하는건 그리 어렵지 않으므로 직접 구현해 보시기 바랍니다. 1.2.4.5) Binary Search Tree Binary Search Tree(이하 BST)는 parent 왼쪽에 작은 값을 담은 child가, parent 오른쪽에 큰 값을 담은 child가 들어가는 자료구조입니다. 이렇게 구성하면 데이터를 효율적으로 검색할 수 있기 때문에, 많이 쓰이는 형태입니다. BST에 데이터를 삽입하는 함수에 대해 알아보겠습니다. BSTinsert(root, val) { temp = new node temp.data = val temp.left = temp.right = null if(root == null) return temp BSTinsert_recurs(root, temp) return root } BSTinsert_recurs(root, temp) { if(temp.data <= root.data) if(root.left == null) root.left = temp else BSTinsert_recurs(root.left, temp) else if(root.right == null) root.right = temp else BSTinsert_recurs(root.right, temp) } pseudo code입니다만 간결하고 알기 쉽게 되어있기 때문에 금방 다른 언어로 구현할 수 있을 겁니다. 다만 여기선 doubly linked list를 썼는데, 그냥 array로 구현하면 훨씬 간단합니다. array로 구현할 경우, parent와 left child, right child의 주소는 각각 parent의 주소를 n이라 할 때 n*2+1, n*2+2 가 됩니다. 위의 코드를 array로 바꾸는 것도 어렵지 않겠죠? BSTreplace(root, ref) { if(ref.left == null) child = ref.right <--- 2 else child = ref.left if(ref == root) { if(child != null) child.parent = null return child } if(ref.parent.left == ref) ref.parent.left = child <--- 3 else ref.parent.right = child if(child != null) child.parent = ref.parent return root } BSTreplace 함수는 root의 child를 ref의 child로 바꿔주는 역할을 하는 함수입니다. delete를 구현하기 위해 필요합니다. BSTdelete(root, ref) { if(ref.left == null || ref.right == null) return BSTreplace(root, ref) <--- 1 succ = ref.right while(succ.left != null) succ = succ.left ref.data = succ.data return BSTreplace(root, succ) } 이제 BSTdelete 함수를 봅시다. BSTinsert보다는 복잡한데 역시 하나하나 따라가며 살펴보면 그리 어렵지 않습니다. 말로 설명하긴 어려우니 직접 아래 그림을 보며 BST에서 어떻게 데이터가 삭제되는지 알아봅시다. 1.2.5) Heap Heap에는 두 종류가 있습니다. Binary Min Heap과 Binary Max Heap 인데요, 검색과 정렬에 있어 높은 효율을 보여주는 자료구조이므로 많이 쓰입니다. 여기선 Binary Max Heap을 중심으로 설명드리겠습니다. Max Heap은 Parent 노드가 Child 노드들보다 항상 큰 값을 갖는 구조로 되어있습니다. Binary Tree보다 Heap은 균형잡힌 구조를 가지게 됩니다. 앞서 Binary Tree의 경우 최악의 경우엔 아래 그림과 같이 linear한 형태를 띄게 되나 Heap은 그럴 일이 없습니다. 또한, array로 만들기도 Binary Tree보다 쉽습니다. heap_insert(val, v, n) { i = n = n + 1 while(i > 1 && val > v[i/2]) { v[i] = v[i/2] i = i / 2 } v[i] = val } 위 함수는 Heap에 데이터를 하나 삽입하는 heap_insert 함수의 pseudo code 입니다. val은 삽입될 데이터를, v는 heap형태의 array를, n은 v의 현재 index를 가르킵니다. siftdown(v, i, n) { temp = v[i] while(2 * i <= n) { child = 2 * i if(child < n && v[child + 1] > v[child]) child = child + 1 if(v[child] > temp) v[i] = v[child] else break i = child } v[i] = temp } siftdown 함수는 아래 그림과 같이 인덱스 i 양쪽에 있는 두 heap을 하나로 합쳐서 새로운 heap을 만드는 함수입니다. i의 left들을 right child와 비교해가며 i를 중심으로 heap을 구성해가는 함수입니다. heapify(v, n) { for i = n / 2 downto 1 siftdown(v, i, n) } heapify함수는 특정한 array 하나를 heap 자료구조 형태로 만들어주는 함수입니다. for loop를 돌며 개별 node들에 대해 하나씩 siftdown을 적용하면 전체적으로 heap 구조가 됨을 알 수 있습니다. n / 2 부터 시작하는 이유는 child가 존재하지 않는 node 들에 대해선 siftdown 함수를 적용할 필요가 없기 때문입니다. 그림을 그려가며 추적해 보면 이해가 빨리 될 겁니다. heap_delete(v, n) { v[1] = v[n] n = n - 1 siftdown(v, 1, n) } 마지막으로 heap에서 시작 root를 삭제하는 함수입니다. heap 전체의 크기를 하나 감소시키고, root 노드를 heap의 마지막 값으로 바꾼 다음, root 노드를 중심으로 siftdown 함수를 사용해 heap을 구성하면 heap이 완성되는 원리를 사용했습니다. 아래는 array를 이용한 Binary Max Heap을 실제로 구현한 C코드입니다. #include <stdio.h> void siftdown(int v[], int i, int n) { int temp, child; temp = v[i]; while(2 * i <= n) { child = 2 * i; if(child < n && v[child + 1] > v[child]) child = child + 1; if(v[child] > temp) v[i] = v[child]; else break; i = child; } v[i] = temp; } void heapify(int v[], int n) { int i; for(i = n / 2; i >= 1; i--) siftdown(v, i, n); } void heap_insert(int val, int v[], int n) { int i; i = n = n + 1; while(i > 1 && val > v[i / 2]) { v[i] = v[i / 2]; i = i / 2; } v[i] = val; } void heap_delete(int v[], int n) { v[1] = v[n]; n = n - 1; siftdown(v, 1, n); } int main() { int i; int v[7] = {-1, 1, 2, 3, 8, 7, 6}; for(i = 1; i < 7; i++) printf("%d ", v[i]); printf("\n"); heapify(v, 6); for(i = 1; i < 7; i++) printf("%d ", v[i]); printf("\n"); heap_insert(5, v, 6); for(i = 1; i < 8; i++) printf("%d ", v[i]); printf("\n"); } 1.2.5.1) Heapsort Heapsort는 Heap 자료구조를 이용하는 특별한 sorting 방식입니다. 값의 절대 위치가 바뀌지 않는 stable sort(여기에 관한 자세한 내용은 4장에서 설명할 겁니다.)며, O(lg n)의 time complexity를 가지는 뛰어난 소팅 알고리즘입니다. heapsort(v, n) { heapify(v, n) for i = n downto 2 { swap(v[1], v[i]) siftdown(v, 1, i - 1) } } v의 root노드가 항상 가장 큰 값을 갖게 되는 성질을 이용한 정렬 방식입니다. 아래 설명을 참고하시기 바랍니다. 1.2.6) Disjoint Set Disjoint set은 집합을 표현하기 위해 쓰는 자료구조입니다. 예를 들어, {1, 2, 3, 4, 5} 라는 집합이 있을 때, 이를 {1}, {2}, {3}, {4}, {5} 이렇게 하나씩 구분할 수도 있고, {1, 2}, {3}, {4, 5} 이런 식으로 연관있는 것끼리 묶어서 표현할 수도 있습니다. 또 하나 예를 들어 볼까요? 1, 2, 3, 4, 5라는 노드들이 있을 때 이 노드들은 각각 연결되어 있을 수도 있고, 아니면 독립된 노드가 있을 수도 있습니다. 만약 1, 2만 연결되어 있고 3, 4, 5는 각자 떨어져 있다면 Disjoint set으로 {1, 2}, {3}, {4}, {5} 이렇게 표현할 수 있겠죠. makeset(i) { parent[i] = i; } makeset 함수는 Disjoint set에 사용되는 단위 하나를 만듭니다. makeset(1) makeset(2) makeset(3) makeset(4) makeset(5) 이렇게 하면, {1}, {2}, {3}, {4}, {5} 와 같이 독립된 노드 하나씩을 만든다는 의미입니다. findset(i) { while(i != parent[i]) i = parent[i] return i } findset 함수는 Disjoint set에서 단위 노드 i의 parent 노드를 찾는 함수입니다. mergetrees(i, j) { parent[i] = j } mergetrees는 두 노드를 합병하는 함수입니다. mergetrees(1,2) mergetrees(3,4) 이렇게 하면, {1,2}, {3,4}, {5}가 됩니다. union(i, j) { mergetrees(findset(i), findset(j)) } union 함수는 i와 j가 서로 다른 set에 속해 있을 때 이들을 서로 합치는 함수입니다. 서로 다른 tree를 합병할 때 이 함수를 사용할 수 있습니다. 예를 들어, {1,2},{3,4},{5}가 있을 때, mergetrees(1,3} 하면 {1,2,3},{4},{5} 가 되지만 union을 쓰면 {1,2,3,4},{5}가 됩니다. 1.2.6.1) Improvement 위에서 소개한 Disjoint set구조는 set을 합칠 때 마구잡이로 합치기 때문에 비효율적입니다. Tree는 되도록 Height가 적고 뻗어나가는 가지가 많은 삼각형 모양이 되어야 검색이나 삽입시 효율적인데 이전의 findset 때문에 O(n)이라는 비효율적인 알고리즘이 됐습니다. 아래 그림을 봅시다. 이를 해결하기 위해선 Disjoint set에 Tree의 height 개념을 도입해 Disjoint set이 균형잡힌 모양으로 구성되게 할 필요가 있습니다. 다만, 각 node에 높낮이 개념을 도입하기 위해 필요한 메모리 공간이 더 소모되는 것은 피할 수가 없겠죠. makeset(i) { parent[i] = i rank[i] = 0 } mergetrees(i, j) { if(rank[i] < rank[j]) parent[i] = j else if(rank[i] > rank[j]) parent[j] = i else { parent[i] = j rank[j] = rank[j] + 1 } } 위 함수를 쓰면 아래 그림과 같이 알고리즘이 개선됩니다. 1.3) C++ Standard Template Library C++의 Standard Template Library(이하 STL)는 프로그래머에게 보다 편리한 환경을 지원하기 위한 목적으로 만들어졌습니다. 여기에 설명되어 있는 대부분의 자료구조가 지원되며 템플릿을 사용하여 타입에 구분없이 사용 가능합니다. 오픈소스의 g++과 Visual C++ .Net 버전 이상이면 무리없이 컴파일하고 사용하실 수 있습니다. 아래는 Visual C++ .Net버전에서 지원하는 컨테이너 목록입니다. - deque - hash_map - hash_multimap - hash_multiset - hash_set - list - map - multimap - multiset - set - vector deque에서 stack, queue를 통합 지원합니다. 즉 그냥 stack, queue라고 써도 되지만 내부적으론 deque로 동작하게 된다는 말입니다. list는 linked list, vector는 일반 array에 대응됩니다. map 역시 일반 array에 대응되며 map이 vector보다는 중간에 빈공간을 허용한다는 점에서 array에 가깝습니다. 모두 내부적으로 알고리즘에 관련된 함수들을 지원하며 일반적으로 사용되는 알고리즘 함수들도 algorithm 파일에 정의되어 있습니다. 프로그램을 짜는데 필요한 자료구조를 하나하나 프로그래밍하는 것보다는 STL을 사용하면 훨씬 편리하게 프로그램을 작성할 수 있을 겁니다. 자세한 사항을 모두 설명하면 책이 한권이 나오게 되므로, 이쯤에서 마치도록 하겠습니다. 개인적으로는 STL 기초는 MSDN Library를, 심화 학습을 위해선 Effective STL (유명한 책이죠...) 번역서를 추천합니다. ------------------------------------------------------------------------------------------------- 이 강좌는 거의 Richard Johnsonbaugh, Marcus Schaefer 공저 Algorithms 책(엄청 좋은 책입니다 ㅡㅡ;) 을 기본으로 해서 만들어졌음을 미리 밝혀둡니다. 다만 번역서는 아닙니다. 이 책을 보고 필자가 이해한 것에 관해서 적은 것이며, 따라서 저작권은 필자에게 있습니다. (1) 특정 단체의 무단 복제를 금합니다. (2) 개인이 복제할 경우, 출처를 표기해주셔야 합니다. (3) 어떠한 경우라도 글 전체 내용에 대한 수정을 가하는 것은 금지합니다.

이 글에 평점 주기: 0점 1점 ■ 2점 ■■ 3점 ■■■ 4점 ■■■■ 5점 ■■■■■ 6점 ■■■■■■ 7점 ■■■■■■■ 8점 ■■■■■■■■ 9점 ■■■■■■■■■

2004-10-31 19:49:00  Re:  알고리즘 강좌(2)...  초보뿔 / iconsrun         이런말씀 드리긴 모하지만.. 제가 1등입니다. 쿨럭

2004-10-31 20:06:00  Re:  알고리즘 강좌(2)...   써니 / hklovecw         저도 이런말씀 드리기 쫌 그러지만,, 제가 2등이군요. 쿨럭

2004-11-01 09:21:00  Re:  알고리즘 강좌(2)...  비행소년 / kalic         저도 아침부터 좀 그렇지만. 제가 3등이군요.. 순위권입니다. 쿨럭

2004-11-01 09:28:00  Re:  알고리즘 강좌(2)...  닉네임 / minidisc         아깝다 ... 메달을 놓쳤네 ... -_-

2004-11-01 18:43:00  Re:  알고리즘 강좌(2)...  초보뿔 / iconsrun         축하드립니다. 써니님이 약물복용으로 탈락되셨답니다. 닉네임님 3등 축하드립니다.

2004-11-01 20:59:00  Re:  알고리즘 강좌(2)...  VC++오늘까지배우고내일부터포기 / clublaw         이승우님 책내실건가요? 사무실이라서 정독은 못했지만 그래도 대단하십니다.

2004-11-01 21:00:00  Re:  알고리즘 강좌(2)...  VC++오늘까지배우고내일부터포기 / clublaw         연재 계속 해달라고 9점 찍었습니다. ^^ㅁ

2004-11-01 22:45:00  Re:  알고리즘 강좌(2)...  이승우 / sunmind         감사합니다. 책은 아니고요, 알고리즘 공부할만한 마땅한 강좌 자료나 사이트가 국내엔 전무해서 취미삼아 쓰게 되었습니다.^^

2004-11-02 08:37:00  Re:  알고리즘 강좌(2)...  VC++오늘까지배우고내일부터포기 / clublaw         좋은 강좌로 남아서 나중에 책으로 꼭 내시게 되길 바라겠습니다.

2004-11-03 09:34:00  Re:  알고리즘 강좌(2)...  김동천 / winicon         좀 더 디데일하게 하신다면 책 내도 좋을것 같습니다.

2004-11-29 12:20:00  Re:  알고리즘 강좌(2)...  심근정 / inyourhand         저도 자료구조랑 알고리즘 공부하려고 많이 찾아 봤지만 다 나뉘어져 있어 통합해 보기 힘들었는데.. 좋네요~ 계속 올려주세요!! ^ ^*

2004-11-08 오후 9:23:40   /  번호: 6968  / 평점:  (9.0) category: VC++ 일반  /  조회: 7,049

알고리즘 강좌(3) 이승우 / sunmind

강좌(2)의 그림 링크가 모두 깨졌군요 이론이론... ㅠㅠ 멀쩡한 전체 내용은 http://cs.knu.ac.kr/~lsw9946/Algorithm.htm 에서 보실 수 있습니다. 목차 1) Introduction 1.1) Mathematical definition 1.1.1) logarithm, factorial 1.1.2) Time complexity 1.1.3) C/C++ example 1.2) Data structures 1.2.1) Stack 1.2.2) Queue 1.2.3) Linked list 1.2.4) Binary tree 1.2.4.1) Preorder traversal 1.2.4.2) Postorder traversal 1.2.4.3) Inorder traversal 1.2.4.4) Stack calculator 1.2.4.5) Binary search tree 1.2.5) Heap 1.2.5.1) Heapsort 1.2.6) Disjoint set 1.2.6.1) Improvement 1.3) C++ Standard Template Library 2) Searching 2.1) Searching 2.1.1) Data Representations 2.1.2) Binary Search 2.1.3) DFS 2.1.4) BFS 2.2) Topological Sort 2.3) Backtracking 3) Divide and Conquer 3.1) Examples 3.1.1) Example : A Tiling Problem 3.1.2) Example : Finding a Closest Pair of Points 3.2) Implementations 3.2.1) Mergesort 3.2.2) Strassen's Matrix Product Algorithm 4) Sorting and Selection 5) Greedy Algorithms 6) Dynamic Programming 7) Text Searching 8) P and NP 9) Heuristic Algorithms Chapter 2) Searching 이 챕터에서는 가장 기본적인 Binary search 와 Depth First Search (깊이 우선 탐색) Breadth First Search (너비 우선 탐색) 및 Topological Sort, Backtracking 같은 기법들에 대해 배울 것입니다. 2.1) Searching 일반적으로 컴퓨터에서 Searching이라고 하면 Linear한 형태의 Searching만을 생각하기 쉽습니다. 예를 들어, 배열 A={1,2,4,7,8,9,10}에서 10을 찾아내라고 하면 어떻게 해야 할까요? while 루프를 돌며 하나하나 찾는 방법이 가장 일반적이겠지요. 그러나 조금만 머리를 쓰면 보다 빠르게 찾을 수 있습니다. 이번 섹션에선 어떤 자료 표현방법을 쓰며, 여기에 대한 어떤 Search 알고리즘이 있는지 하나하나 알아보도록 하겠습니다. 2.1.1) Data Representations Search 알고리즘에 대해 알아보기 전에 자료 표현 방법에 대해 잠시 알아보겠습니다. 이걸 알아보는 중요한 이유는, Search 해야 할 대상이 단순한 배열뿐만 아니라, 그래프나, 경로 길이까지 포함한 그래프도 있을 수 있기 때문입니다. 각각의 대상을 표현하는 방법으로 array가 있을 수도 있지만 adjacency list나 2차원적인 array가 있을 수 있습니다. 위와 같은 그래프가 있다고 가정할 때 각각의 표현법에 대해 알아봅시다. Adjacency list 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 Array 위와 같이 2가지 방식으로 그래프를 표현하는 것을 생각해 볼 수 있는데, Adjacency list에서는 Array와 Linked list를 사용하여 연결되어 있는 노드만을 list에 연결해주고, Array로 그래프를 표현할 때는 Array의 인덱스를 이용하여 인접해 있는 노드들간에는 yes, 인접해 있지 않은 노드들간에는 no라고 표기함을 알 수 있습니다. 이 챕터에선 대부분 Adjacency list를 이용하여 알고리즘을 적용할 것입니다. 2.1.2) Binary Search Binary Search는 가장 기본이 되는 Search 방법중의 하나입니다. linear하게 구성된 array에서도 데이터를 O(lgn)의 속도로 검색할 수 있게 해주는 마법같은 알고리즘입니다. 예를 들어, A={1,2,4,5,7,9}에서 7이라는 수를 찾고 싶다고 할 때, 보통 linear한 검색으로는 1,2,4,5,7까지 총 5번의 검색을 거쳐야 하지만 Binary Search로는 4,5,7 단 세 번의 검색으로 원하는 수를 찾아낼 수 있습니다. 이 격차는 A의 총 연장 길이가 길어질수록 더욱 벌어지지요. 아래 코드를 봅시다. bsearch(L,i,j,key) { while(i <= j) { k = (i + j) / 2 if(key == L[k]) // found return k if(key < L[k]) // search first part j = k - 1 else i = k + 1 } return -1 // not found } L은 데이터를 검색하고자 하는 순서대로 소팅된 array를, i는 검색 시작점을, j는 검색 마지막점을, key는 검색할 데이터를 의미합니다. 아까 예로 든 배열 A에서 7을 찾아내고자 할 떈 i에 1을, j에 6을 입력하고, key 값으로 7을 넣게 되겠지요. 검색하고자 하는 범위의 중간지점의 데이터와 비교해서 검색할 값(key)이 작은 경우엔 반을 뚝 잘라 왼쪽의 작은 데이터들 중에서, key 값이 큰 경우에도 역시 반을 뚝 잘라 오른쪽의 큰 데이터들 중에서 검색하면 된다는 것이 이 알고리즘의 기본 아이디어 입니다. 이런 식으로 검색해 나가면 검색할 범위는 반씩 계속 줄어듦을 알 수 있습니다. 따라서 Linear search의 O(n)이던 Time complexity가 O(lgn)으로 개선되는 것을 볼 수 있죠. 2.1.3) Depth-First Search Depth-First Search는 adjacency list로 표현된 그래프 데이터가 있을 때 특정 노드를 찾는 방법 중 하나입니다. 이 방법을 한 문장으로 요약하자면 '범인 한 사람만 끝까지 추적하자'라고 할 수 있습니다. 그래프 상에서만 본다면 알고리즘 짜기가 어려워 보일수도 있지만 Adjacency list상에서 보면 매우 쉽습니다. index: 1 2 3 4 5 6 visit[n] = {0, 0, 0, 0, 0, 0} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 아까 소개한 Adjacency list에 대하여 DFS를 적용해 보겠습니다. 1부터 시작한다고 가정해봅시다. 그러면 1과 바로 연결된 2번 노드까지 갑니다. 그리고 1과 2를 들렀으므로 여기에 대해 들렀다고 표기해둡니다. 그러면 아래와 같이 되겠죠. index: 1 2 3 4 5 6 visit[n] = {1, 1, 0, 0, 0, 0} 1 -> 2 -> 3 <----- (1) 2 -> 1 <----- (2) 3 -> 1 -> 5 <----- (3) 4 -> 6 5 -> 3 6 -> 5 방금 방문한 2번 노드는 한번도 방문하지 않았던 노드이므로 2번 index, 즉 (2)로 이동하여 새로 동일하게 추적을 시작합니다. 이 index에선 모두 이미 방문했던 노드를 거치므로 다시 원래의 index, (1)로 돌아가서 추적을 계속하게 됩니다. 이젠 방문하지 않았던 3을 방문하게 되죠. 그러면 visit[3]을 1로 표기하고 (3)으로 가서 추적을 다시 시작합니다. 1번 노드는 이미 방문했던 노드이므로 5를 방문하게 되고, 5번 index에서 다시 3으로 가게되고 3번째 index의 추적도 5에서 마무리되므로 DFS 추적이 끝나게 됩니다. 결국 DFS 경로는 아래와 같이 나오게 되죠. 1 -> 2 -> 3 -> 5 index: 1 2 3 4 5 6 visit[n] = {1, 1, 1, 0, 1, 0} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 이렇게 마무리되고 1, 2, 3, 5와 4, 6은 서로 고립된 관계에 있음을 알 수 있게 됩니다. 매우 쉽죠? 아래는 DFS의 pseudo code 입니다. dfs(adj, start) { n = adj.last for i = 1 to n visit[i] = false dfs_recurs(adj, start) } dfs_recurs(adj, start) { println(start) visit[start] = true trav = adj[start] while(trav != null) { v = trav.ver if(!visit[v]) dfs_recurs(adj, v) trav = trav.next } } DFS의 장점은 고립되어 있는 범위를 찾아내기 쉽다는 것입니다. 예를 들어, 포토샵에서 주로 사용되는 툴인 매직 완드 툴이 DFS를 활용한 것이라고 할 수 있습니다. 2.1.4) Breath-First Search Breath-First Search 역시 adjacency list로 표현된 그래프 상에서 특정 노드를 찾는 방법입니다. 이것은 한 노드를 잡아서 그 노드에 연결된 모든 노드를 상대로 탐색을 하는 방식인데, 역시 Adjacency list 상에서 추적해보면 쉬운 알고리즘입니다. index: 1 2 3 4 5 6 visit[n] = {0, 0, 0, 0, 0, 0} queue = {} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 아까 DFS로 추적했던 그래프를 이번엔 BFS로 추적해 봅시다. 1번 노드에서 출발합니다. 그리고 출발한 노드는 큐에 삽입합니다. 큐를 사용하는 이유는 더 이상 추적을 하게 되지 못할 경우를 대비해서 입니다. DFS에서와는 달리 연결된 모든 정점에 대해 탐색을 하는 BFS 알고리즘은 큐를 사용하지 않을 경우 O(n)짜리 검사 알고리즘을 사용하여 추적할 노드가 아직 남아있는지 검사해야 합니다. 큐를 사용할 경우엔 단지 O(1)이면 추적을 계속할 수 있는지 판별할 수 있죠. index: 1 2 3 4 5 6 visit[n] = {1, 0, 0, 0, 0, 0} queue = {1} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 큐에서 가장 먼저 들어간 노드 번호를 하나 꺼내고, 이 노드에 대해 탐색을 시작합니다. 1에 연결된 모든 노드를 거치므로 2와 3을 방문하게 됩니다. 그러면 아래와 같이 되겠죠. index: 1 2 3 4 5 6 visit[n] = {1, 1, 1, 0, 0, 0} queue = {2, 3} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 먼저 들어가 있던 1을 꺼내고 2, 3을 방문했으므로 위와 같이 됐습니다. 다시 큐에서 먼저 들어간 노드 번호를 꺼내고 여기에 대해 탐색을 합니다. 2와 연결된 1은 이미 탐색했으므로 그냥 넘어가고, 3과 연결된 노드들에 대해 탐색합니다. 그러면 2와 3을 큐에서 꺼내고 5를 새로 탐색했으므로 아래와 같이 됩니다. index: 1 2 3 4 5 6 visit[n] = {1, 1, 1, 0, 1, 0} queue = {5} 1 -> 2 -> 3 2 -> 1 3 -> 1 -> 5 4 -> 6 5 -> 3 6 -> 5 큐에서 5를 꺼내고 5와 연결된 노드에 대해 탐색을 하면 3밖에 없으므로 큐는 완전히 비게 되고, 1 -> 2 -> 3 -> 5 순으로 BFS 탐색을 끝내게 됩니다. 간단하지요? 아래는 BFS의 pseudo code입니다. bfs(adj, start) { n = adj.last for i = 1 to n visit[i] = false visit[start] = true println(start) q.enqueue(start) while(!q.empty()) { current = q.front() q.dequeue() trav = adj[current] while(trav != null) { v = trav.ver if(!visit[n]) { visit[v] = true println(v) q.enqueue(v) } trav = trav.next } } } BFS의 장점은 위 DFS와 달리 Recursion을 사용하지 않는다는 것입니다. 의외로 Recursion을 사용할 때 함수가 로드되고 해제되는데 시간이 꽤 걸립니다. ------------------------------------------------------------------------------------------------- 이 강좌는 거의 Richard Johnsonbaugh, Marcus Schaefer 공저 Algorithms 책(엄청 좋은 책입니다 ㅡㅡ;) 을 기본으로 해서 만들어졌음을 미리 밝혀둡니다. 다만 번역서는 아닙니다. 이 책을 보고 필자가 이해한 것에 관해서 적은 것이며, 따라서 저작권은 필자에게 있습니다. (1) 특정 단체의 무단 복제를 금합니다. (2) 개인이 복제할 경우, 출처를 표기해주셔야 합니다. (3) 어떠한 경우라도 글 전체 내용에 대한 수정을 가하는 것은 금지합니다.

이 글에 평점 주기: 0점 1점 ■ 2점 ■■ 3점 ■■■ 4점 ■■■■ 5점 ■■■■■ 6점 ■■■■■■ 7점 ■■■■■■■ 8점 ■■■■■■■■ 9점 ■■■■■■■■■

2004-11-11 12:19:00  Re:  알고리즘 강좌(3)...  신진범 / likelove         오... 승우다 >.< cs가 링크되어 있어서 혹시나 했는데 ㅋㅋ 나 98 진범이~ 여기서 보니 반갑네 ^^

2004-11-12 16:31:00  Re:  알고리즘 강좌(3)...  이승우 / sunmind         진범이형 안녕하세요~ 근데, 아는 사람 만나니 윽... 부끄럽네요 ㅠㅠ; ㅠ___ㅠ

2004-11-16 03:54:00  Re:  알고리즘 강좌(3)...  나물겅주 / minali1232         내가 아는 승우선배..맞는지..ㅋ 모르겠네요..... 내가 아는 승우선배는 알고리즘 공부하라고 했었는뎁~~~