[알고리즘 이론] 백트래킹 (Back Tracking)

최근 [알고리즘 이론] 시리즈에서는 DFS와 BFS 같은 그래프 탐색 알고리즘을 살펴보았습니다. 이번 글에서는 완전 탐색의 일종인 백트래킹에 대해 알아봅니다. 백트래킹은 DFS처럼 깊이 우선으로 탐색하지만, 조건을 만족하지 못하는 분기를 빨리 가지 치기하여 불필요한 경로를 탐색하지 않는다는 점이 특징입니다. [알고리즘 이론] DFS(깊이 우선 탐색)BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요.growingegg.tistory.com 백트레킹 개념점진적 해결 – 백트래킹 알고리즘은 후보 해를 하나씩 쌓아가며 진행합니다. 현재까지 만든 부분 해가 조건을 만족할 수..
알고리즘/알고리즘 이론 2025. 7. 29. 19:29
[알고리즘 이론] DFS(깊이 우선 탐색)

BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요. [알고리즘 이론] 해시 테이블, 그래프, 트리, 힙오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로growingegg.tistory.com DFS(Depth-first Search, 너비 우선 탐색)개념DFS는 가능한 깊게 내려가며 그래프를 탐색한 뒤, 더 이상 갈 수 없으면 다른 분기점으로 백트랙킹(backtracking) 하여 다른 경로를 탐색하는 알..
알고리즘/알고리즘 이론 2025. 7. 28. 16:43
[알고리즘 이론] BFS(너비 우선 탐색)

BFS와 DFS는 그래프나 트리를 탐색하는 대표적인 알고리즘입니다. 두 알고리즘은 동작방식과 사용하는 자료구조가 다릅니다. 혹시나 그래프나 트리에 대해 알고 싶다면 아래 링크를 참조하세요. [알고리즘 이론] 해시 테이블, 그래프, 트리, 힙오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로growingegg.tistory.com BFS(Breadth-first Search, 너비 우선 탐색) 개념최단 경로를 탐색하거나 계층 단위로 노드를 탐색해야 할 때 유리한 알고리즘입니다. 시작 지점부터 현재 계층의 노드를 전부 탐색하고 다음 계층으로 넘어갑..
알고리즘/알고리즘 이론 2025. 7. 28. 16:13
[알고리즘 이론] 퀵 정렬, 병합 정렬, 힙 정렬, 계수 정렬

이전에 시간 복잡도가 O(n^2)인 알고리즘에 대해 다뤄보았는 데요. [알고리즘] 정렬(버블, 선택, 삽입)버블정렬 *정의: 리스트 혹은 배열의 인접한 두 요소를 비교하여 정렬하는 방식. 첫번째 요소부터 마지막 요소까지 정렬을 진행하고 마지막 요소를 제외한 나머지 리스트로 모든 요소가 정렬될growingegg.tistory.com 이번에는 시간복잡도가 O(nlogn)보다 빠른 정렬 알고리즘에 대해 알아보도록 하겠습니다. 퀵 정렬 (Quick Sort)개념분할 정복 방식(Divide-Conquer)의 비교 기반 정렬 알고리즘입니다. 배열에서 정렬의 기준이 되는 피벗(pivot) 값을 선택한 뒤, 피벗 값을 기준으로 큰 요소와 작은 요소로 배열을 분할합니다. 이후 분할된 하위 배열에 대해 같은 과정을 반복..
알고리즘/알고리즘 이론 2025. 7. 28. 14:27
[알고리즘 이론] 해시 테이블, 그래프, 트리, 힙

