ITPE * JackerLab

개요해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)를 통해 고정된 인덱스로 변환하여 값을 저장하는 자료구조이다. 평균적으로 삽입, 삭제, 탐색 연산이 **O(1)**로 매우 빠르며, 파이썬의 dict, set, 자바의 HashMap, C++의 unordered_map 등 거의 모든 언어의 핵심 자료구조로 활용된다.1. 개념 및 정의 항목 설명 키(Key)값을 식별하기 위한 고유한 값값(Value)저장할 실제 데이터해시 함수키를 배열 인덱스로 변환하는 함수버킷(Bucket)해시 충돌이 발생할 수 있는 배열의 각 칸해시 함수는 키를 숫자로 변환해 해시 테이블의 인덱스로 매핑한다.2. 해시 함수와 충돌해시 함수(Hash Function): hash(key) % tabl..

개요해시 탐색(Hash Search)은 키(key)를 해시 함수(hash function)를 통해 해시 테이블의 인덱스로 변환한 뒤, 해당 위치에서 값을 직접 찾아내는 탐색 알고리즘이다. 평균적으로 **O(1)**의 시간 복잡도를 제공하며, 가장 빠른 검색 기법 중 하나로 꼽힌다. 해시맵(HashMap), 딕셔너리(Dictionary), 셋(Set) 등 현대 프로그래밍 언어의 기본 자료구조에서도 사용된다.1. 개념 및 정의해시 탐색은 다음 과정을 거쳐 값을 찾는다:**입력 키(key)**를 해시 함수에 입력하여 해시 값(index)을 얻는다.해당 인덱스에 접근하여 값을 확인한다.해시 충돌이 발생할 경우에는 충돌 해결 기법(체이닝, 개방 주소법 등)을 통해 탐색을 이어간다.2. 해시 함수와 해시 테이블 구..

개요이진 탐색(Binary Search)은 정렬된 데이터에서 중간 값을 기준으로 절반씩 범위를 줄여가며 값을 찾는 탐색 알고리즘이다. 선형 탐색보다 훨씬 빠른 **O(log n)**의 시간 복잡도를 가지며, 배열이나 리스트에서 특정 값을 빠르게 찾아야 할 때 가장 널리 쓰이는 탐색 방식 중 하나다.1. 개념 및 정의이진 탐색은 다음과 같은 절차로 작동한다:데이터가 반드시 오름차순 또는 내림차순으로 정렬되어 있어야 한다.시작점(left)과 끝점(right)을 설정하고, 중간값(mid)을 계산한다.mid 위치의 값과 찾는 값을 비교한다.일치 → 탐색 성공더 작음 → right = mid - 1더 큼 → left = mid + 1범위가 좁아질 때까지 반복한다.2. 동작 원리 단계 설명 1시작 인덱스와 끝 인..

개요선형 탐색(Linear Search)은 데이터를 처음부터 끝까지 순차적으로 확인하며 찾고자 하는 값을 찾는 가장 기본적인 탐색 알고리즘이다. 정렬 여부와 상관없이 사용 가능하며, 구현이 매우 간단해 초보자에게 적합하다. 다만, 데이터가 많아질수록 탐색 시간이 오래 걸릴 수 있어 효율적인 대안이 필요한 경우도 있다.1. 개념 및 정의선형 탐색은 다음과 같은 방식으로 동작한다:배열이나 리스트의 첫 번째 요소부터 마지막까지 반복하며 탐색 대상과 비교찾는 값이 일치하면 해당 인덱스를 반환끝까지 탐색했는데 없으면 -1 또는 None 반환2. 동작 원리 단계 설명 1i = 0부터 시작하여 arr[i]와 target 비교2일치하면 i 반환, 아니면 다음 인덱스로 이동3모든 요소를 확인할 때까지 반복4없다면 실패..

개요DFS(Depth-First Search)는 트리(Tree)나 그래프(Graph) 구조에서 한 방향으로 깊이 탐색을 진행한 뒤, 더 이상 갈 수 없을 때 되돌아오는(Backtracking) 방식의 탐색 알고리즘이다. 재귀 또는 스택 기반으로 구현되며, 경로 탐색, 조합 생성, 백트래킹, 연결 요소 탐색 등에 널리 사용된다. 본 글에서는 DFS의 개념, 구현 방식, 시간 복잡도, BFS와의 차이, 실전 활용 사례 등을 다룬다.1. 개념 및 정의DFS는 시작 노드에서 한 방향으로 가능한 깊이까지 탐색하고, 막히면 이전 지점으로 되돌아가 다시 탐색을 이어가는 방식의 탐색 알고리즘이다. 트리 순회(preorder, postorder)나 그래프의 미방문 노드 전체 탐색 등에 사용된다.2. DFS 탐색 방식 단..

개요BFS(Breadth-First Search)는 그래프나 트리의 탐색 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 탐색해 나가는 너비 우선 방식이다. 큐(Queue)를 기반으로 하며, 최단 거리 탐색과 레벨 기반 처리가 가능해 다양한 문제 해결에 널리 사용된다. 본 글에서는 BFS의 개념, 동작 원리, 시간 복잡도, 구현 방법, 활용 사례 등을 체계적으로 정리한다.1. 개념 및 정의BFS는 탐색 시작 노드에서 인접한 노드들을 먼저 방문한 뒤, 그다음 레벨의 노드들을 방문하는 방식으로 그래프를 탐색하는 알고리즘이다. FIFO 구조의 큐를 사용하며, 방문 순서가 레벨 순으로 진행된다. 무가중치 그래프에서 최단 경로를 찾는 데 가장 적합한 알고리즘이다.2. BFS 알고리즘 동작 방식 단계 ..

개요탐색 알고리즘은 데이터 집합 내에서 특정 값을 찾기 위해 사용되는 알고리즘이다. 효율적인 탐색은 데이터 처리 성능에 직결되며, 자료구조와 문제 특성에 따라 다양한 탐색 방식이 활용된다. 선형 탐색처럼 단순한 방식부터 이진 탐색, 해시 탐색, 그래프 기반 탐색(DFS, BFS), 트리 탐색까지 광범위하게 존재한다. 본 글에서는 탐색 알고리즘의 개념, 종류, 시간 복잡도, 활용 사례를 중심으로 체계적으로 설명한다.1. 개념 및 정의탐색 알고리즘은 주어진 데이터 구조에서 특정 키나 값을 찾는 절차이다. 자료의 정렬 여부, 크기, 구조에 따라 탐색 방식의 효율이 달라지며, 경우에 따라 최적화된 알고리즘 선택이 중요하다.2. 탐색 알고리즘의 분류 분류 설명 적용 자료구조 선형 탐색데이터를 처음부터 끝까지 ..