반응형 코딩테스트44 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나 특정 경로를 찾는 데 유용하며, 다양한 문제 해결에 활용됩니다.1. DFS의 개념DFS는 스택(Stack) 자료구조를 기반으로 하거나 재귀를 사용하여 구현되며, 그래프의 한 경로를 깊게 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 경로로 되돌아갑니다. 이를 "백트래킹(Backtracking)"이라고 합니다.(일반적으로 코딩테스트 문제 풀이 시 재귀로 dfs를 구현합니다.) 2. DFS의 동작 원리시작 정점을 방문하고 스택 또는 재귀 호출을 통해 탐색합니다.현재 정점의 인접 정점 중 방문하지 않은.. 2024. 12. 19. BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도 BFS(Breadth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 가까운 노드부터 탐색을 진행합니다. 경로를 찾거나 최단 거리를 계산하는 데 유용하며, 다양한 문제 해결에 활용됩니다. 1. BFS의 개념BFS는 큐(Queue) 자료구조를 기반으로 작동하며, 그래프의 각 레벨을 순차적으로 탐색합니다. 그래프의 각 정점을 방문하면서 모든 인접한 정점을 차례대로 탐색하므로, 깊이보다는 너비를 우선시합니다. 2. BFS의 동작 원리시작 정점을 큐에 삽입하고 방문 처리합니다.큐에서 정점을 하나씩 꺼내어 해당 정점의 모든 인접 정점을 탐색합니다.인접 정점 중 방문하지 않은 정점을 큐에 삽입하고 방문 처리합니다.큐가 빌 때까지 위 과정을 반복합니다.동작 구조도다음은 B.. 2024. 12. 19. 해시(Hash) 자료구조(C언어,STL, Java, Python 예시코드 포함) 해시 자료구조(Hash Data Structure)는 데이터 검색, 삽입, 삭제 작업을 빠르게 수행할 수 있는 매우 효율적인 자료구조입니다. 많은 프로그램과 애플리케이션에서 사용되며, 특히 키-값(key-value) 쌍 데이터를 저장하고 빠르게 접근해야 하는 경우에 유용합니다. 또한 값 추가, 삭제, 조회의 시간복잡도가 O(1)이라서 코딩테스트 문제에도 많이 활용되고 있습니다.1. 해시의 개념해시는 키(key)와 값(value)의 쌍으로 데이터를 저장합니다. 각 키는 고유하며, 해시 함수(hash function)를 사용하여 특정 키가 저장될 위치를 결정합니다. 이 과정은 다음과 같습니다:키를 입력값으로 해시 함수를 호출됩니다.해시 함수는 키를 고유한 해시 값(hash value)으로 변환합니다.이 해시.. 2024. 12. 19. 트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함) 1. 트라이(Trie) 자료구조란?트라이(Trie)는 문자열을 효율적으로 저장하고 검색하기 위해 설계된 트리(Tree) 기반 자료구조입니다. 주로 문자열 탐색, 자동 완성, 사전(dictionary) 구현에 사용됩니다. 이번 포스팅에서는 트라이의 구조, 구현 방법, 장단점, 활용 사례를 소개합니다. 2. 트라이의 원리와 구조(1) 트라이의 기본 개념**트라이(Trie)**는 각 노드가 문자열의 문자 하나를 나타내는 자료구조입니다.루트 노드에서 시작하여 문자열의 각 문자를 따라가며 데이터를 저장하거나 탐색합니다.문자열의 끝은 특별한 "종료 노드" 또는 플래그로 표시됩니다. (2) 트라이의 특징효율적인 검색: 문자열 검색 시간이 문자열 길이에 비례합니다. (O(L), L: 문자열 길이)공간 절약: 공통 접두.. 2024. 12. 18. 이전 1 ··· 7 8 9 10 11 다음 반응형
