이론87 너비 우선 탐색 BFS BFS(너비 우선 탐색) 이란? BFS(너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점으로부터 인접한 모든 정점을 먼저 탐색하는 방법입니다. 이 알고리즘은 그래프 내의 모든 정점을 방문하고, 최단 경로를 찾거나 특정 조건을 만족하는 노드를 찾을 때 유용하게 사용됩니다. BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 탐색이 시작되면 시작 노드를 큐에 넣고 방문했다는 표시를 합니다. 그 후 큐에서 노드를 하나씩 꺼내어 해당 노드의 인접 노드를 큐에 넣고 방문했다는 표시를 합니다. 이 과정을 큐가 비어있을 때까지 반복합니다. 이러한 방식으로 탐색하면 시작 노드에서부터 거리가 가까운 노드부터 순차적으로 방문하게 됩니다. BFS 코드 예시 (C#) 아래 코드는 그래프를 구성하고 BFS .. 2024. 3. 27. 자료구조 - 큐(Queue) 큐(Queue) 이란? 큐(Queue)는 데이터를 선형 구조로 저장하는 자료구조로, FIFO(First-In-First-Out, 선입선출) 원칙을 따릅니다. 이는 처음 추가된 데이터가 처음으로 제거되는 구조를 의미합니다. 즉, 가장 먼저 저장된 요소가 가장 먼저 나오는 특징을 가지고 있습니다. 새로운 데이터는 큐의 뒷부분에 추가되고, 데이터는 큐의 앞부분에서 제거됩니다. 이로써 데이터는 일렬로 정렬되어 관리됩니다. 주로 데이터 처리 과정에서 선입선출의 원칙이 필요한 경우에 큐가 활용됩니다. 큐 코드 예시 (C#) 아래 코드는 C#에서 queue 활용의 예시입니다. using System; using System.Collections.Generic; public class QueueExample { pub.. 2024. 3. 26. 자료구조 - 스택(Stack) 스택(Stack) 이란? 스택(Stack)은 데이터 구조 중 하나로, 후입선출(LIFO, Last In First Out)의 원리를 따릅니다. 이 말은 가장 최근에 추가된 항목이 가장 먼저 제거되는 구조를 의미합니다. 새로운 데이터는 스택의 맨 위에 추가되며, 마지막에 추가된 데이터가 먼저 제거됩니다. 주로 함수 호출, 재귀 알고리즘, 괄호 검사, 미로 탐색 등과 같은 다양한 응용 프로그램에서 사용됩니다. 스택은 데이터를 저장하고 접근하는데 유용하며, 특히 데이터의 순서가 중요한 경우에 많이 활용됩니다. 스택 코드 예시 (C#) 아래 코드는 C#에서 stack 활용의 예시입니다. using System; using System.Collections.Generic; public class StackExam.. 2024. 3. 24. 정렬 알고리즘 - 병합 정렬 (Merge sort) 병합 정렬 (Merge sort) 이란? 병합정렬(Merge Sort)은 분할정복 알고리즘의 일종으로, 주어진 배열을 반으로 나눈 뒤 각 부분 배열을 재귀적으로 정렬하고 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘입니다. 병합정렬은 아래와 같은 과정으로 진행됩니다. 분할(Divide) : 입력 배열을 절반으로 나눕니다. 이 과정은 배열을 가능한 한 작은 크기의 부분 배열로 분할합니다. 정복(Conquer) : 분할된 부분 배열을 재귀적으로 정렬합니다. 각 부분 배열은 더 이상 분할할 수 없을 때까지 정렬됩니다. 병합(Combine): 정렬된 부분 배열을 다시 하나의 배열로 병합합니다. 이 때, 정렬된 부분 배열을 비교하여 정렬된 새로운 배열을 만듭니다. 병합정렬은 주어진 배열을 반으로 나누어 .. 2024. 3. 23. 이전 1 2 3 4 5 ··· 22 다음