오늘은 자료구조의 나머지 부분인해시 테이블, 그래프, 트리, 힙에 대해서다뤄 보도록 하겠습니다. 그럼 들어가 볼까요? 해시 테이블(Hash Table)해시 테이블은 데이터를 키(key)와 값(value)의 쌍으로 저장하는 자료 구조입니다. python을 주로 다루는 분들은 Dictionary, java나 C++은 MAP이라는 자료 구조로 익숙할 것입니다. 여기서 키(key)는 데이터에 접급하기 위한 고유한 식별자이며 값(value)은 키에 대응하는 실제 데이터입니다. 앞서 배운 배열을 기준으로 생각해보면 데이터의 위치를 나타내는 인덱스가 키 값이며 배열에 저장된 데이터가 실제 값인 것입니다. 다만 배열은 연솟된 메모리를 바탕으로 인덱스도 연속된 정수로 표현되지만 해시 테이블은 다양한 형태의 데이터 ..
알고리즘/알고리즘 이론 2025. 7. 14. 17:59
[알고리즘 이론] 배열, 리스트, 스택, 큐, 해시 테이블 자료 구조

배열 ( Array ) 개념 같은 자료형의 데이터를 연속된 메모리 공간에 순서대로 저장하는 자료 구조. 특징고정 크기: 배열은 선언 시에 크기가 고정되며, 이후에는 크기 변경이 불가합니다. 연속된 메모리 : 데이터들이 메모리 상에 연속적으로 존재하고 있습니다. 같은 자료형 : 배열의 모든 요소는 동일한 자료형 인덱스를 통한 접근 : 배열은 연속된 메모리에 존재하며 모든 요소는 동일한 크기를 가지고 있기 때문에 배열의 시작 주소만 알면 인덱스를 통해 나머지 데이터에 바로 접근할 수 있습니다. 기본 동작 검색🕛시간 복잡도 : O( 1 )💡동작 설명배열에는 데이터의 시작 주소가 저장되어 있습니다. 배열의 크기가 고정이기 때문에 배열의 시작 위치로부터 n번째 데이터에 접급할 경우 아래와 같은 방식으로 데이..
알고리즘/알고리즘 이론 2025. 6. 30. 16:53
[알고리즘 이론] 시간 복잡도와 공간 복잡도

시간 복잡도 개념: 알고리즘이 수행되는 데 걸리는 시간을 입력 값(n)의 크기에 따라 표현한 것.공간 복잡도 개념: 알고리즘이 사용하는 메모리 양을 입력 값(n)에 따라 표현한 것점근적 표기법(Asymptonic Notation)개념: 공간복잡도와 시간복잡도를 수학적으로 표현할 때 쓰는 표기법, 중요하지 않은 계수나 상수를 제거하여 가장 큰 영향을 미치는 항만 표현한다. 오메가 표기법(Big-Omega, Ω): 최선의 경우를 나타냄. 쎄타 표기법(Big-Theta, θ): 평균적인 경우를 나타냄 빅오 표기법(Big-O, o): 최악의 경우를 나타냄 빅오 표기법(Big-O)알고리즘에서는 주로 최악인 경우를 상정하여 빅오 표기법을 사용한다. 최악의 경우 입력값 n이 주어졌을 때를 상정한다.표기 예시O(1)..
알고리즘/알고리즘 이론 2025. 6. 26. 12:52
[알고리즘 이론] 트라이(Trie) 알고리즘 개념 정리 및 문제 추천

트라이(Trie)개념 문자열을 탐색 및 저장을 효율적으로 할 수 있는 트리 기반의 자료 구조 단어 검색, 자동 완성, 사전 구현 등의 작업에 유리하다. 문자열 저장 방식 각 노드는 공통된 접두사를 공유중볻된 부분을 제거하여 공간을 절약 시간 복잡도트리 생성: O(n * L), n은 문자열의 개수, L은 문자열의 길이   문자열 탐색: O(L), L은 문자열의 길이  공간 복잡도: 각 문자마다 노드를 생성하므로 공간을 많이 차지하지만 접두사를 공유하는 문자가 많을 수록 단어를 효율적으로 저장 가능풀이 방식 삽입루트 노드에서 시작하여 문자열의 첫 번째 문자부터 시작문자별로 노드를 추가하며, 해당 문자가 이미 존재하는 경우 기존 노드를 재사용문자열의 끝에 도달하면, 해당 노드에 단어의 끝임을 표시삭제 문자열의..
알고리즘/알고리즘 이론 2025. 1. 7. 16:11
1 2 3