IT's 2 EG

1. 이진탐색(Binary Search) 1.1. 이진탐색 이란? 'Up and Down'이라는 게임이 있습니다. 사회자는 일정 범위의 수 'x'를 생각한다. 참가자가 어떤숫자 'a'를 말했을때, 'a'가 'x' 보다 작으면 사회자는 'Up'이라고 말하며 'a'가 'x'보다 크면 'Down'이라고 말을 합니다. 그렇다면 가장 빠르게 'x'를 찾는 방법은 무엇일까요? 이에 대한 해답은 해당 범위의 중간값을 말하면서 'x'의 범위를 좁혀나가는 방법입니다. 이러한 방법으로 탐색을 해 나가는 것을 이진탐색이라고 합니다. 이진 탐색을 위해서는 우선 정렬이 되어있어야 한다는 조건이 있지만, 매우 큰 범위내에서 빠르게 찾고싶은 데이터를 찾을 수 있는 장점이 있습니다. 결과적으로 이진탐색은 O(logN) 라는 시간복잡..

너비 우선 탐색(BFS) 이란? 너비 우선 탐색 (BFS, Breadth First Search)은 DFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. BFS 알고리즘은 현재의 위치에서 방문할 수 있는 모든 정점을 방문한 뒤 다음 단계로 넘어가는 방식입니다. 일반적으로 BFS 알고리즘을 구현할 때 큐를 이용합니다. 너비 우선 탐색(BFS) 방법 아래는 BFS를 설명하기 위해 작성한 간단한 그래프입니다. 원안의 1,2,3.. 등을 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 BFS 알고리즘을 바탕으로 탐색을 해보겠습니다. 시작점인 1번 정점을 큐에 넣고 해당 위치에 방문을 했다고 표시합니다. 1번 정점과 연결된 2번, 3번 정점을 큐에..

깊이 우선 탐색(DFS) 이란? 깊이 우선 탐색 (DFS, Depth First Search)은 BFS와 함께 대표적인 그래프 탐색 방법 중 하나입니다. 일반적으로 DFS 알고리즘을 구현할 때 스택을 이용하고, 유사하게 재귀함수를 이용하여 구현하기도 합니다. DFS 알고리즘은 스택을 이용해서 갈 수 있는만큼 최대한 이동을 하며, 만약 갈 수 없다면 이전 정점으로 돌아갑니다. 깊이 우선 탐색(DFS) 방법 아래는 DFS를 설명하기 위해 작성한 간단한 그래프입니다. 여기서 원으로 둘라싸인 1, 2, 3 .. 등은 정점(Vertex)라 하고, 정점과 정점을 잇는 선을 간선(Edge)이라고 합니다. 우선 시작점을 1로 정하고 DFS 알고리즘을 바탕으로 탐색을 진행해 보겠습니다. 출발점인 1을 스택에 입력하고, ..