공부한 내용 기록하기 공부한 내용 기록하기

1. 삼진 탐색이란?삼진 탐색(Ternary Search)은 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘으로, 탐색 범위를 세 부분으로 나누어 진행한다. 이진 탐색(Binary Search)이 탐색 범위를 두 부분으로 나누는 것과 달리, 삼진 탐색은 탐색 범위를 세 부분으로 나누기 때문에 비교 횟수를 줄일 수 있다.삼진 탐색은 이진 탐색과 유사하지만, 각 단계에서 두 개의 중간점을 확인한다는 점이 차별화된다. 주로 범위가 넓고 정렬된 배열에서 빠른 탐색이 필요할 때 사용된다.2. 삼진 탐색의 동작 원리삼진 탐색은 다음과 같은 과정으로 수행된다:탐색 범위의 첫 번째와 두 번째 중간점을 계산한다.목표 값을 중간점들과 비교한다.목표 값이 첫 번째 중간점보다 작으면 왼쪽 구간 탐색목표 값이 두 중간점 사이에 ..

1. 이진 탐색 트리(BST) 탐색이란?이진 탐색 트리(Binary Search Tree, BST) 탐색은 이진 탐색 트리 구조에서 특정 값을 찾는 알고리즘이다.이진 탐색 트리는 다음과 같은 특성을 가진다:각 노드의 왼쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 작다.각 노드의 오른쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 크다.이러한 구조를 활용해 데이터를 정렬된 상태로 유지하며 효율적인 탐색을 가능하게 한다.이진 탐색 트리 탐색은 평균적으로 O(log n)의 시간 복잡도를 가지며, 최악의 경우 O(n)의 시간 복잡도를 가진다.2. 이진 탐색 트리 탐색의 동작 원리이진 탐색 트리 탐색은 다음과 같은 절차로 이루어진다:루트 노드에서 시작한다.현재 노드의 값과 찾고자 하는 값을 비교한다.찾는 ..

1. 너비 우선 탐색이란?너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 시작 노드에서 가까운 노드를 먼저 탐색한 후, 점차 더 깊은 노드를 탐색하는 방식으로 동작한다.BFS는 큐(Queue, 선입선출 구조)를 활용하며, 최단 경로 탐색, 네트워크 분석, 퍼즐 해결 등 다양한 분야에서 사용된다.2. 너비 우선 탐색의 동작 원리BFS는 다음과 같은 과정으로 수행된다:시작 노드를 큐에 삽입하고 방문 처리를 한다.큐에서 노드를 하나 꺼내고, 해당 노드와 연결된 모든 인접 노드를 확인한다.인접 노드 중 아직 방문하지 않은 노드를 큐에 삽입하고 방문 처리를 한다.큐가 빌 때까지 2번과 3번 과정을 반복한다.2.1 너비 우선 탐색 과정 예제다음과..

1. 깊이 우선 탐색이란?깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 특정 경로를 따라 최대한 깊이 내려간 후 더 이상 진행할 수 없으면 되돌아가면서 미탐색 노드를 방문하는 방식으로 동작한다.DFS는 스택(LIFO: 후입선출) 구조를 활용하며, 재귀 호출이나 명시적인 스택 자료구조를 사용해 구현할 수 있다.2. 깊이 우선 탐색의 동작 원리DFS는 다음과 같은 과정으로 수행된다:시작 노드를 방문하고 방문 표시를 한다.현재 노드에서 인접한 노드를 차례대로 탐색한다.아직 방문하지 않은 노드가 있다면 해당 노드로 이동하고 위 과정을 반복한다.더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다.2.1 깊이 우선 탐색 과정 예제다음과 같은 그래..

1. 해시 탐색이란?해시 탐색(Hash Search)은 해시 함수를 이용해 데이터를 빠르게 저장하고 검색하는 탐색 알고리즘이다. 데이터를 키(key)로 변환한 후, 해당 키를 기반으로 빠르게 값을 찾을 수 있도록 설계되었다. 평균적으로 O(1)의 시간 복잡도를 제공하기 때문에 대용량 데이터에서 매우 효율적이다.2. 해시 탐색의 동작 원리해시 탐색은 다음과 같은 과정으로 이루어진다:해시 함수(Hash Function) 생성: 입력 데이터를 고유한 키로 변환한다.해시 테이블(Hash Table) 저장: 변환된 키를 인덱스로 활용해 데이터를 저장한다.데이터 검색: 동일한 해시 함수를 사용해 키를 계산하고 해당 위치에서 데이터를 검색한다.2.1 해시 탐색 과정 예제예를 들어, 이름 목록에서 "Alice"를 검색..

1. 이진 탐색이란?이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 효율적으로 찾는 탐색 알고리즘이다. 탐색 과정에서 중간 값을 기준으로 탐색 범위를 절반씩 줄여가며 목표 값을 찾는다.이진 탐색은 순차 탐색보다 훨씬 빠른 O(log n)의 시간 복잡도를 가지며, 데이터의 크기가 커질수록 성능 차이가 커진다.2. 이진 탐색의 동작 원리이진 탐색은 다음과 같은 과정으로 수행된다:중앙값 선택: 배열의 중앙 요소를 선택한다.값 비교: 중앙값과 목표 값을 비교한다.범위 축소:목표 값이 중앙값보다 작으면 왼쪽 절반에서 탐색목표 값이 중앙값보다 크면 오른쪽 절반에서 탐색재귀 또는 반복: 목표 값을 찾을 때까지 위 과정을 반복한다.2.1 이진 탐색 과정 예제목표 값: 22정렬된 배열: [10, 1..

1. 순차 탐색이란?순차 탐색(Linear Search)은 데이터 집합에서 원하는 값을 찾을 때 처음부터 끝까지 차례대로 확인하는 탐색 알고리즘이다. 가장 기본적이고 단순한 형태의 탐색 방법으로, 정렬 여부와 관계없이 사용할 수 있다.2. 순차 탐색의 동작 원리순차 탐색은 다음과 같은 과정으로 동작한다:첫 번째 요소부터 시작하여 목표 값과 비교한다.목표 값을 찾으면 해당 인덱스를 반환한다.끝까지 확인했지만 목표 값이 없으면 -1을 반환한다.2.1 순차 탐색 과정 예제다음은 배열에서 숫자 6을 찾는 과정이다:입력 배열: [3, 5, 6, 8, 9]첫 번째 요소 3과 비교 → 불일치두 번째 요소 5와 비교 → 불일치세 번째 요소 6과 비교 → 일치 (탐색 종료)출력: 인덱스 22.2 순차 탐색 예제 코드 (..

1. 탐색 알고리즘이란?탐색 알고리즘(Search Algorithm)은 주어진 데이터에서 원하는 값을 찾는 과정에서 사용되는 알고리즘이다. 탐색은 데이터베이스 검색, 네트워크 경로 탐색, 정보 검색 등 다양한 분야에서 필수적으로 활용된다. 탐색 알고리즘의 성능은 주로 시간 복잡도와 공간 복잡도로 평가된다.2. 탐색 알고리즘의 분류탐색 알고리즘은 크게 선형 탐색(Linear Search), 이진 탐색(Binary Search), 해시 기반 탐색(Hash Search), 트리 기반 탐색(Tree Search), 그래프 탐색(Graph Search)으로 나눌 수 있다.선형 탐색: 데이터의 처음부터 끝까지 차례로 확인하며 원하는 값을 찾는 방식 (예: 순차 탐색)이진 탐색: 정렬된 데이터에서 중앙값을 기준으로 ..