1. 너비 우선 탐색a.k.a. BFS33장에서 우리는, 그래프를 탐색하는 데는 두 가지 방법이 있다고 하였습니다. 그중 하나는 시작 노드에서의 깊이를 우선으로, 다른 하나는 시작 노드에서의 너비를 우선한다고 하였죠. 33장에서 전자인 DFS를 보았으니, 이번 장에서는 후자인 너비 우선 탐색에 대해 알아봅시다. 너비 우선 탐색(Breadth First Search)의 순서는 다음과 같습니다.시작 정점에서 탐색을 시작한다.시작 정점의 자식 노드들을 대기열에 순서대로 모아둔다.대기열의 맨 앞 원소를 탐색한다. 마찬가지로 탐색하는 원소의 자식 노드들 중 탐색하지 않은 노드들을 대기열에 순서대로 추가한다.3.을 대기열이 빌 때까지 반복한다.33장에서도 사용한 그래프 예시를, 이번에는 너비 우선 탐색(이하 BFS..

1. 그래프의 탐색트리는 순회, 그래프는 탐색트리를 배울 때 우리는 "순회"라는 개념에 대해 함께 공부한 바 있습니다. 트리 순회의 본질이 트리의 모든 정점을 탐색하는 것이었는데, 이 과정이 트리를 순차적으로, 재귀적으로 탐색하기 때문에 트리에게는 단순히 "탐색"이라는 단어가 아닌 "순회"라는 단어를 이용해 표현합니다. 그래프도 여기에 상응하는 전체적인 탐색 방법이 있는데 이를 문자 그대로 그래프 탐색(Graph Search)이라고 합니다.트리 순회의 목적은 단순히 '정점을 모두 확인하는 것'에 있었습니다. 당초 트리에서 정점의 정보만큼이나 중요할 부모 자식 관계(다른 것들도 다 중요하겠지만 결국에는 트리의 부모 자식 관계에 기인하고 있습니다)는 정의하는 과정에서 이미 드러나 있기 때문에 트리 순회의 궁..

1. 알고리즘에서의 그래프란?다른 의미에서의 그래프의 정의초등학교 수학에서 "그래프"라는 용어를 한 번 이상 들어보셨을 겁니다. 흔히들 실생활에서 자주 보는 그래프는 도표의 개념이 강하다면, 알고리즘에서의 그래프는 전혀 다른 도형을 그래프라고 지칭합니다.앞서 트리에 대해 소개하면서, "소속 자료 간 계층 구조를 강조하기 위한 자료 구조"라고 설명한 바 있습니다. 이와 같은 맥락으로, 소속 자료 간 연결 구조를 강조하는 자료 구조를 그래프(Graph)라고 합니다.그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현합니다. 현실 세계에서 보자면, 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등을 그래프의 예시라 할 수 있으며, 그래프에는 부모 자식 관계의 ..

1. 개괄구간 연산의 시간 복잡도지금까지의 내용들을 충실히 공부해 왔다면, 우리는 1차원(또는 2차원) 배열 상에서 벌어지는 여러 가지 구간 연산들에 대해 정확한 답을 내놓을 수 있을 것입니다. 이러한 점이 가장 잘 드러나는 부분 합 이외에도, 정말 많은 문제들에 답할 수 있죠.자, 그렇다면 이 문제의 시간 복잡도는 어떠할까요?배열 $A=\{1, 6, 7, 4, 0, 5, 8, 3, 9, 2\}$의 부분 구간들의 최솟값을 모두 구하시오.이렇게 문제가 적혀 있다 보니 수학적으로 풀 수 있는 Logic이 떠오르기는 하지만, 우리는 문제의 의도에 충실하게 일일이 구간을 모두 추정하고 그 추정된 배열들을 모두 순회하며 일일이 최소치를 찾는 방식으로 풀어 보고자 합니다. 이렇게 했을 때 시간 복잡도는 당연하게도 ..

1. 우선순위 큐무슨 큐라고요?앞서 자료 구조에 대해 이야기하면서, 우리는 "큐"라는 친구에 대해 뜯어본 바 있습니다. 지금부터 다룰 이야기는, 이러한 큐 중에서도 굉장히 특수한 형태의 큐인 우선순위 큐(Priority Queue)에 대한 이야기입니다.큐의 큰 특징 중 하나는 바로 선입선출입니다. 그러니까 먼저 들어온 녀석이 먼저 빠져나온다는 거죠. 그리고, 우선순위 큐의 가장 큰 특징은 이 선입선출이 굉장히 독특한 방식으로 이루어진다는 것입니다. 우선순위 큐에서 나오는 순서는, "입력된 순서"에 기반하는 게 아니라, "우선순위"에 기반합니다. 역시나 이 우선순위는 어떠한 것이라도 문제가 없습니다.정렬을 하면 되는 거 아니야?사실 여기까지 오셨다면, 위의 질문이 떠오를 법도 합니다. 흔히들 우리가 가장 ..

1. 이진 트리와 검색 트리이진 트리이진 트리란 과연 무엇일까요?앞서 우리는 탐색에 대해 공부하면서, "이진" 탐색(Binary Search)이라는 기법에 대해 공부한 바 있습니다. 가만히 보니, 지금 우리가 배우게 될 '이진 트리'와 '이진'이라는 단어를 공유하고 있지요. 실제로 이진 트리(Binary Tree)의 영어 표기를 보면, 동일한 속성을 공유하고 있음을 짐작할 수 있습니다.실제로 이진 트리는, 각 정점이 최소 0개, 최대 2개의 자식을 가지는 트리를 의미합니다. 이때, 이 두 개의 자식 노드는 각각 왼쪽 자식 노드와 오른쪽 자식 노드로 표현됩니다. 참고로 이 둘은 별도의 노드로 취급하기 때문에 아래 그림의 트리가 일반적인 트리였다면 같은 트리였겠지만, 만약 이진 트리라면 이 둘은 같은 트리가..

1. 트리란 무엇인가계층 구조를 나타내는 방법?2장에서 우리는 자료 구조에 대해 공부하면서, 정적 배열과 동적 배열, 큐, 스택, 덱 등에 대해 공부해 온 바 있죠. 이들의 공통점은 바로 "선형으로 표현된 자료를 나타낼 수 있는 자료 구조"라는 점입니다. 생각해 보면 그렇죠? 일반적으로 저들은 1차원 배열, 또는 이에 준하는 형식의 데이터를 나타낼 때 활용되곤 합니다.하지만, 이제 우리는 시야를 넓혀 더 많은 자료를 나타내어 보고자 합니다. 그렇다면 우리는 새로운 자료 구조를 배워야겠지요.선형 자료 구조가 명확하게 나타내지 못하는 게 바로 계층 구조입니다. 이렇게 말하면 어렵게 느껴질 수도 있는데, 쉽게 생각해서 자료 간에 상하위 관계나 포함 관계가 존재하는 경우 우리는 이 자료 간에 "계층 구조가 존재..

1. 프로그래밍과 기하학나오는 주제가 정해져 있다?프로그래밍과 수학이 밀접하게 엮여 있다면, 역시 수학에서 빼놓을 수 없는 영역인 기하학 또한 언급하지 않을 수 없을 듯 합니다. 그런데 한 가지 특이한 점이 있다면, 프로그래밍에서 나오는 기하학의 세부 주제들, 정확히는 전산학과 엮여 있는 기하학의 세부 주제들은 정해져 있다는 겁니다. 일반적으로 이러한 주제들은 각종 기하학적 도형들을 다루는 영역들에 속해 있는데 이 주제들을 통틀어 우리는 계산 기하학(Computational Geometry)라고 합니다."계산"이라는 용어에서 어느 정도 눈치를 채신 분들도 계실 듯한데, 실제로 계산 기하학에서는 벡터와 그 연산을 기준으로 하여 갖가지 도형들의 관계라든지 이런 부분들을 흔히 다룹니다. 사실 이러한 주제들이 ..

1. 게임하는데 굳이 이론까지 써야 돼?!배스킨~라빈스~써리~원이 글의 제목을 보고 "뭔 게임하는데 수학 이론이 필요하다고..."라고 생각이 드신 분이 한 분쯤은 계실 것 같습니다. 하지만 흔히들 "배스킨라빈스 31"이라고 불리는 게임을 해 보신 분이라면 한 번쯤 여러분이 31을 외치게 될 경우의 수를 계산해 보신 적이 있으실 겁니다. 이는 배스킨라빈스 31 게임의 고유 룰인 "한 번에 1~3개의 수만을 외칠 수 있다"는 특성에 의한 것인데요. 만약 이러한 생각을 하셨다면 여러분은 이미 게임 이론을 술과 함께 몸속에 체화하신 게 됩니다.귀엽고~깜찍하게~써리~원정확히는 이러한 게임의 종류를 게임 이론에서는 "돌 가져가기 게임", 전문 용어로는 "님 게임"(Nim Game)이라고 합니다. 게임 이론은 님 게..

1. 개괄$\left|A\cup B\right|\neq \left|A\right|+\left|B\right|$?위의 명제는 굉장히 잘 알려져 있는 명제입니다. 그 이유를 수학적으로 설명할 수도 있겠지만, 우리가 알기 쉽게 설명하면 다음과 같은 이유일 것입니다.$A$와 $B$의 합집합의 원소의 개수는 $A$와 $B$의 원소의 개수의 합에 $A$와 $B$의 교집합의 원소의 개수를 제거해야 하기 때문이다.즉, 쉽게 이야기하자면, $A$와 $B$의 합집합의 원소의 개수를 셀 때는 $A$와 $B$의 교집합에 속하는 원소가 2번이 아닌 1번 세어지기 때문입니다. 따라서 최종적으로는 다음과 같이 식을 써야 맞는 논리가 되죠.$$\left|A\cup B\right|=\left|A\right|+\left|B\right|..