살펴보면서 전진하자! 너비 우선 탐색(BFS, Breadth First Search) 이번에는 너비 우선 탐색(BFS, Breadth First Search) 알고리즘에 대해 알아보려고 합니다. 우리가 전에 알게된 깊이 우선 탐색(DFS)과는 달리 스택을 이용하지 않고 큐를 이용하며, 너비 우선 탐색도 트리나 그래프에서의 탐색에 사용되는 알고리즘입니다. 이 너비 우선 탐색은 깊이가 1인 모든 정점을 방문하고 나서, 그 다음에는 깊이가 2인 모든 정점을, 깊이가 3인 모든 정점을 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마칩니다. 너비 우선 탐색은 깊이 우선 탐색과는 다르게 무작정 막힐때까지 탐색을 진행하는게 아니라, 이곳저곳 살펴보면서 탐색을 진행하는 것이라고 할 수 있습니다. ..

해를 찾기위해 전진, 또 전진! 깊이 우선 탐색(DFS, Depth First Search) 이번에는 깊이 우선 탐색(DFS, Depth First Search)이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 이 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 너비 우선 탐색이라고 해서 깊이 우선 탐색과 비슷한게 있는데, 너비 우선 탐색은 다음 강좌에서 소개할 예정입니다. 이 DFS 알고리즘은 더이상 나아갈 길이 보이지 않을 만큼 깊이 들어가는 특징을 지니고 있는데, 만약 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 다른 길을 선택하여 움직입니다. 이해하기 쉽도록 그래프를 보면서 설명을 하도록 하겠습니다. 깊이 우..

매 순간마다 최선의 선택! 탐욕 알고리즘(Greedy Algorithm) 오늘 알아볼 알고리즘은 '탐욕 알고리즘(Greedy Algorithm)' 입니다. 알고리즘의 이름 그대로, 상당히 욕심이 많은 알고리즘 입니다. 탐욕 알고리즘이 어떤 알고리즘이냐면, 매 순간마다 최선의 선택을 하는 녀석입니다. 즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해나가며 최종적인 해답을 구하는 알고리즘이라고 말할 수 있습니다. 그러나, 이 알고리즘을 설계할 때 유의할 점은 전체를 고려하는게 아니라 문제를 부분적으로 나누어, 나누어진 문제에 대한 최적의 해답을 구하므로 전체적인 최적의 해가 될 수 있는 경우가 존재합니다. 한번 예를 보아볼까요? 탐욕 알고리즘의 대표적인 문제로 거스름돈을 계산하는 문제가 있는데, 만약 거스..

특별한 트리를 기본으로 하는 자료구조! 힙(Heap) 오늘은 '힙(Heap)'이란 자료구조에 대해서 알아보려고 합니다. 이 힙(Heap)이란 자료구조는 위키백과에 따르면 '특별한 트리를 기본으로 하는 자료구조이다.'라고 설명되어 있습니다. 여기서 특별한 트리란 우리가 전에 배운 완전 이진 트리를 말하며, 힙 자료구조는 최대 힙(Max Heep)과 최소 힙(Min Heep)으로 나뉘며 이러한 힙은 최대값 또는 최소값을 짧은 시간내에 찾기 위해서 만들어진 자료구조입니다. 최대 힙이란 부모 노드의 값이 항상 자식 노드의 값보다 크다는 것이며, 최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작다는 것입니다. 예를 들어, 부모 노드의 값이 항상 자식 노드의 값보다 작은 최소 힙(Min Heap)은 아래와 ..

데이터를 찾아보자! 이진 탐색 트리(Binary Search Tree) 이번에는 이진 탐색(Binary Search)이 적용된 이진 트리(Binary Tree)에 대해서 알아볼 것입니다. 이진 트리(Binary Tree)에 대해 더 상세한 설명을 보고싶으시면 아래 링크를 방문하여 이진 트리에 대한 설명을 읽어보시기 바랍니다.이진 트리(Binary Tree): http://blog.eairship.kr/215 우리가 알고 있는 이진 트리는 자식 노드가 최대 두 개의 노드를 지니고, 네 가지 성질을 지닙니다. 자식 노드가 아에 없거나, 왼쪽 자식 노드 혹은 오른쪽 자식 노드 하나만 존재하거나, 왼쪽과 오른쪽 자식 노드를 모두 지니는 경우입니다. 그렇다면, 우리가 배우게 될 이진 탐색 트리는 어떻게 자라야 할..

데이터를 찾아보자! 이진 탐색(Binary Search) 이번에는 순차 탐색에 이어 이진 탐색(Binary Search)에 대해 알아보도록 할텐데, 이 '이진 탐색(Binary Search)'이 왜 이진인지 짐작이 가시나요? 이진 탐색이란 이름이 붙여진 이유는 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 줄어들기 때문에 그렇습니다. 이 탐색 알고리즘은 순차 탐색과는 달리 정렬된 배열을 전제로 합니다. 이진 탐색이 얼마나 빠른 알고리즘이냐면, 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있습니다. 놀랍죠? 이진 탐색(Binary Search)의 탐색 과정 이제 한번, 위같은 정렬된 배열에서 이진 탐색..