이론/알고리즘7 깊이 우선 탐색 DFS DFS(깊이 우선 탐색) 이란? DFS(깊이 우선 탐색)은 그래프나 트리 구조에서 한 정점으로부터 시작하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 주로 그래프의 모든 정점을 방문하거나 특정한 조건을 만족하는 정점을 찾는 데 사용됩니다. DFS는 스택(Stack) 또는 재귀 함수를 통해 구현될 수 있습니다. 시작 정점에서 출발하여 다음 정점으로 이동하고, 그 다음 정점에서 또 다시 다음 정점으로 이동하는 식으로 깊이를 우선적으로 탐색합니다. 이러한 과정에서 방문한 정점은 방문했다는 표시를 하고, 이미 방문한 정점이라면 더 이상 탐색을 진행하지 않고 이전 단계로 되돌아갑니다. DFS 코드 예시 (C#) 아래 코드는 그래프에서 깊이 우선 탐색을 수행하는 예시입니다. 각 정점을 리스트로 표현하.. 2024. 3. 28. 너비 우선 탐색 BFS BFS(너비 우선 탐색) 이란? BFS(너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점으로부터 인접한 모든 정점을 먼저 탐색하는 방법입니다. 이 알고리즘은 그래프 내의 모든 정점을 방문하고, 최단 경로를 찾거나 특정 조건을 만족하는 노드를 찾을 때 유용하게 사용됩니다. BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 탐색이 시작되면 시작 노드를 큐에 넣고 방문했다는 표시를 합니다. 그 후 큐에서 노드를 하나씩 꺼내어 해당 노드의 인접 노드를 큐에 넣고 방문했다는 표시를 합니다. 이 과정을 큐가 비어있을 때까지 반복합니다. 이러한 방식으로 탐색하면 시작 노드에서부터 거리가 가까운 노드부터 순차적으로 방문하게 됩니다. BFS 코드 예시 (C#) 아래 코드는 그래프를 구성하고 BFS .. 2024. 3. 27. 정렬 알고리즘 - 병합 정렬 (Merge sort) 병합 정렬 (Merge sort) 이란? 병합정렬(Merge Sort)은 분할정복 알고리즘의 일종으로, 주어진 배열을 반으로 나눈 뒤 각 부분 배열을 재귀적으로 정렬하고 병합하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘입니다. 병합정렬은 아래와 같은 과정으로 진행됩니다. 분할(Divide) : 입력 배열을 절반으로 나눕니다. 이 과정은 배열을 가능한 한 작은 크기의 부분 배열로 분할합니다. 정복(Conquer) : 분할된 부분 배열을 재귀적으로 정렬합니다. 각 부분 배열은 더 이상 분할할 수 없을 때까지 정렬됩니다. 병합(Combine): 정렬된 부분 배열을 다시 하나의 배열로 병합합니다. 이 때, 정렬된 부분 배열을 비교하여 정렬된 새로운 배열을 만듭니다. 병합정렬은 주어진 배열을 반으로 나누어 .. 2024. 3. 23. 분할 정복 알고리즘 (Divide and Conquer) 분할 정복 알고리즘 분할정복(Divide and Conquer)은 문제를 작은 부분으로 나누어 해결하는 알고리즘 설계 전략입니다. 이 방법은 주어진 문제를 세 단계로 나누어 처리합니다: 분할(Divide): 주어진 문제를 더 작고 해결하기 쉬운 작은 부분 문제들로 분할합니다. 이때, 문제는 일반적으로 동일한 크기의 작은 부분 문제들로 분할됩니다. 정복(Conquer): 분할된 작은 부분 문제들을 각각 해결합니다. 보통 재귀적으로 작은 부분 문제를 해결하는 방식을 사용합니다. 결합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 얻습니다. 이 과정에서 분할된 문제들의 해를 결합하여 최종 해를 얻습니다. 분할정복은 문제를 더 작고 해결하기 쉬운 작은 부분 문제들로 분할함으로써 전체적인 .. 2024. 3. 22. 이전 1 2 다음