DATA101

본 포스팅에서는 너비 우선 탐색이라고 불리는 BFS(Breadth-First Search)에 대해 알아봅니다. 📚 목차 1. BFS 알고리즘이란? 2. BFS 알고리즘 동작 과정 3. BFS 파이썬 구현 3.1. 소스코드 설명 3.2. 전체 소스코드 1. BFS 알고리즘이란? BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘입니다. BFS 알고리즘은 언제 사용하면 좋을까요? BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘입니다. 그리고 "미로를 빠져나가는 최단 거리(경로)"를 구하는 문제 등에서 효과적으로 활용할 수 있는 알고리즘입니다...

본 포스팅에서는 깊이 우선 탐색 DFS(Depth-First Search) 알고리즘에 대해 알아봅니다. 📚 목차 1. DFS 알고리즘이란? 2. DFS 알고리즘 동작 과정 3. DFS 파이썬 구현 1. DFS 알고리즘이란? DFS(Depth-First Search)는 그래프 전체를 탐색하는 방법(i.e., 완전 탐색) 중 하나로, '깊이'를 우선적으로 탐색하는 알고리즘입니다. DFS는 한 노드를 시작으로 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다. 예를 들어, DFS 알고리즘은 미로 탐색 시 한 방향으로 모든 노드를 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법입니다...

본 포스팅에서는 큐(Queue) 자료구조에 대해 알아봅니다. 📚 목차 1. 큐(Queue) 자료구조란? 2. 큐 동작 예시 3. 큐 구현(Python) 1. 큐(Queue) 자료구조란? 큐 자료구조는 선입선출(先入先出, First In First Out, 줄여서 FIFO) 구조로 흔히 놀이공원 내 놀이기구 대기줄에 비유합니다(그림 1 참고). 즉, 놀이기구 대기줄에 먼저 선 사람(데이터 입력)이 먼저 놀이기구를 타는(데이터 출력/제거) 방식입니다(단, 새치기는 없다고 가정). 큐 자료구조는 아래 2가지 핵심적인 함수로 동작합니다. 데이터 삽입(append) 데이터 삭제(popleft) 큐 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow)가 발생하지 않도록 유의해야 합니다..

본 포스팅에서는 스택(Stack) 자료구조에 대해 알아봅니다. 📚 목차 1. 스택(Stack) 자료구조란? 2. 스택 동작 예시 3. 스택 구현(Python) 1. 스택(Stack) 자료구조란? 스택 자료구조는 먼저 들어온 데이터가 늦게 나가는 형태의 자료구조로서 선입후출(先入後出) 방식입니다. 스택 자료구조는 아래의 그림 1 과 같이 입구와 출구가 동일한 형태로 표현할 수 있으며 "박스 쌓기"를 연상하시면 기억하기 편합니다. 스택 자료구조는 아래 2가지 핵심적인 함수로 동작합니다. 데이터 삽입(Push) 데이터 삭제(Pop) 스택 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow) 발생에 유의해야 합니다. 오버플로우: 어떠한 자료구조가 저장할 수 있는 데이터의 크기를 초..

본 포스팅에서는 그리디(Greedy) 알고리즘에 대해 알아봅니다. 1. 그리디 알고리즘이란? 그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전적 의미로서 "탐욕스러운"이라는 뜻을 갖고 있습니다(그림 2 참고). 즉, 그리디 알고리즘은 주어진 문제를 프로그래밍을 통해 탐욕스럽게 풀어내는 알고리즘입니다. 여기서 "탐욕스러운"이라는 말은 그리디 알고리즘이 주어진 상황에서 최선의 옵션만 선택하며 현재의 선택이 향후에 미칠 영향은 고려하지 않는다는 의미입니다. 2. 특징 그리디 알고리즘 문제에서는 주로 "가장 큰 숫자 순서대로" 혹은 "가장 짧은 경로 순으로"와 같은 조건을 제시해 줍니다. 이러한 조건은 대체로 정렬 알고리즘으로 해결할 수 있다는 점에서 그리디 알고리즘은 정렬 알고리즘과 세트로 주어지는 ..