본문 바로가기

Algorithm3

BFS(너비 우선 탐색) 알고리즘: 동작 원리와 Python 코드 구현 너비 우선 탐색 (Breadth-First Search)란?Breadth-First Search (BFS)는 현재 깊이 수준에 있는 모든 노드를 탐색한 후 다음 깊이 수준의 노드를 탐색하는 그래프 순회 알고리즘입니다. 가중치가 없는 그래프에서 최단 경로 문제를 해결하거나, 트리 탐색 및 연결 요소 분석 등에 널리 사용됩니다.BFS 알고리즘 설명BFS는 큐(queue) 자료구조를 사용하여 다음에 탐색할 노드를 추적합니다. 핵심 아이디어는 다음과 같습니다:시작 노드를 방문하고 큐에 추가합니다.큐가 비어있지 않은 동안:큐의 앞쪽에서 노드를 꺼냅니다.노드를 처리합니다 (예: 출력, 기록).방문하지 않은 모든 이웃 노드를 큐에 추가합니다.알고리즘 단계 (이진 트리)루트 노드를 시작으로 큐에 추가합니다.큐가 비어있.. 2025. 4. 29.
검색 알고리즘: 상세 설명과 Python 구현 탐색 알고리즘 소개탐색 알고리즘은 인공지능(AI)과 컴퓨터 과학의 핵심 도구입니다. 이 알고리즘은 문제 해결 에이전트가 복잡한 환경을 탐색하고, 해답을 찾으며, 의사결정을 내릴 수 있도록 도와줍니다. 탐색 알고리즘은 주어진 시작 상태로부터 목표 상태에 도달하는 경로를 찾기 위해 문제 공간 내의 가능한 경로를 체계적으로 조사합니다.일반적으로 탐색 알고리즘은 다음 두 가지 주요 범주로 나뉩니다:비정보 탐색 알고리즘 (Uninformed Search Algorithms): 이러한 알고리즘은 문제 정의 외에 도메인에 대한 구체적인 정보를 갖고 있지 않습니다. 목표의 방향을 예측하지 않고 모든 노드를 동일하게 취급하며, 무작위로 탐색 공간을 확장합니다. 복잡하거나 규모가 큰 환경에서는 비효율적일 수 있지만, 특정.. 2025. 4. 28.
Heap 구조 설명 및 파이썬 예제 힙(Heap)은 이진 트리 기반의 자료구조로, 힙 속성(Heap Property)을 만족합니다:- 최소 힙(Min-Heap): 모든 부모 노드는 자식 노드보다 작거나 같습니다.- 최대 힙(Max-Heap): 모든 부모 노드는 자식 노드보다 크거나 같습니다.** 힙은 정렬된 구조는 아니지만, 가장 작은 값(또는 가장 큰 값)이 항상 루트(최상단)에 위치한다는 것을 보장합니다. 1. 최소 힙 예제다음 입력이 주어지면: [5, 3, 8, 1, 2]최소힘은 다음과 같은 이진 트리로 입력 갑을 변환함:그리고 새롭게 저장된 배열은 다음과 같음: [1, 2, 8, 5, 3]각 노드의 인덱스 i에 대해서:왼쪽 자식 노드 = 인덱스 2i + 1오른쪽 자식 노드 = 인덱스 2i + 2 2. 실제 힙 구조가 사용되는 경우들.. 2025. 4. 19.

티스토리툴바