완전 이진 트리의 배열 표현과 힙 불변식, 삽입·삭제·heapify의 원리를 설명하고 동률·갱신·취소·상위 k개·다중 병합·최단 거리 예제를 검증한다. 이진 힙(binary heap)은 완전 이진 트리의 모양과 부모·자식 간 우선순위 규칙을 함께 유지하는 자료구조다. 최소 힙에서는 부모가 자식보다 크지 않고, 최대 힙에서는 부모가 자식보다 작지 않다. 이 국소 규칙 덕분에 루트에서 전체의 최솟값 또는 최댓값을 얻을 수 있다.
배열의 인덱스·메모리 배치·길이와 용량을 설명하고 삽입·삭제, 복사와 뷰, 다차원 인덱싱, 누적 합·차분·압축을 실행 예제와 경계 검사로 살펴본다. 배열(array)은 여러 원소를 인덱스로 구분하여 다루는 자료구조다. 기본적인 연속 배열 모델에서는 같은 크기의 슬롯이 차례로 놓이며 시작 위치와 인덱스로 각 슬롯의 위치를 계산할 수 있다. 연결 리스트처럼 앞 원소의 링크를 따라가야만 다음 위치를 알 수 있는 구조와 차이가 있다.
연결 리스트의 노드·링크·소유권을 설명하고 단일·이중 연결 구현, 역순 변환, 순환 검출, 정렬 병합과 LRU 캐시를 예제 및 기준 모델 대조로 살펴본다. 연결 리스트(linked list)는 값과 다음 노드의 위치를 묶은 노드들을 연결하여 순서를 표현하는 자료구조다. 배열에서는 시작 주소와 원소 크기로 i번째 위치를 계산하지만, 연결 리스트에서는 앞 노드가 다음 노드를 가리킨다. 논리적으로 이웃인 원소가 메모리에서도 이웃일
덱은 앞과 뒤에서 원소를 넣고 꺼내는 양방향 큐다. 원형 배열 구현, 언어별 계약, 제한 용량과 회전, 단조 덱의 윈도 최댓값과 0-1 BFS를 실제 예제와 기준 구현 대조로 설명한다. 덱(deque)은 double-ended queue의 줄임말로, 앞과 뒤에서 원소를 넣고 꺼낼 수 있는 양방향 큐다. 보통 앞 삽입·뒤 삽입·앞 제거·뒤 제거의 네 연산을 제공한다. 한쪽에서 넣고 반대쪽에서 빼면 FIFO 큐,같은 쪽에서 넣고
큐는 먼저 넣은 항목부터 꺼내는 FIFO 자료형이다. 원형 버퍼 구현과 BFS, 작업 큐의 역압·완료·종료·동시성 정책을 실행 예제와 4,000단계 모델 검사, 16,384개 최단 거리 대조로 설명한다. 큐(queue)는 원소를 뒤에 넣고 앞에서 꺼내는 선입선출, 즉 FIFO 순서를 가진 추상 자료형이다. enqueue 또는 put은 대기열에 넣고, dequeue 또는 get은 가장 먼저 들어온 원소를 제거하며 반환한다. 맨
스택은 마지막에 넣은 값을 먼저 꺼내는 LIFO 자료형이다. 기본 구현과 경계 오류에서 출발해 괄호 검사, 수식 변환·평가, DFS 프레임, 실행 취소, 최솟값·단조 스택을 예제와 완전 열거 검사로 설명한다. 스택(stack)은 마지막에 넣은 원소를 먼저 꺼내는 후입선출, 즉 LIFO 규칙을 가진 추상 자료형이다. 원소를 넣는 push, 맨 위 원소를 제거하며 반환하는 pop, 제거하지 않고 보는 peek 또는 top이 핵심
동적 배열은 길이와 내부 용량을 구분하고 필요할 때 저장소를 확장하는 자료구조다. 두 배 확장 구현, 복사 횟수 분석, 삽입·삭제와 축소 진동, 참조 수명, 예약·메모리·동시성의 한계를 실행 예제와 모델 기반 검사로 설명한다. 동적 배열(dynamic array)은 원소를 순서대로 담는 내부 배열을 사용하면서 필요한 경우 더 큰 저장 공간으로 옮겨 길이를 늘리는 자료구조다. 배열 인덱스로 원소를 읽는 장점과 실행 중 원소를 추
자료 구조는 데이터를 저장하고 찾기·추가·삭제·순회 같은 연산을 지원하는 방식이다. 이 문서는 배열·연결 리스트·스택·큐·해시·트리·힙을 실제 예제로 비교하고, 참조 공유와 동점 처리, LRU 캐시 구현과 검증까지 설명한다. 자료 구조는 데이터를 조직해 저장하고 필요한 연산을 지원하는 방식이다. 원소를 어디에 두는가뿐 아니라 찾기·추가·삭제·순회가 어떻게 동작하며 무엇을 보장하는지가 중요하다. 같은 값 목록도 배열, 연결 리스
힙은 부모와 자식 사이의 우선순위 조건을 유지하는 트리 기반 자료구조이다. 최소 힙은 부모 키가 자식 키보다 크지 않도록 유지한다. 최솟값은 루트에서 찾지만 다른 모든 원소가 정렬된 상태는 아니다. 우선순위 큐의 구현에 사용하며, 메모리 할당 영역을 뜻하는 힙과는 다른 개념이다. 대기 작업의 실행 시각을 키로 쓰면 가장 이른 작업을 루트에서 꺼낼 수 있다. 새 작업을 넣은 뒤 부모와 비교하며 위치를 조정한다. 아무 값이나 검색
이진 탐색 트리는 키의 대소관계에 따라 왼쪽과 오른쪽 부분 트리를 나누어 저장하는 이진 트리이다. 찾는 키를 현재 노드와 비교하고 한쪽 부분 트리로 내려간다. 탐색·삽입·삭제의 비용은 높이 h에 비례하는 O(h)이며, 균형을 유지할 때 O(log n)을 기대할 수 있다. 10, 5, 15를 넣으면 10의 왼쪽에서 5, 오른쪽에서 15를 찾는다. 중위 순회는 키의 정렬 순서를 얻는 데 사용할 수 있다. 정렬된 입력을 단순 삽입하
이진 트리는 각 노드가 최대 두 개의 자식 위치를 가지는 트리 자료구조이다. 일반적으로 왼쪽과 오른쪽 자식을 구별한다. 루트에서 노드까지의 경로 길이를 깊이라 하고, 노드에서 가장 먼 잎까지의 경로 길이를 높이라고 한다. 값의 정렬 조건은 이진 트리의 정의에 포함되지 않는다. 산술식 (a+b)×c를 표현할 때 곱셈을 루트에, 덧셈과 c를 자식에 놓을 수 있다. 트리 순회 순서에 따라 다른 표현을 만들 수 있다. 이진 트리가 곧
