반응형 Python31 BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도 BFS(Breadth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 가까운 노드부터 탐색을 진행합니다. 경로를 찾거나 최단 거리를 계산하는 데 유용하며, 다양한 문제 해결에 활용됩니다. 1. BFS의 개념BFS는 큐(Queue) 자료구조를 기반으로 작동하며, 그래프의 각 레벨을 순차적으로 탐색합니다. 그래프의 각 정점을 방문하면서 모든 인접한 정점을 차례대로 탐색하므로, 깊이보다는 너비를 우선시합니다. 2. BFS의 동작 원리시작 정점을 큐에 삽입하고 방문 처리합니다.큐에서 정점을 하나씩 꺼내어 해당 정점의 모든 인접 정점을 탐색합니다.인접 정점 중 방문하지 않은 정점을 큐에 삽입하고 방문 처리합니다.큐가 빌 때까지 위 과정을 반복합니다.동작 구조도다음은 B.. 2024. 12. 19. 트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함) 1. 트라이(Trie) 자료구조란?트라이(Trie)는 문자열을 효율적으로 저장하고 검색하기 위해 설계된 트리(Tree) 기반 자료구조입니다. 주로 문자열 탐색, 자동 완성, 사전(dictionary) 구현에 사용됩니다. 이번 포스팅에서는 트라이의 구조, 구현 방법, 장단점, 활용 사례를 소개합니다. 2. 트라이의 원리와 구조(1) 트라이의 기본 개념**트라이(Trie)**는 각 노드가 문자열의 문자 하나를 나타내는 자료구조입니다.루트 노드에서 시작하여 문자열의 각 문자를 따라가며 데이터를 저장하거나 탐색합니다.문자열의 끝은 특별한 "종료 노드" 또는 플래그로 표시됩니다. (2) 트라이의 특징효율적인 검색: 문자열 검색 시간이 문자열 길이에 비례합니다. (O(L), L: 문자열 길이)공간 절약: 공통 접두.. 2024. 12. 18. 스택(Stack) 자료구조란? (C언어, Java, Python 예시코드 포함) (1) 스택(Stack) 자료구조란?스택(Stack)은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 처리하는 선형 자료구조입니다. 즉, 가장 나중에 삽입된 데이터가 가장 먼저 제거됩니다. 이 특성 덕분에 함수 호출 관리, 계산기 구현, 문자열 역순 처리 등 다양한 프로그래밍 문제에서 활용됩니다. (2) 스택의 기본 동작삽입(Push): 스택의 맨 위에 데이터를 추가.삭제(Pop): 스택의 맨 위 데이터를 제거.확인(Peek 또는 Top): 스택의 맨 위 데이터를 제거하지 않고 확인. (3) 스택의 주요 특징후입선출(LIFO): 나중에 삽입된 데이터가 먼저 제거됨.제한된 접근: 데이터는 스택의 맨 위에서만 삽입 및 제거 가능.구현 방식: 배열 또는 연결 리스트를 사용. (4) 스.. 2024. 12. 18. 이전 1 ··· 5 6 7 8 다음 반응형
