거대한 그래프에서 특정 조건을 만족하는 노드를 찾는 가장 효율적인 방법은 무엇일까? 본 포스팅에서는 그래프의 노드를 탐색 혹은 방문하는 유명한 알고리즘인 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해 소개하고자 한다. DFS(Depth-First Search)DFS는 그래프의 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방법이다. 깊이를 우선으로 탐색하는 방식이다. DFS는 아래와 같은 특징을 가진다.구현 방식: 재귀나 스택 자료구조를 사용하여 구현한다.완전 탐색: 한 경로의 끝까지 가고, 더 이상 진행할 수 없으면 이전 노드로 돌아와 다른 경로를 탐색한다.메모리 사용량: 경로의 깊이에 비례하여 메모리를 사용한다.예를 들어, 아래와 같은 완전 이..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 앞서 나왔던 자료구조 중 일반적인 상황에서 탐색에 가장 효율적인 것은 AVL 트리(https://cascade.tistory.com/99)로 O(logN)의 시간 복잡도를 가지고 있었다. 본 포스팅에서 다룰 자료구조는 탐색을 한 번에 하는, O(1) 짜리 자료구조인 테이블이다. 테이블이란, 사원번호 - 이름 표와 같이 key와 value로 저장된 데이터 구조이다. 여기에는 세 가지 규칙이 있다.Key는 반드시 Value와 쌍을 이룬다Key가 존재하지 않는 값은 저장할 수 없다.어떤 Key도 중복되지 않는다.먼저, 배열을 기반으로 테이블 자료구조를 구현하자.배열 기반의 테이블 구현위에서 든 예와 같이, ..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 앞선 포스팅에서 살펴 본 이진 탐색 트리를 통한 searching은 일반적으로 시간 복잡도가 O(logN)이다. 그러나, 트리가 불균형할 경우, 시간 복잡도가 O(N)까지 상승할 수 있다.https://cascade.tistory.com/97 [열혈자료구조] 11강. 탐색(Search) 1* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를cascade.tistory.com 예를 들어, 아래와 같은 트리가 "불균형한 트리"이다.이러한 트리의 모양은 5, 4, 3..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 11강에서 다루는 이전에 다루었던 단순 탐색, 이진 탐색을 다루는 것이 아니라, 트리 구조를 기반으로 하는 탐색을 다룬다. 즉, 데이터를 어떻게 저장하는지가 탐색의 효율에 큰 영향을 미칠 수 있다. 단순 탐색과 이진 탐색은 이전 포스팅을 참고!! https://cascade.tistory.com/62 탐색 알고리즘 (백준 1920번)무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세cascade.tistory.com 보간 탐색(Interpolation S..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 5. 병합 정렬(Merge Sort) 병합 정렬은 divide and conquer라는 알고리즘에 의해 근거하였다. 16개의 데이터를 정렬한다고 하면, 8개짜리 2개로 나눠서 정렬하고 합치는 것이 더 효율적이라는 것이다. 즉, 8개를 다시 4개로, 4개를 다시 2개로 ... 재귀적으로 가장 작은 단위까지 정렬할 데이터를 쪼개면, if문만으로 정렬이 가능한 것이다. 그리고 이를 합쳐 가며 하나로 만들면 된다. 병합 정렬은 구현이 조금 까다롭다. 먼저, MergeSort 함수는 정렬 대상이 되는 데이터의 개수 정보가 아닌 정렬 대상의 범위 정보를 전달해야 한다. 정렬 대상을 계속 쪼개 가면서 진행할 것이기..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 1부터 N까지의 수가 한 줄로 무작위 순서로 서 있다. 이들을 크기 순서로 세우는 최적의 알고리즘은 무엇일까? 본 포스팅에서는 각종 정렬 알고리즘을 교재를 바탕으로 정리해보고자 한다. 정렬 알고리즘의 성능은 비교의 횟수와 이동의 횟수가 결정한다. 그리고 이를 기준으로 Big-O notation을 정한다. 1. 버블 정렬(Bubble Sorting) 버블 정렬은 연속한 두 개의 항을 비교하여, 앞의 것이 크기가 크면 순서를 바꾸고, 뒤의 것이 크면 순서를 유지하는 방법이다. 앞에서부터 뒤로 훑는 이 과정을 모든 수가 정렬될 때까지 반복한다. 버블 정렬의 코드는 아래와 같다. #include void Bu..