본문 바로가기
반응형

dfs4

메모이제이션을 통한 성능개선 (3) - DFS DFS(Depth First Search)는 그래프 탐색 및 다양한 문제를 해결하는 데 널리 사용되는 알고리즘입니다. 이 알고리즘에 메모이제이션(Memoization)을 활용하면 중복 계산을 제거하고 효율성을 극대화할 수 있습니다. 이번 포스팅에서는 DFS와 메모이제이션의 결합 아이디어를 설명하고, C, Java, Python 예제 코드와 함께 성능 비교를 통해 차이를 분석하겠습니다.1. DFS와 메모이제이션이란?DFS (Depth First Search)깊이 우선 탐색으로, 그래프의 한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색합니다.백트래킹과 결합하여 다양한 문제를 해결할 수 있습니다.메모이제이션계산한 값을 저장하여 동일한 계산을 반복하지 않도록 하는 기술입니다.DFS와 결합하면 중복된 상태를 다시 .. 2024. 12. 21.
브루트포스, DFS, 백트래킹 차이점 정리 브루트포스(Brute Force), DFS(깊이 우선 탐색), 백트래킹(Backtracking)은 알고리즘 문제 해결에서 자주 언급되는 기법입니다. 이 세 가지는 개념적으로 유사한 점이 많지만, 실제 사용 방식과 효율성에서는 큰 차이가 있습니다. 오늘은 이 세 가지 알고리즘을 비교하면서 각 기법의 특징, 차이점, 사용 시기를 명확히 정리해보겠습니다.1. 브루트포스 (Brute Force)개념브루트포스는 가능한 모든 경우를 전부 탐색하는 방법입니다. 가장 직관적이고 간단한 알고리즘으로, 조건에 맞는 결과를 찾기 위해 모든 경우의 수를 시도합니다.특징구현이 간단.최적해를 반드시 찾음.효율성은 낮음.장점모든 경우를 탐색하므로 정확한 결과를 보장.직관적이고 쉽게 이해 가능.단점데이터 크기가 커질수록 시간복잡도가.. 2024. 12. 20.
DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도) 2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나best-coding.tistory.com2024.12.19 - [알고리즘] - BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복.. 2024. 12. 19.
DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도 DFS(Depth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 한 경로를 끝까지 탐색한 후에 다른 경로로 이동하는 방식으로 동작합니다. 모든 경로를 탐색하거나 특정 경로를 찾는 데 유용하며, 다양한 문제 해결에 활용됩니다.1. DFS의 개념DFS는 스택(Stack) 자료구조를 기반으로 하거나 재귀를 사용하여 구현되며, 그래프의 한 경로를 깊게 탐색한 후, 더 이상 탐색할 노드가 없을 때 이전 경로로 되돌아갑니다. 이를 "백트래킹(Backtracking)"이라고 합니다.(일반적으로 코딩테스트 문제 풀이 시 재귀로 dfs를 구현합니다.) 2. DFS의 동작 원리시작 정점을 방문하고 스택 또는 재귀 호출을 통해 탐색합니다.현재 정점의 인접 정점 중 방문하지 않은.. 2024. 12. 19.
반응형

티스토리툴바