Algorithm3 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS) 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)는 그래프 탐색 알고리즘의 두 가지 대표적인 방식이다. 이 두 알고리즘은 각기 다른 방식으로 그래프를 순회하며, 그 특성과 적합한 적용 사례가 서로 다르다. 이 글에서는 DFS와 BFS의 특징, 구현 방식, 그리고 적합한 활용 사례를 살펴본다.깊이 우선 탐색(DFS)특징DFS는 그래프에서 한 경로를 따라 끝까지 탐색한 뒤, 다시 돌아와 다른 경로를 탐색하는 방식이다. 이 알고리즘은 재귀적으로 호출되거나 스택을 사용하여 구현된다. 주요 특징은 다음과 같다:경로 기반 탐색: 한 경로를 끝까지 탐색한 뒤 다른 경로로 이동한다.스택 사용: 재귀 호출이나 명시적인 스택 자료구조를 사용한다... 2025. 1. 8. 시간복잡도와 Big O 표기법 컴퓨터 과학에서 알고리즘의 효율성을 평가할 때 중요한 개념 중 하나가 시간복잡도다. 시간복잡도는 주어진 입력 크기에 따라 알고리즘이 실행되는 시간을 나타낸다. 이를 표현하는 데 자주 사용되는 것이 바로 Big O 표기법이다.Big O 표기법Big O 표기법은 알고리즘의 성능을 표현하는 데 사용되는 수학적 표기법이다. 이 표기법은 가장 나쁜 경우(worst-case) 시나리오를 고려하여 알고리즘의 실행 시간을 설명한다. 주로 입력 크기 ( n )이 무한대로 커질 때 알고리즘의 성능을 어떻게 예측할 수 있는지를 나타낸다.Big O 표기법의 주요 유형O(1) - 상수 시간 복잡도알고리즘의 실행 시간이 입력 크기에 관계없이 일정하다.예: 배열의 특정 인덱스에 접근하는 연산.예시: arr[5]O(log n) - .. 2024. 7. 5. Tower of Hanoi(하노이의 탑) 재귀 함수를 말할 때 빠지지 않고 등장하는 예시인 하노이의 탑 문제에 대해 풀이해 보려 한다. 하노이의 탑은 프랑스의 수학자인 에두아르 뤼카(Édouard Lucas)가 클라우스 교수(professeur N. Claus)라는 필명으로 1883년에 발표하였다. 1년 후 드 파르빌(Henri de Parville)은 Claus가 Lucas의 애너그램(anagram; 어구전철) 임을 밝히면서 다음과 같은 이야기로 하노이의 탑을 소개하였다. "인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이.. 2023. 12. 29. 이전 1 다음