알고리즘
19편
알고리즘 · 자료구조 · 트리
이진 탐색 트리 (Binary Search Tree) 핵심 메커니즘과 복잡도
2026. 9. 4.
이진 트리와 이진 탐색 트리의 원리 이진 트리(binary tree)란 각 노드에 최대 두 개의 자식 노드가 있는 트리 자료 구조다. 이진 탐색 트리(binary search tree)란 정렬된 이진 트리로서 모든 노드는 자신의 왼쪽 브랜치 노드들보다 큰 값을 갖고, 오른쪽 브랜치 노드들보다 작은 값을 갖는 특징을 가진다
자료 구조 · 알고리즘
[자료 구조/알고리즘] 문자열
2025. 7. 25.
문자열은 연속된 문자들이 그룹화되어 구성된 자료 구조이다. 따라서 데이터를 그룹화한 추상 자료형인 컬렉션(collection)의 다양한 자료 구조로 문자열을 구조화할 수 있으며 다양한 자료 구조 탐색 알고리즘을 사용하여 부분 문자열들을 탐색 및 비교하는 등의 문제를 해결할 수 있다. 선형 컬렉션 그래프 문자열을 그래프 자
자료 구조 · 알고리즘
[자료 구조/알고리즘] 백트래킹
2025. 7. 25.
백트래킹(backtracking)(또는 역추적) 알고리즘이란 최적의 해결책을 찾기 위해 모든 가능한 방법을 후보(candidate)로 구성한 후, 점진적으로 후보들을 시도하면서 유효한 후보가 아닐 경우(문제의 정답 조건을 만족하지 않을 경우) 문제 해결 과정에서 제외하고 되돌아가 다른 후보를 시도(백트랙)하는 과정을 반복
자료 구조 · 알고리즘
[자료 구조/알고리즘] 백트래킹 구현
2025. 7. 25.
N 퀸 문제 노드: 퀸들의 현재 배치 상태 간선: 한 행에서 다음 행으로 퀸을 놓는 것 가지치기: 퀸을 놓으려는 위치가 이미 다른 퀸의 공격 범위에 있는 경우 퀸을 배치하지 않는 것 루트 노드: 퀸이 놓이지 않은 초기 상태 리프 노드: 더 이상 퀸을 놓을 수 없는 최종 상태 정답인 경우: 모든 퀸이 놓인 상태 정답이 아닌
자료 구조 · 알고리즘
[자료 구조/알고리즘] 연결 리스트 구현
2025. 7. 25.
단일 연결 리스트 더미 노드 미사용 더미 노드 사용 이중 연결 리스트 더미 노드 미사용 더미 노드 사용 LRU(least recently used) 캐시 구현
알고리즘
[알고리즘] 정렬
2025. 6. 12.
버블 정렬 리스트의 데이터를 처음부터 끝까지 하나씩 선택하여(N번), 인접한 데이터와 크기를 비교하여 정렬 순서에 맞게 서로 위치를 바꾸는 작업을 더 이상 비교할 데이터가 없을 때까지 최대 N번 수행한다. 정렬 알고리즘 중 구현이 가장 간단하지만 가장 비효율적인 알고리즘이다. 버블 정렬은 안정 정렬이다. 시간 복잡도 최선