ITPE * JackerLab

개요이진 탐색 트리(BST, Binary Search Tree)는 이진 트리의 일종으로, 왼쪽 서브트리에는 루트보다 작은 값이, 오른쪽 서브트리에는 루트보다 큰 값이 저장되는 자료구조이다. 중복 없는 정렬된 데이터를 저장하면서 빠르게 탐색, 삽입, 삭제가 가능하며, 평균적으로 O(log n)의 성능을 보인다. 알고리즘 문제풀이와 데이터베이스, 메모리 관리 등 다양한 분야에 활용된다.1. BST의 구조와 특징 구성 요소 설명 루트(Root)트리의 최상위 노드노드(Node)데이터와 자식 포인터를 포함한 단위왼쪽 자식루트보다 작은 값오른쪽 자식루트보다 큰 값BST는 모든 노드에 대해 왼쪽 이 성립한다.2. BST의 연산 동작 원리연산동작 방식시간 복잡도 (평균/최악)탐색(Search)루트부터 값 비교, 작으..

개요이진 트리(Binary Tree)는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 계층적 구조이다. 트리의 기본이자 다양한 트리 기반 알고리즘의 뼈대 역할을 하며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie), 표현식 트리 등으로 확장된다. 노드의 위치와 순서가 중요한 구조로, 다양한 순회 알고리즘이 적용된다.1. 이진 트리의 구조와 용어 용어 설명 노드(Node)데이터를 저장하는 기본 단위루트(Root)트리의 시작 노드 (부모 없음)왼쪽 자식(Left Child)루트 기준 왼쪽 하위 노드오른쪽 자식(Right Child)루트 기준 오른쪽 하위 노드리프(Leaf)자식이 없는 노드서브트리(Subtree)특정 노드를 루트로..

개요트리(Tree)는 노드(Node)와 간선(Edge)로 구성된 계층적 비선형 자료구조로, 하나의 루트 노드(Root)에서 시작하여 자식 노드로 분기되는 구조를 가진다. 트리는 컴퓨터 과학에서 데이터 분류, 탐색, 계층 구조 표현 등 매우 널리 사용되며, 이진 트리, 이진 탐색 트리, 힙, 트라이, AVL 트리, B트리 등 다양한 종류가 있다.1. 트리의 개념과 구성 요소 구성 요소 설명 노드(Node)데이터를 담는 기본 단위루트(Root)트리의 시작 노드 (부모가 없음)부모(Parent), 자식(Child)노드 간 관계 정의리프(Leaf)자식이 없는 마지막 노드서브트리(Subtree)특정 노드를 루트로 하는 부분 트리간선(Edge)노드 간 연결 관계2. 트리의 특성특성설명비선형 구조노드 간 관계가 계..

개요덱(Deque, Double-Ended Queue)은 양쪽 끝(front, rear) 모두에서 삽입과 삭제가 가능한 선형 자료구조이다. 일반 큐는 FIFO, 스택은 LIFO 원칙만 따르지만, 덱은 스택과 큐의 기능을 모두 갖춘 유연한 자료구조로, 양방향에서 데이터를 처리할 수 있다. 파이썬에서는 collections.deque 모듈을 통해 효율적인 덱을 구현할 수 있다.1. 개념 및 정의 구성 요소 설명 front덱의 앞쪽 끝, 요소 삽입/삭제 가능rear덱의 뒤쪽 끝, 요소 삽입/삭제 가능연산append, appendleft, pop, popleft, peek덱은 입력 제한 덱(Input-Restricted Deque), 출력 제한 덱(Output-Restricted Deque) 등으로 확장 가능..

