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

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

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

1764번: 듣보잡 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력: 듣보잡의 수와 그 명단을 사전순으로 출력한다. 문제를 보자마자 "교집합->set을 이용하자" 를 떠올렸다. Intersection..

백준 2164번: 카드 2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 우선순위 큐(Priority Queue)란? 우선순위 큐 또한 큐와 마찬가지로 enqueue, dequeue 연산이 있으나, 연산의 결과에서 차이를 보인다. 뒤에서 데이터를 enqueue하고 앞에서 dequeue 하는 큐와 달리, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 프로그래머가 결정한 기준에 따라 데이터에 우선순위를 매기고, 해당 순서에 따라 데이터를 꺼낼 수 있도록 하는 것이다. 우선순위 큐는 아래 세 가지 방법으로 구현한다. 배열을 기반으로 구현 연결 리스트를 기반으로 구현 힙(heap)을 기반으로 구현 배열을 기반으로 구현 배열을 기반으로 구현..