[알고리즘] 29. BFS 너비 우선 탐색지난 글에서는 DFS 깊이 우선 탐색에 대해 정리했습니다. 이번 글에서는 그래프 탐색에서 DFS와 함께 가장 많이 등장하는 BFS에 대해 알아보겠습니다.BFS는 Breadth First Search의 줄임말로, 우리말로는 너비 우선 탐색이라고 합니다. DFS가 한 방향으로 깊게 들어가는 방식이라면, BFS는 시작점에서 가까운 곳부터 차례대로 탐색하는 방식입니다.BFS는 시작점에서 가까운 정점부터 차례대로 방문하는 탐색 알고리즘입니다.1. BFS란?BFS는 그래프나 트리에서 시작 정점과 가까운 정점부터 먼저 방문하는 탐색 방법입니다. 한 정점에서 바로 갈 수 있는 곳을 먼저 모두 확인하고, 그다음 거리의 정점을 확인합니다. 1 / \ ..
[알고리즘] 28. DFS 깊이 우선 탐색지난 글에서는 이분 탐색 응용에 대해 정리했습니다. 이번 글에서는 그래프 탐색에서 매우 자주 등장하는 DFS에 대해 알아보겠습니다.DFS는 Depth First Search의 줄임말로, 우리말로는 깊이 우선 탐색이라고 합니다. 이름 그대로 한 방향으로 갈 수 있는 곳까지 깊게 들어간 뒤, 더 이상 갈 곳이 없으면 되돌아와 다른 방향을 탐색하는 방식입니다.DFS는 한 방향으로 깊게 탐색한 뒤, 막히면 되돌아와 다른 경로를 탐색하는 알고리즘입니다.1. DFS란?DFS는 그래프나 트리에서 모든 정점을 방문할 때 사용하는 탐색 방법입니다. 특정 시작점에서 출발해 연결된 정점을 따라 최대한 깊게 이동합니다.1├─ 2│ ├─ 4│ └─ 5└─ 3위와 같은 구조에서 1번부..
[알고리즘] 27. 이분 탐색 응용지난 글에서는 이분 탐색 기초에 대해 정리했습니다. 이번 글에서는 단순히 특정 값을 찾는 것을 넘어, 이분 탐색을 조금 더 넓게 활용하는 방법을 알아보겠습니다.이분 탐색은 정렬된 배열에서 값을 찾을 때만 사용하는 알고리즘처럼 보일 수 있습니다. 하지만 실제 알고리즘 문제에서는 조건을 만족하는 가장 작은 값이나 조건을 만족하는 가장 큰 값을 찾을 때도 자주 사용됩니다.이분 탐색 응용의 핵심은 값을 직접 찾는 것이 아니라, 조건을 만족하는 경계 지점을 찾는 것입니다.1. 기본 이분 탐색과 응용 이분 탐색의 차이기본 이분 탐색은 정렬된 배열에서 target 값이 있는지 찾는 방식입니다.정렬된 배열: [1, 3, 5, 7, 9]target = 7결과: 인덱스 3하지만 응용 이분..
[알고리즘] 26. 이분 탐색 기초지난 글에서는 선형 탐색(Linear Search)에 대해 정리했습니다. 이번 글에서는 정렬된 데이터에서 값을 빠르게 찾는 탐색 방법인 이분 탐색(Binary Search)에 대해 알아보겠습니다.선형 탐색은 앞에서부터 하나씩 확인하는 방식입니다. 반면 이분 탐색은 탐색 범위를 절반씩 줄여가며 원하는 값을 찾습니다.이분 탐색은 정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 값을 찾는 알고리즘입니다.1. 이분 탐색이란?이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 방법입니다. 배열의 가운데 값을 확인한 뒤, 찾는 값이 가운데 값보다 작으면 왼쪽 절반만 탐색하고, 크면 오른쪽 절반만 탐색합니다.정렬된 배열: [1, 3, 5, 7, 9, 11, 13]찾을 값: 9가운데 ..
[알고리즘] 25. 선형 탐색(Linear Search)지난 글에서는 유니온 파인드(Union-Find)에 대해 정리했습니다. 이번 글부터는 탐색 알고리즘 영역으로 들어갑니다. 그 첫 번째 주제는 가장 기본적인 탐색 방법인 선형 탐색(Linear Search)입니다.선형 탐색은 배열이나 리스트의 값을 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 방법입니다. 복잡한 자료구조나 정렬이 필요하지 않아 알고리즘 입문 단계에서 가장 먼저 익히기 좋은 탐색 방식입니다.선형 탐색은 데이터를 앞에서부터 하나씩 확인하며 원하는 값을 찾는 가장 기본적인 탐색 방법입니다.1. 선형 탐색이란?선형 탐색은 데이터를 순서대로 하나씩 확인하는 탐색 방법입니다. 배열의 첫 번째 값부터 시작해서 마지막 값까지 차례대로 비교합니..
[알고리즘] 24. 유니온 파인드(Union-Find)지난 글에서는 그래프 기초에 대해 정리했습니다. 이번 글에서는 그래프와 집합 문제에서 자주 사용되는 유니온 파인드(Union-Find)에 대해 알아보겠습니다.유니온 파인드는 여러 원소가 있을 때, 두 원소가 같은 집합에 속해 있는지 빠르게 확인하고, 서로 다른 집합을 하나로 합치는 자료구조입니다. 알고리즘 문제에서는 서로소 집합, 연결 여부 확인, 사이클 판별 문제에서 자주 등장합니다.유니온 파인드는 여러 원소를 집합으로 관리하고, 같은 집합인지 빠르게 확인하는 자료구조입니다.1. 유니온 파인드란?유니온 파인드는 이름 그대로 두 가지 핵심 연산을 가지고 있습니다.연산의미union두 집합을 하나로 합친다.find어떤 원소가 속한 집합의 대표를 찾는다.예..
[알고리즘] 23. 그래프 기초지난 글에서는 트리 기초에 대해 정리했습니다. 이번 글에서는 알고리즘에서 매우 중요한 자료구조인 그래프(Graph)에 대해 알아보겠습니다.그래프는 여러 개의 대상이 서로 연결되어 있는 관계를 표현하는 자료구조입니다. 지하철 노선도, 도로망, 친구 관계, 컴퓨터 네트워크, 웹페이지 링크 구조처럼 연결 관계가 있는 문제에서 자주 사용됩니다.그래프는 정점과 간선을 이용해 데이터 사이의 연결 관계를 표현하는 자료구조입니다.1. 그래프란?그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 정점은 하나의 대상이고, 간선은 정점과 정점을 연결하는 선입니다.A --- B| |C --- D위 구조에서 A, B, C, D는 정점입니다. A와 B를 연결하는 선, ..
[알고리즘] 22. 트리 기초지난 글에서는 힙(Heap)에 대해 정리했습니다. 이번 글에서는 자료구조에서 매우 중요한 개념인 트리(Tree)에 대해 알아보겠습니다.트리는 데이터를 계층적으로 표현하는 자료구조입니다. 파일 시스템, 조직도, 댓글 구조, 카테고리, 이진 탐색 트리, 힙 등 다양한 곳에서 사용됩니다.트리는 하나의 시작점에서 여러 데이터가 가지처럼 뻗어나가는 계층형 자료구조입니다.1. 트리란?트리는 노드들이 부모와 자식 관계로 연결된 자료구조입니다. 가장 위에는 하나의 시작 노드가 있고, 그 아래로 여러 노드가 이어집니다. A / \ B C / \ \ D E F위 구조에서 A는 가장 위에 있는 노드입니다. B와 C는 A의 자식이고..