개요큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 선입선출(First-In, First-Out, FIFO) 구조를 가지는 선형 자료구조이다. 데이터는 **뒤(Rear)**에서 삽입되고, **앞(Front)**에서 삭제되며, 일상적인 줄서기, 프로세스 스케줄링, 버퍼 처리 등에 널리 사용된다. 파이썬에서는 collections.deque, 리스트, 큐 모듈 등을 통해 구현할 수 있다.1. 개념 및 정의 항목 설명 구조선형적, 한쪽에서는 삽입, 반대쪽에서는 삭제 수행주요 연산enqueue(삽입), dequeue(삭제), peek(앞 요소 확인), isEmpty원리FIFO (First-In, First-Out)2. 큐 연산 동작 예시초기: []enqueue(10) → [10]enqueue(20) → [..

개요스택(Stack)은 데이터가 일렬로 쌓이고, 가장 마지막에 삽입된 요소가 가장 먼저 제거되는 후입선출(Last-In, First-Out, LIFO) 원칙을 따르는 선형 자료구조이다. 삽입은 push, 삭제는 pop, 현재 요소 확인은 peek 또는 top 연산으로 수행되며, 재귀, 수식 계산, 괄호 검사, 웹 브라우저의 방문 기록 등 다양한 분야에서 널리 활용된다.1. 개념 및 정의 항목 설명 구조선형적, 한쪽 끝에서만 삽입 및 삭제 가능주요 연산push(삽입), pop(삭제), peek/top(최상단 확인), isEmpty대표 원리LIFO (Last-In, First-Out)2. 스택 연산 동작 예시초기: []push(10) → [10]push(20) → [10, 20]pop() → [10] (2..

개요연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 함께 저장하여 데이터를 선형으로 연결한 자료구조이다. 배열과 달리 메모리 상에서 연속적이지 않아도 되며, 삽입/삭제 연산이 유연하다는 장점이 있다. 리스트의 형태에 따라 단일(Singly), 이중(Doubly), 원형(Circular) 등으로 구분되며, 알고리즘과 시스템 구현에서 핵심적으로 활용된다.1. 개념 및 정의 구성 요소 설명 Node데이터(data) + 포인터(next)로 구성된 기본 단위Head연결 리스트의 시작 노드를 가리키는 포인터Tail마지막 노드를 의미하며, next는 None 또는 Head를 가리킴노드는 동적으로 생성되며, 메모리를 필요할 때마다 할당한다.2. 배열과의 차이점 비교항목배열(Ar..

개요배열(Array)은 같은 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조로, 프로그래밍에서 가장 기본적이면서도 핵심적인 구조 중 하나다. 인덱스를 기반으로 요소에 빠르게 접근할 수 있으며, 리스트, 행렬, 문자열 등 다양한 형태로 확장되어 활용된다. 정렬, 탐색, 해싱, 동적 프로그래밍 등 거의 모든 알고리즘에서 필수적으로 사용된다.1. 개념 및 정의 항목 설명 정의같은 데이터 타입을 가지는 원소들이 메모리상에 연속적으로 배치된 구조인덱스0부터 시작하는 정수로, 각 원소에 접근하는 주소 역할특징빠른 접근 속도 (인덱스 기반), 고정된 크기 (정적 배열 기준)2. 배열의 특징항목설명시간 복잡도 (접근)O(1) (arr[i]로 바로 접근 가능)시간 복잡도 (삽입/삭제)O(n) (중간에 삽입/삭제..

개요동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 중복된 하위 문제로 나누고, 이들을 한 번만 계산하여 결과를 저장해 재사용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 전략이다. 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack), 경로 탐색 등 다양한 최적화 문제에 활용되며, **탑다운(메모이제이션)**과 바텀업(테이블화) 방식이 있다.1. 핵심 개념 및 정의동적 계획법의 핵심은 다음 두 가지 조건을 만족하는 문제에서 적용 가능하다:중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 반복적으로 등장함최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 하위 문제의 최적해로 구..

개요백트래킹(Backtracking)은 가능한 모든 경우의 수를 탐색하되, 불가능하거나 의미 없는 경로는 조기에 차단(pruning)하는 완전 탐색 기법이다. DFS(깊이 우선 탐색)를 기반으로 하며, 부분 해(partial solution)를 점진적으로 구성해가다가 해답이 아니라고 판단되면 직전 상태로 되돌아가 다른 경로를 탐색한다. 퍼즐, 조합, 순열, 경로 탐색 등 다양한 문제에 사용된다.1. 개념 및 정의완전 탐색(Brute Force): 가능한 모든 경우를 시도백트래킹: 모든 경우를 시도하되, 유망하지 않은 경로는 가지치기(prune)재귀 호출 + 조건 기반 되돌아가기 형태로 구현됨2. 동작 구조 단계 설명 1현재 노드(상태)가 해답인지 확인2해답이면 출력 또는 저장3아니라면 다음 가능한 선택..

개요그리디(Greedy) 알고리즘은 문제 해결 과정에서 매 순간 가장 좋아 보이는 선택(최적의 선택)을 하는 전략이다. 각 단계의 선택이 이후의 선택에 영향을 주지 않는 문제, 즉 **탐욕적 선택 속성(Greedy Choice Property)**과 **최적 부분 구조(Optimal Substructure)**를 만족하는 문제에 효과적이다. 빠르고 구현이 간단하며, 다양한 최적화 문제에서 널리 활용된다.1. 개념 및 정의그리디 알고리즘의 핵심은 다음과 같다:현재 단계에서 가장 이득이 크거나 비용이 적은 선택을 한다.과거의 선택과 무관하게 현재 선택이 전체 최적해에 포함된다고 가정한다.전체 문제를 한 번의 탐색으로 해결할 수 있다.단점은 항상 최적의 해를 보장하지 않는다는 것이다.2. 알고리즘 동작 구조 ..

개요분할 정복(Divide and Conquer)은 큰 문제를 작고 동일한 구조의 하위 문제로 나눈 뒤, 이를 각각 해결하고 결합하여 전체 문제를 해결하는 알고리즘 전략이다. 컴퓨터 과학에서 가장 널리 사용되는 알고리즘 설계 패러다임 중 하나로, 정렬, 탐색, 수학 계산, 동적 프로그래밍 등 다양한 분야에 활용된다. 병렬 처리와 최적화 문제에도 효과적이다.1. 개념 및 정의분할 정복은 다음과 같은 3단계로 구성된다:Divide (분할): 문제를 동일한 구조의 더 작은 하위 문제로 나눈다.Conquer (정복): 각 하위 문제를 재귀적으로 해결한다.Combine (결합): 하위 문제의 해를 결합하여 원래 문제의 해를 도출한다.2. 대표 알고리즘 예시 알고리즘 설명 시간 복잡도 병합 정렬 (Merge S..

개요트리 탐색(Tree Traversal)은 트리 구조를 가진 자료구조의 노드를 특정 순서에 따라 방문하는 알고리즘이다. 이진 트리(Binary Tree), 이진 탐색 트리(BST), 힙(Heap) 등 다양한 트리 구조에서 데이터를 순차적으로 접근하거나 연산을 수행할 때 사용된다. DFS 기반의 전위/중위/후위 순회와 BFS 기반의 레벨 순회로 나뉘며, 문제에 따라 적절한 탐색 방법을 선택해야 한다.1. 개념 및 정의트리 탐색은 다음과 같은 두 가지 유형으로 나뉜다:DFS(Depth-First Search): 깊이 우선 순회 (전위, 중위, 후위 순회)BFS(Breadth-First Search): 너비 우선 순회 (레벨 순회)2. DFS 기반 트리 순회 순회 방식 방문 순서 주요 특징 전위 순회 (..

개요해시 탐색(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없다면 실패..

개요기수 정렬(Radix Sort)은 정수형 데이터를 자릿수별로 분류하여 정렬하는 방식의 비교 기반이 아닌(non-comparative) 정렬 알고리즘이다. LSD(Least Significant Digit) 방식에서는 가장 낮은 자리부터 정렬하고, MSD(Most Significant Digit)는 가장 높은 자리부터 정렬한다. **시간 복잡도는 O(nk)**로 매우 효율적이며, 계수 정렬 또는 안정 정렬을 내부적으로 활용한다.1. 개념 및 정의기수 정렬은 숫자의 각 자릿수를 기준으로 여러 번의 정렬을 반복하여 전체 배열을 정렬하는 알고리즘이다. 각 자릿수마다 안정 정렬을 수행해야 정확한 결과를 보장할 수 있다.예를 들어 [170, 45, 75, 90, 802, 24, 2, 66]를 정렬할 경우:1의 ..

개요계수 정렬(Counting Sort)은 정수 데이터가 주어진 범위 내에 존재할 때, 매우 빠르게 정렬할 수 있는 비교 기반이 아닌 정렬 알고리즘이다. 데이터의 빈도수를 카운트 배열에 저장하고, 이를 기반으로 정렬된 결과를 생성하는 방식으로, 평균 시간 복잡도 **O(n + k)**의 매우 빠른 성능을 제공한다. 단, 정수 범위가 제한적일 때만 효율적이다.1. 개념 및 정의계수 정렬은 다음 절차로 이루어진다:입력 배열에서 최댓값(K)을 기준으로 길이 K+1짜리 카운트 배열 생성각 원소의 빈도수를 카운트 배열에 저장카운트 배열을 누적합으로 변경 (누적합 정렬 시 사용)누적합을 기반으로 정렬된 결과 배열에 삽입음수 데이터에는 직접 사용할 수 없고, 변환이 필요하다.2. 동작 원리 단계 설명 1입력 배열에..

개요힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 하는 비교 기반 정렬 알고리즘이다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 이용해 최댓값(또는 최솟값)을 반복적으로 추출하고, 이를 배열의 끝에 삽입하는 방식으로 동작한다. **시간 복잡도가 항상 O(n log n)**으로 일정하며, **제자리 정렬(in-place)**이 가능하다는 장점이 있다.1. 개념 및 정의힙 정렬은 다음 두 단계로 이루어진다:배열을 힙 구조(완전 이진 트리)로 구성 (heapify)루트 노드(최댓값 또는 최솟값)를 추출한 뒤, 남은 요소로 힙 재구성 → 정렬 반복일반적으로 최대 힙을 사용해 오름차순 정렬을 수행한다.2. 동작 원리 단계 설명 1단계입력 배열을 최대 힙 구조로 변환2단계힙의 ..

개요퀵 정렬(Quick Sort)은 평균적으로 매우 빠른 성능을 자랑하는 비교 기반 정렬 알고리즘으로, 분할 정복(Divide and Conquer) 전략을 사용한다. 주어진 배열에서 기준이 되는 **피벗(Pivot)**을 기준으로 좌우로 나누고, 이를 재귀적으로 정렬해 전체 배열을 정렬하는 방식이다. 내부 정렬 중 가장 널리 사용되며, 실무에서도 많이 활용되는 알고리즘이다.1. 개념 및 정의퀵 정렬은 다음과 같은 방식으로 작동한다:피벗(pivot)을 하나 선택한다피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할각 파티션(partition)에 대해 재귀적으로 퀵 정렬 수행병합은 따로 필요 없음 (자리 교환으로 해결)2. 동작 원리 단계 설명 1피벗을 선택한다 (보통 처음, 마지막, 중간 또는 랜덤)2..

개요병합 정렬(Merge Sort)은 데이터를 반으로 나누고 각각을 정렬한 뒤 다시 병합하는 분할 정복(Divide and Conquer) 전략을 사용하는 효율적인 정렬 알고리즘이다. 안정 정렬이며, 항상 **O(n log n)**의 시간 복잡도를 유지해 정렬 알고리즘 중에서도 높은 성능과 예측 가능성을 보인다. 내부 정렬과 외부 정렬(External Sort) 모두에 활용되며, 대용량 데이터 정렬에도 적합하다.1. 개념 및 정의병합 정렬은 다음 과정을 반복하여 배열을 정렬한다:배열을 반으로 나눈다 (재귀적으로)각각을 병합 정렬로 정렬한다정렬된 두 부분 배열을 하나로 병합한다병합 시에는 두 정렬된 배열을 비교하여 하나의 정렬된 배열로 합친다.2. 동작 원리단계설명1배열을 재귀적으로 반씩 나눔2분할된 배열..

개요삽입 정렬(Insertion Sort)은 정렬되지 않은 데이터를 하나씩 꺼내어 정렬된 부분에 삽입해가는 방식으로 작동하는 비교 기반 정렬 알고리즘이다. 카드 정렬 방식과 유사하며, 구현이 간단하고 작은 데이터 집합에서 매우 효과적이다. 또한 대부분의 경우에 안정 정렬로 분류되며, 부분 정렬이 되어 있는 경우 효율적이다.1. 개념 및 정의삽입 정렬은 다음과 같이 동작한다:두 번째 원소부터 시작해 이전 원소들과 비교정렬된 부분 중 적절한 위치를 찾아 값을 삽입이 과정을 배열 끝까지 반복이미 정렬된 데이터에는 최소 연산만 수행되어 최적의 성능을 발휘한다.2. 동작 원리 단계 설명 1단계두 번째 원소부터 시작하여 이전 원소들과 비교2단계더 큰 값을 뒤로 이동시키며 빈 자리를 만들고 삽입3단계삽입 후 정렬된..

개요선택 정렬(Selection Sort)은 정렬되지 않은 부분에서 가장 작은(또는 큰) 값을 선택해 맨 앞의 값과 교환하는 방식으로 정렬을 수행하는 알고리즘이다. 반복적으로 최솟값을 선택하고 정렬된 영역 뒤에 배치하면서 전체 배열을 정렬해나간다. 구현이 간단해 정렬 알고리즘 입문용으로 적합하며, 메모리 사용이 적은 것이 특징이다.1. 개념 및 정의선택 정렬은 다음과 같은 방식으로 동작한다:전체 배열에서 가장 작은 값을 찾아 첫 번째 위치와 교환두 번째부터 끝까지 반복하여 두 번째로 작은 값을 두 번째 위치로 이동이런 식으로 n-1번 반복해 정렬 완료2. 동작 원리 단계 설명 1단계i번째 인덱스를 기준으로 최솟값을 찾음2단계최솟값과 i번째 값을 교환(swap)3단계i를 1 증가시키고 배열 끝까지 반복배..