홈 > 강의소개
자료구조 통합과정
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 12개 챕터, 82강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 자료구조와 알고리즘 | ||
|
[1강] 자료구조와 알고리즘
|
0:
58:
09
|
|
|
자료구조와 알고리즘 기초 개념 및 알고리즘 표현 방식 정리
• 자료구조 기본 개념: 리스트·스택(LIFO)·큐(FIFO)·트리·그래프·탐색 구조 정의와 C 언어 배열을 통한 자료 저장 구조 이해 • 프로그램 구성 원리: 전역/지역 변수, 상수 정의, 배열, 함수 반환형과 매개변수, call by value·call by reference(포인터 활용), 스택 기반 함수 호출 구조 • 알고리즘 형식 체계: 알고리즘 정의와 5가지 조건(입력·출력·명확성·유한성·유효성) 및 자연어·흐름도·유사코드·프로그래밍 언어 표현 방식 특징 정리 |
||
|
[2강] 추상데이터 타입. 알고리즘의 성능 분석. 자료구조 표기법
|
1:
08:
37
|
|
|
추상 데이터 타입과 알고리즘 성능 분석 및 자료구조 표기법 핵심 정리
• 추상 데이터 타입(ADT) 개념: 객체와 연산 명세를 구현과 분리하여 정의하고, 자료구조(구조체·typedef)와 연산 함수(push, pop, 탐색 등)를 독립적으로 설계하는 데이터 추상화 원리 • 알고리즘 성능 분석: 성능 측정 vs 성능 분석 구분, 입력 크기 기준 시간·공간 복잡도 정의, Big-O·Big-Ω·Big-Θ 표기와 지배항 개념, 순차 탐색 알고리즘의 최선·최악·평균 시간 복잡도 도출 • C 자료구조 표기 관례: 상수·변수·함수 네이밍 규칙, typedef로 논리적 타입 정의, 구조체 기반 리스트·스택(StackType)의 데이터 구성과 포인터를 활용한 연산 함수 구현 방식 정리 |
||
| 2장. 순환 | ||
|
[3강] 순환의 소개. 거듭제곱 값 계산
|
1:
01:
55
|
|
|
순환 알고리즘과 거듭제곱 계산 알고리즘 핵심 정리
• 순환(recursion)과 재귀 관계: 자기 호출 구조와 초기/종료 조건을 기반으로 선행항으로 현재항을 정의하는 재귀 관계 개념 및 스택 기반 호출·복귀 메커니즘 정리 • 순환 vs 반복 알고리즘: 팩토리얼 예제를 통해 두 방식의 시간 복잡도 O(n) 동일성, 스택 오버헤드에 따른 실제 성능·메모리 차이, 표현 간결성과 실행 효율성 트레이드오프 비교 • 거듭제곱 계산 알고리즘: 단순 반복 i_power의 O(n) 구조와 대비되는 지수 이진 분할 기반 r_power·i2_power 알고리즘의 O(log n) 시간 복잡도, 이진 표현 활용 절차 및 연산 최적화 원리 정리 |
||
|
[4강] 피보나치 수열의 계산. 하노이탑 문제
|
0:
49:
52
|
|
|
피보나치 수열과 하노이 탑: 순환 vs 반복 알고리즘 시간복잡도 비교
• 피보나치 수열 알고리즘: 점화식 f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)에 기반한 순환 알고리즘의 중복 호출로 인한 지수 시간복잡도 O(2^n)와 반복 알고리즘의 선형 시간복잡도 O(n) 비교 • 순환 알고리즘과 Divide & Conquer: 점화식을 그대로 구현하는 순환 구조와 연산 횟수를 감소시키는 Divide & Conquer 기법(분할·정복·합병)의 개념, 피보나치 순환의 비효율성과 빠른 거듭제곱·이진 탐색·정렬 알고리즘 등의 대조 • 하노이 탑 문제: n개 원반 이동 최소 횟수 점화식 H_n=2H_{n-1}+1, 해 H_n=2^n-1 도출과 이에 따른 순환 알고리즘 구조(ht(n-1, from→temp, temp→to) 패턴) 및 고정적인 지수 시간복잡도 O(2^n)의 특성 정리 |
||
| 3장. 배열, 구조체, 포인터 | ||
|
[5강] 배열
|
0:
37:
01
|
|
|
배열과 2차원 배열, 함수 매개변수 배열의 메모리 구조 핵심 정리
• ADT Array와 배열 개념: 동질적 요소 집합을 <인덱스, 요소> 쌍과 create·retrieve·store 연산으로 정의하는 추상 자료형 구조 • 배열 메모리와 주소 계산: 1차원·2차원 배열의 연속 메모리 배치에서 base + 인덱스(또는 i×n+j) × sizeof(요소)로 물리 주소를 계산하는 규칙 • 배열 이름과 포인터·함수 전달: 배열 이름을 첫 요소 주소를 나타내는 상수 포인터로 해석하고, 함수 인자에서 주소 복사에 의해 배열 요소 변경이 호출자에게 반영되는 메커니즘 |
||
|
[6강] 배열의 응용: 다항식
|
1:
06:
00
|
|
|
다항식의 배열 표현과 덧셈 알고리즘 정리
• 다항식 배열 표현 방식: dense 구조(poly)의 최대차수·계수 배열 기반 표현과 sparse 구조(term)의 (계수, 차수) 쌍·구간 인덱스 기반 표현 및 메모리 효율 비교 • 덧셈 알고리즘 설계: poly_add1의 최대차수 기준 인덱스·차수 동기화 순회와 poly_add2의 term 전역배열·comp 비교·att 삽입을 이용한 sparse 덧셈 절차 정리 • 전역 배열·예외 처리: term·avail 전역 관리, 시작·끝 인덱스(sA,eA,sB,eB,sC,eC) 기반 다항식 구간 표현, 경계 검사와 side effect·포인터 인자 처리 원리 설명 |
||
|
[7강] 배열의 응용: 희소 행렬. 구조체
|
1:
00:
54
|
|
|
배열의 응용: 희소 행렬과 구조체 기본 개념 정리
• 희소 행렬 및 인덱스 넘버: 0이 아닌 원소만 (행, 열, 값) 구조로 저장하고 index_number=row×열수+col 공식을 이용해 2차원 위치를 1차원 인덱스로 변환·비교하는 메모리·연산 최적화 개념 정리 • 희소 행렬 연산 구조(SM 방식): element, SM 구조체로 희소 행렬을 표현하고 ts(0이 아닌 항 개수) 기반 병합 알고리즘(sm_add2)으로 덧셈을 수행하는 절차와 자료구조 설계 원리 정리 • 구조체 문법 및 활용: struct/typedef 기반 사용자 정의 타입, 구조체 대입과 필드 비교 규칙, 자기 참조 구조체를 통한 연결 구조, 구조체 배열·중첩 구조체를 이용한 복합 데이터 모델링 방식 정리 |
||
|
[8강] 포인터. 동적 메모리 할당
|
1:
00:
22
|
|
|
포인터와 동적 메모리 할당 핵심 개념 정리 (C 언어)
• 포인터와 포인터 유형: 주소를 저장하는 포인터의 개념과 &·* 연산자, 배열 이름과의 관계, 구조체 포인터와 → 연산자, 포인터의 포인터와 함수 포인터 선언 및 호출 방식 정리 • 포인터 활용과 주의점: 함수 매개변수로서의 포인터를 통한 call by value 보완(swap 등), 포인터 연산(증가·감소, 간접참조) 의미 구분, NULL 초기화·명시적 캐스팅 등 안전한 포인터 사용 규칙 정리 • 메모리 할당 방식: 정적 메모리 할당의 특성과 한계, 동적 메모리 할당의 개념과 malloc·free·calloc 사용 절차, sizeof 연산자를 이용한 이식성 있는 메모리 크기 계산 방법 정리 |
||
| 4장. 리스트 | ||
|
[9강] 리스트 추상 데이터 타입. 배열로 구현된 리스트
|
1:
06:
11
|
|
|
배열로 구현한 리스트 ADT와 C 구조체·포인터 핵심 정리
• 리스트 추상 데이터 타입과 배열 기반 구현: 순서가 있는 요소 집합으로서 리스트 ADT 연산(add, delete, get, length, is_empty, is_full, display)을 정의하고, 이를 `element list[]`와 `int length` 필드를 가진 ArrayList 구조체로 구현하며 인덱스와 길이, 공백/포화 및 경계 조건을 관리하는 구조 • 배열 리스트 연산 절차: add(pos)에서 뒤에서 앞으로 한 칸씩 이동 후 삽입하고 delete(pos)에서 앞에서 뒤 값을 한 칸씩 당겨 삭제하며, 항상 `0 ≤ pos ≤ length`, `length ≤ MAX_LIST_SIZE` 조건을 검증하고 display는 `0`부터 `length-1`까지 순차 접근해 실제 저장된 요소만 출력하는 절차 • 구조체·포인터와 메모리 관리: C의 값 전달과 주소(포인터) 전달 차이를 기반으로 `ArrayList *L` 형태 구조체 포인터 인자로 원본을 조작하고, `.`와 `->` 연산자 차이를 구분하며, 정적 배열과 `malloc/free`를 이용한 동적 할당에서 리스트 논리 구조는 동일하되 메모리 확보 시점·수명·메모리 누수 관리가 핵심인 개념 |
||
|
[10강] 연결 리스트 (1)
|
0:
38:
16
|
|
|
연결 리스트와 단순 연결 리스트 삽입 함수 핵심 정리
• 연결 리스트 자료 구조: 배열과 대비되는 물리적 자료 구조로, 동적할당 기반 노드(데이터+링크) 연결을 통해 메모리 효율·삽입·삭제 성능을 확보하며 포인터 오버헤드와 선형 탐색 비용을 가짐 • 연결 리스트 유형과 구조: 단순·원형·이중 연결 리스트로 구분되며, 헤드 포인터/헤드 노드 사용 방식, 단방향·양방향 링크, 마지막 노드 링크(NULL·첫 노드) 차이를 통해 탐색·삽입·삭제 동작 특성이 결정됨 • 단순 연결 리스트 구현과 삽입 알고리즘: C 구조체(ListNode)와 malloc 기반 create_node로 노드를 생성하고, insert_node(ListNode **phead, ListNode *p, ListNode *node)에서 공백 리스트·첫 노드 앞·중간 삽입 3가지 경우를 헤드 포인터의 포인터와 링크 갱신 순서(node->link, p->link)로 제어함 |
||
|
[11강] 연결 리스트 (2)
|
0:
40:
27
|
|
|
단순 연결 리스트 삭제·방문·탐색·연결·역순 및 main 적용 정리
• 단순 연결 리스트 기본 연산: 노드 삭제(remove_node), 반복·재귀 방문(i_traverse, r_traverse), 선형 탐색(search)을 통해 헤드 포인터·선행/현재 노드 포인터 활용과 공백 리스트·NULL 처리 원리 정리 • 리스트 구조 변환 연산: 두 리스트 연결(concat)과 역순 변환(reverse)을 통한 링크 재설정 절차, p·q·r 포인터 역할, in-place 링크 방향 변경 및 결과 헤드 포인터 반환 구조 정리 • 동적 메모리 관리: create_node·insert_node·main 예시를 통한 동적 노드 생성·삽입 과정과 연산 후 노드 단위 free를 수행하는 리스트 해제 절차 및 메모리 누수 방지 원리 정리 |
||
|
[12강] 연결 리스트 (3)
|
1:
04:
16
|
|
|
원형·이중 연결 리스트와 다항식 연결 리스트 구현 요약
• 원형·이중 연결 리스트 구조: 원형 연결 리스트와 tail 포인터로 앞·뒤 삽입을 상수 시간에 수행하고, 이중 연결 리스트의 양방향 링크(llink, rlink)와 헤드 노드로 선행·후속 노드 직접 접근 및 포인터 재연결 기반 삽입·삭제 구현 • 다항식 연결 리스트 표현: 계수(co)·차수(ex)를 가진 PolyNode와 길이(len)·head·tail을 가진 PolyHeader로 다항식을 단순 연결 리스트로 표현하고, append 연산으로 후단 노드 추가 및 공백/비공백 리스트 관리 • 다항식 덧셈 알고리즘: 차수 내림차순 정렬된 두 다항식 리스트를 순차 비교(ex 같음/큼/작음)하여 결과 리스트에 병합(append)하는 poly_add 알고리즘으로, 계수 합이 0인 항은 생략하고 O(m+n) 시간에 다항식 합을 구성 |
||
|
[13강] 연결 리스트로 구현된 리스트. 선형 리스트의 응용
|
0:
59:
16
|
|
|
연결리스트 기반 리스트 ADT 구현과 텍스트 에디터 응용 정리
• 리스트 ADT와 자료구조 개념: 배열·연결리스트 등 물리적 구조와 리스트·스택·큐·트리·그래프 등 논리적 구조, 리스트 ADT의 순서·위치·연산 집합 정의 및 단순 연결리스트(헤더 LinkedList, 노드 ListNode, 0-based 인덱스)로의 구현 원리 정리 • 연결리스트 기본 연산과 구현 절차: is_empty·get_length·get_nodeptr 기반 탐색, add·add_first·add_last·delete·get_entry·clear·display·is_in_list 연산의 인덱스 범위 조건, 선행 노드/대상 노드 포인터 사용, 링크 조정과 메모리 할당·해제 원리, ADT 기반 구현과 포인터 직접 조작 방식의 효율성 비교 • 텍스트 에디터 응용 구조: 한 줄을 element(문자 배열)로, 한 줄 노드를 ListNode로, 전체 문서를 LinkedList로 구성하는 라인 리스트 구조와 줄 단위 삽입·삭제·수정 연산을 리스트 ADT 연산(add, delete, get_entry, replace 등)에 매핑하는 설계 원리 정리 |
||
|
[14강] 동치 부류
|
1:
18:
32
|
|
|
동치 관계와 연결리스트를 이용한 동치 부류 알고리즘 요약
• 동치 관계·동치 부류 개념: 반사·대칭·이행 관계로 정의되는 동치 관계와 집합의 분할로서의 동치 부류 구조, 모듈로 3 예(세 동치 부류)로 분할 개념 정리 • 동치쌍 리스트·스택 기반 equ_class 알고리즘: seq 포인터 배열·ListNode 구조·out 방문 배열을 이용해 equ_pairs로 양방향 인접 리스트(동치쌍 리스트)를 만들고, 연결리스트를 재사용한 스택(top)과 DFS 유사 탐색으로 각 동치 부류를 한 번씩만 추출하는 절차 • 시간 복잡도 O(m+n): n개 원소 초기화와 바깥 루프가 O(n), m개 동치쌍(2m개 노드) 처리와 리스트·스택 탐색이 각 노드를 최대 한 번씩만 방문하여 O(m), 전체 동치 부류 계산이 선형 시간에 수행됨 |
||
|
[15강] 희소 행렬
|
1:
14:
43
|
|
|
희소행렬 다중 연결 리스트 구조와 구현 요약
• 희소행렬 노드 및 헤더 구조: tagfield와 union을 사용하는 mNode(head/entry 통합 구조), 행·열 겸용 헤더 노드 배열 H, right/down 포인터를 이용한 원형 다중 연결 리스트 표현 • 희소행렬 입·출력 및 삭제 절차: mread의 헤더 생성과 (row,col,val) 기반 행·열 동시 연결, mwrite의 행 헤더 순회 기반 (row,col,val) 출력, merase의 행별 엔트리 및 잔여 헤더 노드 해제 과정 • 시간복잡도 및 메모리 효율: mread·merase의 O(Rows+Cols+Terms), mwrite의 O(Rows+Terms) 분석과 0이 아닌 항목만 저장하는 방식의 공간 절약 및 연결 구조 설계 원리 |
||
| 5장. 스택 | ||
|
[16강] 스택 (1)
|
1:
06:
28
|
|
|
스택 구현과 응용: 배열·연결리스트, 괄호 검사 정리
• 스택 추상 데이터 타입과 LIFO 구조: top 기반 상태관리, create/is_empty/is_full/push/pop/peek 연산 정의 및 후입선출 동작 원리 정리 • 스택 구현 방식: 배열 기반 스택과 연결 리스트 기반 스택의 자료구조 정의, 초기화·공백/포화 검사, push/pop 절차 및 정적 크기 제약 vs 동적 메모리 활용 비교 • 스택 응용: 함수 호출 스택 프레임(복귀 주소·매개변수·지역변수) 관리와 undo 기능, 괄호 검사 알고리즘(올바른 괄호열 조건·스택 기반 검사 절차) 구조화 정리 |
||
|
[17강] 스택 (2)
|
1:
01:
24
|
|
|
수식 계산과 스택 응용: 후위 표기, 중위 변환, 미로 탐색
• 수식 표기법과 후위 표기식 계산: 중위·전위·후위 표기 개념과 특징, 후위 표기식에서 피연산자 push·연산자 시 op2/op1 pop 후 연산·결과 재 push 구조, 한 번의 순차 스캔으로 연산자 우선순위·괄호 없이 계산하는 스택 기반 알고리즘 정리 • 중위 → 후위 변환 알고리즘: 피연산자 즉시 출력, 연산자·괄호만 스택 저장, 우선순위 함수 pr(op)로 “현재 연산자 ≤ 스택 top 연산자”이면 pop 후 출력, 괄호 쌍 처리와 종료 시 스택 비우기를 통해 연산자 순서를 재배치하는 구조적 변환 절차 정리 • 스택 기반 미로 탐색(DFS): 좌표(r,c)를 원소로 하는 스택 구조와 상·하·좌·우 후보 pushL 조건(인덱스 범위·벽·방문 여부 검사), 방문 위치 마킹과 스택 empty 시 실패·출구 'x' 도달 시 성공으로 정의되는 비재귀 깊이 우선 탐색 알고리즘 정리 |
||
| 6장. 큐 | ||
|
[18강] 큐 (1)
|
1:
01:
30
|
|
|
큐 ADT와 배열·연결리스트 구현 핵심 정리
• 큐 추상 데이터 타입 개념: 선입선출(FIFO) 선형 자료구조로, create·init·is_empty·is_full·enqueue·dequeue·peek 연산과 front·rear 포인터 의미 정의 • 배열 기반 큐 구현: 선형 큐와 원형 큐에서 front/rear 인덱스, 공백·포화 조건, 모듈러 연산을 이용한 원형 큐 구조, 큐 구조체(QueueType)와 is_empty·is_full·enqueue·dequeue 절차 정의 • 연결 리스트 기반 큐 구현: 노드 구조체(QueueNode)와 헤더(LinkedQueue)에서 front·rear 포인터 의미, 동적 메모리(malloc/free)에 기반한 enqueue·dequeue 알고리즘과 빈 큐/단일 노드 예외 처리 규칙 정의 |
||
|
[19강] 큐 (2)
|
0:
42:
29
|
|
|
덱(deque)과 큐의 응용 핵심 정리
• 덱과 Linked Deque 구조: 양쪽 끝에서 삽입·삭제 가능한 double-ended queue 개념과 create/init/is_empty 연산, head·tail·llink·rlink로 구성된 양방향 연결 리스트 기반 Linked Deque 구조 및 노드 생성/에러·경계 처리 원리 정리 • 덱 연산 알고리즘: add_front/add_rear, del_front/del_rear, get_front/get_rear 연산에서 공백·단일 노드·일반 경우별 head·tail 및 양방향 링크 조정 절차와 O(1) 시간 복잡도 구현 원리 정리 • 큐의 응용 개념: 장치 간 버퍼링과 작업 순서 제어(프린터 서버·사용자별 큐) 및 은행·콜센터 대기 행렬 시뮬레이션에서 도착 패턴, 서비스 처리기 수, 서비스 시간, 평균 대기시간을 큐 모델로 분석하는 기법 정리 |
||
| 7장. 트리 | ||
|
[20강] 트리의 개념. 이진 트리의 소개 및 표현
|
0:
41:
48
|
|
|
트리의 개념과 이진 트리의 성질 및 표현 요약
• 트리와 이진 트리 기본 개념: 루트·부모·자식·형제·조상·자손·단말·서브트리·포리스트, 차수·레벨·높이 정의 및 이진 트리의 재귀적 정의(루트와 왼쪽·오른쪽 서브트리 구조) 정리 • 이진 트리 구조적 성질: 노드 수·간선 수·레벨별 최대 노드 수·높이 사이의 수학적 관계, 포화 이진 트리와 완전 이진 트리의 정의·노드 수 범위·높이 최소화 및 탐색 효율 특성 • 이진 트리 구현 방식: 포화/완전 이진 트리 기준 배열 인덱스 규칙(부모·왼쪽/오른쪽 자식 관계)과 연결 리스트 기반 링크 표현(TreeNode 구조체, 포인터 필드, 동적 메모리 할당) 비교 정리 |
||
|
[21강] 이진 트리의 순회
|
0:
40:
32
|
|
|
이진 트리 순회와 수식 트리 평가 핵심 정리
• 이진 트리 순회 종류: 전위(VLR)·중위(LVR)·후위(LRV)·레벨(BFS) 순회의 정의, 방문 순서, 재귀·큐 기반 구현과 시간 복잡도 O(n) 구조 정리 • 재귀 순회 알고리즘: if(root) 조건을 기반으로 루트·왼쪽·오른쪽 서브트리 방문 순서를 바꾸어 전위·중위·후위 순회를 구현하고, 트리 높이에 비례한 재귀 깊이 분석 • 수식 트리와 eval 알고리즘: 연산자/피연산자 이진 트리에서 전위·중위·후위 표기식과 순회의 일대일 대응을 정리하고, 후위적 계산 구조의 재귀 eval 함수로 사칙연산 수식 값을 평가하는 절차 설명 |
||
|
[22강] 이진 트리의 연산. 스레드 이진 트리
|
0:
41:
52
|
|
|
이진 트리 연산과 스레드 이진 트리 핵심 정리
• 이진 트리 기본 연산: 재귀 순회를 이용해 노드 수·단말 노드 수·높이를 계산하고, 차수·간선 수 관계로 단말 노드 수 공식 n₀ = n₂ + 1을 정식화함 • 스레드 이진 트리 개념 및 구조: NULL 링크(n+1개)를 중위 후속자 저장용 스레드로 재활용하고, right 포인터와 isThread 필드로 자식 링크와 스레드 링크를 구분하는 노드 구조를 정의함 • 스레드 이진 트리 알고리즘: find_successor로 중위 후속자를 탐색하고, thread_inorder로 스택·재귀 없이 중위 순회를 수행하며, thread_insert_right로 기존 right 링크·isThread를 새 노드에 상속 후 부모의 오른쪽 자식으로 삽입하는 절차를 사용함 |
||
|
[23강] 이진 탐색 트리 (1)
|
0:
50:
29
|
|
|
이진 탐색 트리 탐색·삽입·삭제와 시간복잡도 정리
• 이진 탐색 트리 정의·탐색 원리: 모든 노드에서 왼쪽 서브트리는 더 작은 키, 오른쪽 서브트리는 더 큰 키를 가지는 재귀적 구조를 통해 rsearch·isearch로 높이 h 이내에서 탐색 수행 • 삽입 연산(insert_node): 탐색 후 중복 키는 삽입 금지, 단말 위치에 새 노드 동적 할당·연결하며, 초기 공백 트리 처리를 위해 루트 이중 포인터(TreeNode **root) 사용 • 삭제 연산·시간 복잡도: 단말·자식 하나·자식 둘(후계자/선행자 치환) 세 경우로 나누어 링크 재조정·동적 메모리 해제 수행하며, 트리 높이에 따라 탐색·삽입·삭제 비용이 O(log n)~O(n) 범위가 되어 AVL·Red-Black 등 균형 트리 필요성 제시 |
||
|
[24강] 이진 탐색 트리 (2)
|
0:
34:
26
|
|
|
이진탐색트리(BST) 삭제 알고리즘 상세 정리
• 삭제 경우 분류와 포인터 구조: 단말노드, 한쪽 자식만 가진 비단말노드, 두 자식을 가진 비단말노드 세 유형으로 나누어 T(삭제 대상), P(부모), C(자식) 포인터를 사용해 부모-자식 포인터 재연결 규칙을 정의함 • 단말·한쪽 자식 노드 삭제 알고리즘: 단말노드는 부모의 해당 자식 포인터를 NULL로 변경 후 free, 한쪽 자식 비단말노드는 유일한 자식 C를 부모 P 또는 루트 포인터에 직접 연결하여 구조를 보존한 뒤 T를 free함 • 두 자식 노드 삭제 및 루트 처리: 두 자식 비단말노드는 오른쪽 서브트리의 가장 작은 노드(레프트모스트, inorder successor)를 찾아 키를 복사 후 그 노드를 단말/한쪽 자식 삭제 규칙으로 제거하며, 루트 변경이 필요한 경우 `TreeNode **root` 이중 포인터를 통해 루트 포인터 자체를 갱신함 |
||
|
[25강] 선택 트리. 포리스트
|
0:
49:
35
|
|
|
선택 트리와 포리스트의 이진트리 변환 및 순회 개념 정리
• 선택 트리(승자트리·패자트리) 기반 k-way 합병: 정렬된 k개의 런(run)을 단말노드로 갖는 완전 이진트리 구조에서 승자/패자 비교를 통해 매 단계 O(log k) 비교로 최솟값(또는 최댓값)을 선택하여 전체 n개 레코드를 O(n log k)에 단일 정렬 런으로 합병 • 승자트리·패자트리 구조 비교: 승자트리는 내부노드에 승자를 저장해 루트가 최종 승자가 되고, 패자트리는 내부노드에 패자를 저장하고 최종 승자를 별도 루트 상단에 두어 부모 비교만으로 재구성 가능하게 함으로써 특히 연결리스트 구현에서 링크 탐색을 단순화 • 포리스트와 이진트리 변환·순회: 분리된 트리 집합인 포리스트를 “첫 번째 트리 루트 → 전체 루트, 자식 서브트리 → 왼쪽, 나머지 트리 → 오른쪽” 재귀 규칙으로 단일 이진트리로 변환하고, 포리스트 전위·중위·후위 순회는 변환 이진트리 순회와 구조적으로 대응되지만, 레벨 순회는 형제 관계가 오른쪽 자식 계층으로 바뀌어 방문 순서가 달라질 수 있음 |
||
|
[26강] 분리 집합의 표현 (1)
|
0:
22:
37
|
|
|
분리집합(Partition)과 배열 기반 표현, 시간복잡도 및 가중 규칙 요약
• 분리집합(Partition) 개념: 전체 집합을 서로소이면서 공집합이 아닌 부분집합들로 분할하고, 각 부분집합의 합이 전체 집합이 되도록 구성하는 구조 • 트리·배열 기반 표현과 연산: 각 부분집합을 루트를 갖는 트리와 parent 배열로 표현하고, simpleFind로 대표 원소(루트) 탐색, simpleUnion으로 두 집합 병합을 수행 • 시간복잡도와 가중 Union: 단순 Union-Find는 편향 트리로 인해 Find의 최악 시간복잡도가 O(n²)까지 증가하므로, 노드 수를 비교해 작은 트리를 큰 트리에 붙이는 가중 Union으로 트리 높이를 줄이고 연산 효율을 개선함 |
||
|
[27강] 분리 집합의 표현 (2)
|
0:
55:
47
|
|
|
Summary Content:
분리 집합에서 weighted union과 collapsing find, 동치부류 응용 요약 • 분리 집합과 weightedUnion: parent 배열 음수값을 트리 크기로 사용하는 분리 집합 구조에서, 항상 노드 수가 큰 트리를 루트로 두고 작은 트리를 붙여 트리 높이를 O(log n)으로 제한하는 union 규칙 • collapsingFind와 경로 압축: find 연산 시 루트까지 경로상의 모든 노드를 루트에 직접 연결하여 트리 레벨을 붕괴시키고, weightedUnion과 결합해 평균 시간 복잡도를 O(α(n)) 수준으로 낮추는 알고리즘 • 동치부류와 분리 집합 응용: 동치 관계 i ≡ j를 collapsingFind로 각 루트를 찾은 뒤 weightedUnion으로 병합하여 동치부류를 트리(별 모양 구조)에 저장하고, 연결성 판정·컴포넌트 분할 등에서 효율적으로 관리하는 절차 |
||
| 8장. 우선순위 큐 | ||
|
[28강] 우선순위 큐 추상 데이터 타입. 우선순위 큐의 구현 방법. 히프
|
1:
09:
51
|
|
|
우선순위 큐와 힙의 구현 및 시간복잡도 정리
• 우선순위 큐 ADT와 구현 비교: 우선순위 기반 삽입·삭제 연산(insert, delete, find, is_empty, is_full) 정의 및 배열·연결 리스트(정렬/비정렬) 구현별 삽입·삭제 시간복잡도(O(1) vs O(n)) 구조적 비교 • 힙 자료구조와 배열 인덱스 구조: 완전 이진 트리 기반 최대 힙·최소 힙 정의, 부모–자식 우선순위 조건, 형제 비교 미고려 특성, 배열 구현 시 인덱스 규칙(i, 2i, 2i+1, ⌊i/2⌋) 및 구조체(heap 배열, hsize) 설계 • 힙 연산 알고리즘과 시간복잡도: 삽입 시 상향 이동(heapify up), 삭제 시 하향 이동(heapify down) 절차와 알고리즘 흐름 분석, 완전 이진 트리 높이 h ≈ log n 관계를 이용한 삽입·삭제 연산의 O(log n) 복잡도 도출 및 우선순위 큐 효율성 평가 |
||
|
[29강] 히프의 응용
|
0:
56:
41
|
|
|
힙 응용: 이산이벤트 시뮬레이션과 허프만 코드 생성 원리
• 힙 기반 우선순위 큐 응용: 배열 기반 최소 힙으로 우선순위 큐를 구현하고 힙정렬·이산이벤트 시뮬레이션에서 이벤트를 발생 시각 기준으로 정렬·처리 • 허프만 코드와 트리 구조: 문자 출현 빈도에 따른 가변 길이 prefix-free 이진 코드 부여를 위해 가중치 이진트리(허프만 트리)를 사용하여 비손실 압축 수행 • 허프만 트리 생성 알고리즘과 C 구현: 문자 빈도 노드를 최소 힙에 삽입 후 최소 가중치 노드 두 개를 반복 결합해 단일 루트 트리 생성하고, 트리 경로(0/1 배정)를 통해 인코딩·디코딩 코드 테이블을 구성하는 구조체·힙 연산 절차 정리 |
||
|
[30강] 우선순위 큐의 확장. 좌향트리 (1)
|
0:
38:
34
|
|
|
Summary Content:
우선순위 큐 확장과 좌향 트리(leftist tree) 구조 요약 • 확장 우선순위 큐·DEPQ 개념: 합병 연산·양쪽 끝 최소/최대 삭제·임의 노드 삭제·키 변경을 지원하는 우선순위 큐 및 DEPQ 연산(DP1~DP5)의 정의와 기능 정리 • 좌향 트리 구조와 높이 성질: 외부 노드·최단경로 sh(x) 정의, 좌향 조건 sh(lc(x)) ≥ sh(rc(x))와 보조정리 n ≥ 2^{sh(r)}-1, sh(r) ≤ log₂(n+1)를 통한 오른쪽 경로 로그 높이 분석 • 최소·최대 좌향 트리와 합병 연산: min/max-heap 속성을 갖는 좌향 트리 정의, 루트 키 비교 기반 오른쪽 경로 재귀 합병과 sh 교정 절차를 통해 합병·삽입·삭제를 모두 O(log n)에 수행하는 원리 정리 |
||
|
[31강] 좌향트리 (2)
|
0:
32:
38
|
|
|
최소 좌향트리 합병과 가중치편향 좌향트리, 보조정리 2 요약
• 최소 좌향트리 구조와 합병 개념: 노드 필드(data.key, sh, lc, rc)와 포인터의 포인터 사용을 통한 루트 포인터 갱신, minMeld/minUnion 기반의 오른쪽 경로 재귀 합병과 좌향 조건(sh) 유지로 O(log n) 시간 합병 수행 • 가중치편향 좌향트리(WBLT) 특성: 서브트리 내부 노드 수 w(x)를 가중치로 정의하고 모든 내부 노드에서 w(lc(x)) ≥ w(rc(x))를 유지하여, 합병 시 단일 하향 과정에서 w(x) 갱신이 가능하고 높이편향 좌향트리보다 구현·연산이 효율적인 구조 제공 • WBLT 보조정리 2와 시간복잡도 근거: 내부 노드 x에 대해 오른쪽 경로 길이 rm(x) ≤ log₂(w(x)+1)을 수학적 귀납법으로 증명하여, 좌향 조건에서 오른쪽 서브트리 가중치 상한 w(rc(x)) ≤ (w(x)−1)/2를 도출하고, 이를 통해 WBLT 연산의 O(log n) 시간복잡도와 구조적 균형성 보장 |
||
|
[32강] 이항 히프
|
1:
03:
21
|
|
|
이항 힙의 구조와 삭제 연산, 비용상환 개념 정리
• 이항 힙 구조와 이항 트리 특성: 서로 다른 차수의 최소 트리 집합으로 루트는 이중 연결 원형 리스트로 관리하며, 각 이항 트리 B_k는 서브트리 B_0,…,B_{k-1}로 구성되고 노드 수가 2^k, 최대 차수는 O(log n) 범위 유지 • 주요 연산과 시간복잡도: 삽입·힙 합병은 루트 리스트에 노드를 결합하고 min 포인터만 갱신하는 O(1) 연산이며, 최소 삭제는 min 루트 제거 후 자식 트리를 루트로 승격시켜 같은 차수 트리를 조인하여 재구성하며, 트리 수 s와 MaxDegree에 따라 O(s + log n) 시간 소요 • 비용상환(Amortized) 분석: 삽입·합병 시 구조 정비 작업을 미뤄 두었다가 삭제에서 한꺼번에 수행하고, 이 비용을 이전 연산들에 분산 상환함으로써 삽입·합병의 상환 시간복잡도는 O(1), 삭제의 상환 시간복잡도는 O(log n)인 우선순위 큐 성능 확보 |
||
|
[33강] 피보나치 히프
|
0:
23:
56
|
|
|
피보나치 힙 임의 삭제와 키 감소, 연쇄 분리 핵심 정리
• 피보나치 힙 노드 구조와 추가 연산: parent·childCut 필드를 포함한 노드 구조를 사용해 임의 노드 대상으로 임의 삭제·키 감소 연산을 지원하고, 루트 리스트 기반 최소 힙 형태로 우선순위 큐 기능 구현 • 임의 삭제·키 감소 및 연쇄 분리 절차: 임의 노드 삭제 시 자식 서브트리를 루트 리스트로 승격하고, 키 감소 시 힙 특성 위반 노드를 잘라 루트로 올린 뒤 childCut 상태에 따라 부모를 연쇄 분리하여 구조를 보정하며, 최소 포인터 갱신을 통해 amortized O(1) 키 감소·임의 삭제 달성 • childCut 메커니즘과 이항 힙 비교: childCut과 연쇄 분리를 통해 각 최소 트리의 차수–노드 수 지수적 하한(≈2^k 성장 규칙)을 유지하면서도 루트 리스트에 동일 차수 트리 공존을 허용하여, 이항 힙과 동급의 O(log n) 최소 삭제와 더불어 임의 노드 키 감소·삭제에 유리한 우선순위 큐 구조 확보 |
||
|
[34강] 페어링 히프. 대칭 최소-최대 히프
|
1:
02:
47
|
|
|
페어링 힙과 대칭 최소-최대 힙 핵심 연산 정리
• 페어링 힙(pairing heap) 연산 구조: 루트 비교 기반 합병으로 삽입·키-감소를 상수 시간 기대에 수행하고, 최소 삭제·임의 삭제는 루트 삭제 후 자식 서브트리들을 투 패스·멀티 패스 방식으로 단계적 합병하여 재구성 • 페어링 힙 삭제 알고리즘: 최소 삭제에서 루트 제거 후 남은 서브트리들을 좌→우 짝짓기 후 우→좌 재합병(투 패스) 또는 큐를 이용한 반복 2개씩 합병(멀티 패스)으로 하나의 힙으로 만들고, 임의 노드 삭제는 해당 서브트리 분리·부분 최소 삭제·두 힙 재합병 절차로 처리 • 대칭 최소-최대 힙(SMMH): 공백 루트를 가진 완전 이진 트리를 배열로 표현하여 형제 간 정렬(왼쪽 ≤ 오른쪽)과 조부모-손자 최소·최대 성질을 유지하고, 삽입 시 형제 비교+조부모 기준 버블업, 최소/최대 삭제 시 마지막 노드 이동 후 형제·손자 비교 기반 버블다운으로 모두 O(log n) 시간 보장 |
||
|
[35강] 구간 히프
|
0:
45:
32
|
|
|
구간 힙 정의와 삽입·삭제·보완적 범위 탐색 요약
• 구간 힙(interval heap) 구조와 성질: 각 노드에 구간 [a,b]를 저장하는 완전 이진 트리로, a≤b 및 부모 구간이 자식 구간을 포함하도록 유지하여 왼쪽 끝점 집합은 최소 힙, 오른쪽 끝점 집합은 최대 힙이 되며 루트가 전체 최소·최대 원소를 동시에 제공하는 이중 우선순위 큐 구조 • 구간 힙 연산 절차: 삽입 연산은 배열 끝에 원소 추가 후 a≤b·부모 포함 조건을 만족하도록 위로 재조정하고, 최소 삭제 연산은 루트의 왼쪽 끝점을 제거 후 마지막 노드 왼쪽 끝점을 올려 최소 힙 조건 중심으로 하향 재조정하여 두 연산 모두 O(log n) 시간 복잡도 달성 • 구간 힙 응용과 힙 비교: 보완적 범위 탐색에서 주어진 구간 [a,b] 밖의 점을 찾기 위해 루트 구간 포함 여부와 끝점 위치를 기준으로 서브트리를 선택적으로 순환 탐색하고, 이진 힙·leftist heap·binomial heap·Fibonacci heap 등 다양한 힙과 함께 우선순위 큐 연산(삽입·삭제·합병·키 변경)의 효율 개선 맥락에서 비교되는 구조 |
||
| 9장. 정렬 | ||
|
[36강] 정렬의 개념. 선택·삽입·버블·셀 정렬
|
1:
00:
18
|
|
|
정렬 기본 개념과 선택·삽입·버블·셸 정렬 비교 요약
• 정렬 기본 개념·안정성·목적 : 레코드·필드·키 구조와 오름차순/내림차순 정렬 정의, 동일 키 상대 순서 유지 여부에 따른 안정/불안정 정렬 구분, 검색 효율 향상을 위한 내부/외부 정렬 개념 정리 • 기본 내부 정렬 알고리즘(선택·삽입·버블 정렬) : 선택정렬·삽입정렬·버블정렬의 동작 절차(루프 구조·비교·교환/이동 방식), 안정성 여부(선택 불안정, 삽입·버블 안정), 시간복잡도 O(n²) 및 실제 성능 비교 정리 • 셸 정렬과 삽입정렬 응용 : 간격(gap)을 줄여가며 부분 리스트에 삽입정렬을 반복 적용하는 셸정렬 구조, gap 선택 규칙(절반 감소·홀수 조정)과 insSort 서브루틴 구성, 평균 시간복잡도 O(n^1.5) 수준의 성능 특성 정리 |
||
|
[37강] 합병 정렬
|
0:
52:
17
|
|
|
합병정렬 개념과 재귀·반복 구현, 시간복잡도 정리
• 합병정렬 기본 개념: 분할정복 기반으로 배열을 최소 단위까지 분할 후 정렬된 부분 리스트를 merge 연산으로 합병하며, 두 정렬 리스트의 선형 비교와 잔여 구간 복사로 안정적인 O(n) 합병 수행 • 재귀/반복 Merge Sort 구조: 재귀 버전은 구간 [l, m], [m+1, r]로 분할·정복 후 merge 수행하고, 반복 버전은 세그먼트 길이 s=1,2,4,…에 대해 mergePass로 길이 2s 부분 리스트를 순차 합병하며 보조 배열과 원본 배열을 교대로 사용 • merge/mergePass와 시간복잡도: merge는 정렬된 두 구간을 포인터 i,j,k 기반으로 비교·복사하여 안정적으로 통합하고, mergePass는 전체 배열을 세그먼트 단위로 합병하며 꼬리 구간은 조건적으로 합병 또는 복사 처리하여 각 단계 O(n), 단계 수 O(log n)로 전체 시간복잡도 O(n log n) 확보 |
||
|
[38강] 퀵 정렬
|
0:
26:
34
|
|
|
퀵정렬 알고리즘 흐름과 피벗 분할 과정 정리
• 퀵정렬 기본 개념: 평균 O(n log n), 최악 O(n²) 시간복잡도를 가지며 피벗을 기준으로 배열을 분할하고 재귀 호출로 부분 배열을 정렬하는 분할정복 정렬 알고리즘 • 피벗·분할(partition) 절차: 배열에서 피벗을 선택하고 양쪽 인덱스 i, j를 이동시켜 피벗보다 작은 값/큰 값 집합으로 분리한 뒤, 피벗의 최종 위치를 확정하고 좌·우 부분 배열에 동일 절차를 재귀적으로 적용하는 구조 • 의사코드·경계 조건: quickSort(list, left, right)에서 left |
||
|
[39강] 히프 정렬
|
0:
48:
08
|
|
|
힙 정렬(heap sort) 원리와 구현, 시간복잡도 정리
• 힙 구조와 우선순위 큐: 완전이진트리 기반 힙(배열 인덱스 1부터, 자식 2r·2r+1, 부모 r/2)로 우선순위 큐를 구현하고 최소 힙·최대 힙을 이용해 키 우선 삭제로 정렬을 수행함 • 힙정렬 알고리즘 구조: 방법1은 최소 힙에 n번 삽입 후 n번 삭제로 정렬하고, 방법2는 배열을 한 번에 최대 힙으로 구성(adjust 반복)한 뒤 루트-마지막 원소 교환 및 adjust 재호출을 반복해 오름차순 정렬함 • 시간복잡도 분석: 반복 삽입·삭제 방식은 삽입 O(nlogn)+삭제 O(nlogn)으로 O(nlogn), 배열 일괄 힙화 방식은 힙 구성 O(n)+정렬 단계 O(nlogn)으로 전체 O(nlogn)이며, adjust는 부분트리 높이에 비례해 O(logn) 시간에 최대 힙 속성을 복원함 |
||
|
[40강] 기수 정렬
|
0:
22:
57
|
|
|
기수정렬(radix sort) 알고리즘과 시간복잡도 핵심 정리
• 기수정렬(radix sort) 개념: 자릿수·다단계 키를 기준으로 버킷(큐)에 분배·수집하여 정렬하는 안정 정렬 알고리즘 구조 • LSD 기수정렬 구조: 1의 자리→상위 자릿수 순 패스, 0~9 버킷 큐 사용, (값/ factor)%10으로 자릿수 추출 후 enqueue/dequeue로 순서 유지 • 시간복잡도 O(dn): 자릿수 D에 대해 각 패스마다 n개 분배·수집으로 O(n) 수행, 전체 연산량 O(D·n)으로 상수/제한된 D에서 선형 시간 정렬처럼 동작 |
||
|
[41강] 리스트 정렬
|
0:
57:
53
|
|
|
리스트 정렬과 연결 리스트 기반 레코드 재배치 개념 정리
• 리스트 정렬 기본 개념: 레코드 직접 이동을 최소화하고 인덱스(링크 필드)만 정렬하여 논리적 순서를 구성한 뒤, 필요 시 최소 스왑으로 물리적 배열을 재배치하는 정렬 방식 • 이중 연결 리스트 기반 재배치(listSort1): next·prev 두 링크로 정렬된 논리 순서를 저장하고, prev 배열 생성 후 각 위치에 올 레코드를 스왑하며 제한된 링크(next[prev[i]], prev[next[i]])만 수정하는 O(mn) 재배치 알고리즘 • 단순 연결 리스트 기반 재배치(listSort2): 단일 link 배열에 “정렬된 다음 노드”와 “이동 추적 정보”를 겸용으로 저장하고, while(first < i) 탐색과 link[first], link[i] 갱신을 통해 prev 없이 레코드 재배치를 수행하는 O(mn) 알고리즘 |
||
|
[42강] 테이블 정렬. 내부 정렬 알고리즘 비교
|
0:
55:
14
|
|
|
테이블 정렬과 내부 정렬 알고리즘 비교 핵심 정리
• 테이블 정렬(table sort)·사이클 구조: 인덱스 테이블 t[i]와 trivial(t[i]=i)·non-trivial(tᵏ(i)=i, k>1) 사이클을 이용해 비당연 사이클 단위로 레코드를 재배치하는 내부 정렬 기법 • 테이블 정렬 성능 분석: 비당연 사이클 길이 k_i에 대해 이동 k_i+1회, Σ(k_i)=n, 전체 이동 ≤3n/2회로 리스트 정렬(3n 수준)보다 적은 레코드 이동으로 O(mn) 시간복잡도 달성 • 내부 정렬 알고리즘 비교·하이브리드 전략: 버블·선택·삽입 O(n²), 셸 ≈O(n^{1.5}), 힙·합병 O(n log n), 퀵 평균 O(n log n)·최악 O(n²), 데이터 크기에 따라 단순 정렬과 분할합병 정렬을 브레이크이븐 포인트 기준으로 혼합 사용 |
||
|
[43강] 외부 정렬 (1)
|
1:
13:
12
|
|
|
외부 정렬과 k-way 합병의 시간 복잡도 분석 핵심 정리
• 외부 정렬 구조와 I/O 모델 : 레코드·블록·런 개념과 디스크 탐구시간(ts)·회전지연시간(tl)·전송시간(trw)을 포함한 1블록 I/O 시간 tIO 정의, 내부 정렬 시간 tIS·레코드당 합병 시간 tm을 통한 전체 외부 정렬 시간식 구성 • 2-way 및 k-way 합병 복잡도 : 런 수 m에 대한 2-way 합병 패스 수 log₂m, k-way 합병 패스 수 logₖm 및 단순 비교 시 전체 비교 횟수 n(k−1)logₖm과 I/O 감소 vs CPU 비교 연산 증가 관계 정리 • 선택 트리(패자 트리) 기반 k-way 합병 최적화 : k개의 입력 런을 높이 log₂k 선택 트리로 관리하여 패스당 O(n log₂k), 전체 O(n log₂m) 비교 복잡도 달성 및 k와 무관한 CPU 시간, 메모리·버퍼 수 제약에 따른 최적 k 선택 원리 정리 |
||
|
[44강] 외부 정렬 (2)
|
0:
55:
46
|
|
|
외부 정렬 병렬 연산과 유동 버퍼 기반 k-원 합병 요약
• 외부 정렬 및 k-원 합병 구조: 패스 수 감소를 위한 k-원 합병·패자 트리 사용, 디스크·DMA·다수 입출력 버퍼를 활용한 리드–라이트–합병 병렬화 설계 • 버퍼 관리 및 유동 버퍼 원리: 입력 버퍼 2k개·출력 버퍼 2개 구성, lastKey[]와 우선순위 기반으로 비어 있는 버퍼를 동적으로 각 런에 재배치하여 끊김 없는 합병 유지 • 유동 버퍼 기반 합병 알고리즘: 각 런 끝에 무한대 키 배치, lastKey 최소 런을 넥스트 런으로 선택해 리드–라이트–합병을 대부분 단계에서 동시 수행함으로써 외부 정렬 전체 실행 시간 단축 |
||
|
[45강] 외부 정렬 (3)
|
0:
44:
33
|
|
|
유동버퍼 기반 k-원 합병 알고리즘과 런의 최적 합병 핵심 정리
• 유동버퍼 k-원 합병 알고리즘: 입력·합병·출력을 병행 수행하며, 패자트리를 이용해 k개의 런을 로그 시간 비교로 합병하고, 정리 1·2를 통해 단계 ⑥에서의 자유 버퍼 존재성과 다음 블록 선행 읽기를 보장함 • 가중치 외부 경로 길이와 합병 비용: 각 런 길이×트리 경로 길이의 합을 합병 비용으로 보고, 긴 런의 경로를 짧게·짧은 런의 경로를 길게 설계한 합병 트리가 최소 I/O·비교 횟수를 달성함 • 허프만 알고리즘과 최적 합병 트리: 런 길이를 빈도, 경로 길이를 코드 길이에 대응시켜 가장 짧은 런들부터 묶는 허프만 방식으로 k-원 합병 트리를 구성하면 가중치 외부 경로 길이가 최소가 되어 전체 합병 비용이 이론적으로 최적화됨 |
||
| 10장. 그래프 | ||
|
[46강] 그래프. 그래프 추상 데이터 타입. 그래프의 표현방법
|
1:
04:
38
|
|
|
그래프 정의와 표현, 주요 용어 정리
• 그래프 이론 기본 개념: 정점·간선으로 정의되는 그래프, 부분 그래프·연결 그래프·트리·완전 그래프·신장 트리와 차수·경로·단순 경로·사이클·오일러/해밀턴 개념 정리 • 그래프 분류와 성질: 무방향·방향·가중치 그래프, 인접 정점·부속 간선·진입차수·진출차수, 차수 합 = 2|E|·in/out-degree 합 = |E|·트리 |E|=|V|−1·완전 그래프 간선 수 n(n−1)/2 공식 정리 • 그래프 ADT와 표현: 그래프 추상 데이터 타입 연산(createGraph, init, insVertex, insEdge, delVertex, delEdge, adjacent 등)과 인접행렬·인접리스트 구조, C 구현 원리 및 시간·공간 복잡도 비교 |
||
|
[47강] 그래프 탐색. 연결 요소
|
0:
37:
05
|
|
|
그래프 탐색, DFS/BFS, 연결 요소 핵심 정리
• 그래프 탐색 개념: 시작 정점에서 경로가 존재하는 모든 정점을 방문하는 연산으로, visited 배열을 사용해 DFS·BFS로 그래프 구조와 연결성 분석 • DFS·BFS 알고리즘: DFS는 재귀 호출 또는 스택으로 깊이 우선 방문, BFS는 큐로 거리(계층) 순서 방문하며, 인접행렬은 O(n²), 인접리스트는 O(e) 시간복잡도 • 연결 요소(Connected Component) 탐색: 모든 정점에 대해 미방문 정점마다 DFS/BFS를 새로 시작해 한 번의 탐색 결과를 하나의 연결 요소로 정의, 전체 탐색은 인접리스트 O(n+e), 인접행렬 O(n²) |
||
|
[48강] 신장 트리 (1)
|
1:
04:
59
|
|
|
신장 트리와 이중결합 요소, 단절점, DFST 핵심 정리
• 신장 트리와 간선 분류: 원래 그래프와 정점은 같고 간선은 부분집합인 연결·무사이클·간선 수 n-1의 최소 연결 부분그래프로, 트리 간선과 비트리 간선(백 간선 포함)의 구조와 사이클 형성 관계 정리 • 단절점·이중결합 그래프·이중결합 요소: 정점 삭제로 연결 성분 수가 증가하는 단절점, 단절점이 없는 이중결합 그래프, 그래프 간선 집합을 분할하는 최대 이중결합 부분그래프인 이중결합 요소의 정의와 성질 정리 • DFST, dfn, low와 bicon 알고리즘: 깊이우선 신장 트리에서 dfn·low 계산, 백 간선 처리, dfn(u) ≤ low(w)에 기반한 단절점 판별 규칙과 DFS+스택을 사용하는 bicon 함수로 이중결합 요소를 분할·추출하는 절차 정리 |
||
|
[49강] 신장 트리 (2)
|
0:
52:
20
|
|
|
Summary Content:
이중결합 요소와 단절점, DFS 기반 탐색 알고리즘 정리 • 이중결합 요소와 단절점: 정점 제거 시 연결성 유지 여부로 정의되는 이중결합요소·단절점 개념과 그래프 신뢰성 분석에서의 구조적 역할 정리 • DFN·LOW와 백엣지: DFS 번호 DFN과 LOW 값 정의, 백엣지를 통한 LOW 계산 규칙, DFN(u)·LOW(v) 관계로 사이클·연결 구조 판별 • 단절점·이중결합요소 탐색 알고리즘: 재귀 DFS와 간선 스택을 이용해 DFN·LOW 계산, DFN(u) ≤ LOW(v) 조건으로 단절점 판정 및 스택 팝으로 이중결합요소 분해 절차 정리 |
||
|
[50강] 최소 비용 신장 트리 (1)
|
0:
30:
42
|
|
|
최소비용 신장트리와 Kruskal 알고리즘 핵심 구조 정리
• 최소비용 신장트리(MST) 개념: 주어진 그래프의 간선만 사용하여 모든 정점을 연결하되 사이클 없이 간선 수 n-1개와 가중치 합이 최소가 되도록 구성하는 신장트리 구조 • Kruskal MST 알고리즘 구조: 간선을 가중치 오름차순(정렬 또는 최소힙)으로 선택하면서 사이클을 만들지 않는 간선만 포함해 포리스트를 하나의 트리로 병합하는 그리디 알고리즘으로, 전체 시간 복잡도는 O(e log e) • Union-Find(분리집합) 최적화: 각 정점을 트리 기반 집합으로 관리하며 find/union으로 사이클 여부를 판별하고, weightedUnion과 collapsingFind로 트리 높이를 줄여 Kruskal에서의 집합 연산을 거의 상수 시간에 가깝게 최적화하는 자료구조 설계 |
||
|
[51강] 최소 비용 신장 트리 (2)
|
1:
01:
08
|
|
|
크루스칼·프림·솔린 알고리즘의 최소 비용 신장 트리 생성 및 증명 정리
• Kruskal 알고리즘·Union-Find 구조: 간선 가중치 오름차순 선택과 사이클 방지를 통한 MST 구성, 신장 트리 성질 및 최소 비용성(간선 치환 논리) 증명 • Prim 알고리즘·우선순위 큐: 정점 집합 확장과 최소 간선 선택, dist 배열·키 감소 연산·힙 기반 구현, 신장 트리 성질 및 최소 비용성(다른 MST와 비용 동등) 증명 • Sollin(Borůvka) 알고리즘·포리스트 병합: 각 트리에서 나가는 최소 비용 간선 병렬 선택과 트리 병합 과정을 통한 MST 구성, 병렬 계산에 유리한 구조 특징 정리 |
||
|
[52강] 최단 경로 (1)
|
1:
00:
59
|
|
|
단일 출발점 최단 경로: Dijkstra와 Bellman-Ford 비교 정리
• 단일 출발점 최단경로 문제: 하나의 시작 정점에서 모든 정점까지의 최단거리 계산 문제로, dist 배열과 집합 S 개념을 사용해 경로 길이를 구조적으로 표현 • Dijkstra 알고리즘: 모든 간선 가중치가 0 이상일 때 사용 가능한 탐욕적 최단경로 알고리즘으로, S에 포함되지 않은 정점 중 최소 dist 선택과 인접 정점 거리 갱신을 반복하며 O(n log n + e) 시간에 동작 • Bellman-Ford 알고리즘: 음수 가중치 허용·음의 사이클 부재를 전제로 간선 수를 기준으로 distₖ[u]를 반복 완화(relax)하는 동적 계획법 기반 알고리즘으로, 최대 n−1번 간선 완화를 통해 O(ne) 또는 O(n³)에 최단경로와 음수 사이클 여부를 판별 |
||
|
[53강] 최단 경로 (2)
|
0:
57:
02
|
|
|
플로이드 알고리즘과 트랜지티브 클로저
• 플로이드 알고리즘: Ak[i][j] 점화식 Ak[i][j] = min(Ak−1[i][j], Ak−1[i][k] + Ak−1[k][j])을 이용해 O(n³) 시간에 모든 정점 쌍 최단경로를 동적 계획법으로 계산하는 인접행렬 갱신 알고리즘 • 트랜지티브 클로저와 부울 행렬 곱: 방향 그래프의 경로 존재 여부를 A⁺, A*로 표현하고, 플로이드 알고리즘의 덧셈·최솟값 연산을 AND·OR로 치환한 부울 행렬 곱을 통해 도달 가능성 행렬을 계산하는 절차 • A⁺, A*와 사이클 판정: A⁺는 양의 길이 경로만, A*는 0 길이 자기 경로까지 포함하는 이행적 폐쇄 행렬이며, A⁺의 대각선 원소가 1인 정점의 존재 여부로 방향 그래프 내 사이클 존재를 판별하는 방법 정리 |
||
|
[54강] 위상 정렬
|
0:
22:
17
|
|
|
위상정렬과 진입차수 기반 알고리즘 핵심 정리
• 위상정렬(topological sort) 개념: 방향그래프에서 모든 간선 ⟨u, v⟩에 대해 선행자 u가 후속자 v보다 항상 먼저 오도록 정점을 나열하는 순서 결정 절차 • 진입차수(in-degree) 기반 알고리즘: 인접리스트로 그래프를 표현하고 각 정점의 진입차수를 계산한 뒤, 진입차수 0 정점을 스택에 넣어 반복적으로 pop·간선 삭제·후속자 진입차수 감소를 수행해 위상순서를 생성하는 과정 • 시간복잡도와 조건: 정점·간선을 각각 한 번씩만 처리하는 구조로 O(e+n) 시간에 동작하며, 사이클이 없는 방향그래프(DAG)에서만 모든 정점에 대한 유효한 위상정렬 결과가 존재함 |
||
|
[55강] 작업네트워크 (1)
|
0:
42:
30
|
|
|
작업 네트워크 AOV와 AOE, 위상정렬·임계경로 핵심 정리
• AOV 네트워크·위상정렬·부분순서: 작업을 정점으로 표현한 DAG에서 비반사·이행적 부분순서 관계를 위상정렬(topSort2)로 계산하며, 진입차수 배열을 스택 링크로 재사용해 O(n+e)로 작업 순서를 결정함 • AOE 네트워크·모조작업·프로젝트 기간: 사건을 정점, 작업을 가중치 간선으로 표현하고, 선행 제약 표현을 위해 수행시간 0 모조작업을 사용하며, 시작 사건에서 종료 사건까지 최장 경로 길이를 프로젝트 최소 완료시간으로 산정함 • 임계경로·Earliest/Latest 시간·자원 배치: 사건의 Earliest/Latest 시간과 작업의 e(i), l(i)로 임계작업(e=l)과 slack을 계산하여 임계경로를 결정하고, 비임계 경로의 여유시간을 활용한 자원 재배치로 프로젝트 기간을 효과적으로 단축함 |
||
|
[56강] 작업네트워크 (2)
|
0:
57:
39
|
|
|
AOE 작업 네트워크의 이른·늦은 작업시간과 임계경로 분석 정리
• 시간 엔티티(ee, le, e(i), l(i)) 정의: 이른 사건시간 ee는 선행 정점 ee+duration의 최대값, 늦은 사건시간 le는 후속 정점 le-duration의 최소값으로 정의하고, 각 간선 작업의 이른·늦은 작업시간 e(i)=발생 정점 ee, l(i)=도착 정점 le-duration으로 설정 • 시간 계산 알고리즘: 위상정렬(전진)로 모든 정점 ee와 작업 e(i)를 계산하고, 역위상정렬(후진)로 le와 l(i)를 구하며, 예제 네트워크를 통해 위상 순서·역위상 순서에 따른 수치 계산 절차를 구조적으로 제시 • 임계도·임계경로·오류 탐지: 임계도 slack(a_i)=l(i)-e(i)로 임계 작업(슬랙 0)과 임계경로를 판별하고, 슬랙이 양수인 작업은 자원 재배치 여유를 제공하며, ee가 0인 비시작 정점을 통해 도달 불가능 정점과 프로젝트 계획 오류를 탐지함 |
||
|
[57강] [부록] 패턴 매칭
|
1:
09:
01
|
|
|
단순 패턴 매칭과 KMP 알고리즘 핵심 정리
• 패턴 매칭 기본 개념과 단순 알고리즘: 스트링과 패턴 정의, 모든 시작 위치에서 순차 비교하는 단순 패턴 매칭 구조와 포인터 후진으로 인한 최악 시간 복잡도 O(nm) 분석 • KMP 알고리즘과 실패함수: 패턴 내부 반복을 이용해 되돌아감 없이 전진하는 KMP 구조, 실패함수 f(j)의 수학적 정의·접두사-접미사 일치 의미·예제 해석, 매칭 알고리즘의 세 가지 분기와 선형 시간 O(m) 보장 원리 • 실패함수 계산 알고리즘과 동적 프로그래밍: f[0..n-1]을 선형 스캔으로 구하는 fail 함수 구조, f[j-1]·f(f[j-1]) 등을 이용한 재귀적 갱신 과정, 각 인덱스의 유한 번 후진을 통한 전체 시간 복잡도 O(n) 성립 원리 |
||
| 11장. 해싱 | ||
|
[58강] 해싱 (1)
|
0:
48:
37
|
|
|
Summary Content:
해싱의 기본 구조와 충돌 해결 정리(정적 해싱 중심) • 해시 테이블과 해시 함수: 배열 기반 버킷·슬롯 구조 위에서 제산·폴딩·중간 제곱 등 해시 함수를 사용해 키를 버킷 인덱스로 매핑하여 평균 O(1) 탐색을 달성하는 기법 • 충돌·오버플로 개념: 서로 다른 키가 동일 해시 주소를 갖는 충돌과 버킷 슬롯 수를 초과해 저장 불가능해지는 오버플로를 정의하고, 해시 함수 설계와 구조 설계로 이들의 발생을 최소화하는 원리 • 충돌 해결 기법: 선형 조사·이차 조사·이중 해싱을 사용하는 개방 주소법과 버킷별 연결 리스트를 사용하는 체인법으로 정적 해싱에서 클러스터링·메모리 사용·탐색 성능을 조절하는 구조적 방법 정리 |
||
|
[59강] 해싱 (2)
|
1:
09:
14
|
|
|
해싱 성능 분석과 동적 해싱 핵심 정리
• 해싱 성능 분석 개념: 해시 순서·성공/실패 탐색(Sn, Un)·적재밀도 α 정의와 선형 조사법·이차 조사법·이중 해싱·체인법의 평균 비교 횟수 및 체인법 성능 특성 정리 • 해싱 복잡도와 활용: 순차 탐색·이진 탐색·탐색트리·해싱의 탐색·삽입·삭제 시간 복잡도 비교와 사전·심볼테이블 등 해싱 기반 주요 응용 구조 정리 • 동적 해싱 구조: 정적 해싱의 재해싱 한계를 배경으로 디렉터리 사용 방식과 비사용 방식의 버킷·비트 기반 확장 원리, 오버플로우 버킷 분할 및 국소 재해싱 절차 정리 |
||
| 12장. 탐색 | ||
|
[60강] 탐색. 정렬되지 않은 배열에서의 탐색
|
0:
44:
31
|
|
|
12장 탐색: 순차탐색과 정렬된 배열에서의 탐색 핵심 정리
• 탐색 기본 개념·복잡도: 항목(item)·탐색 키(key) 정의, 비교 연산 기준 시간복잡도(Big-O) 분석, 정렬 여부에 따른 탐색 전략 선택 원리 • 선형·이진 탐색 알고리즘: 순차 탐색(보초 기법 포함)과 정렬 배열 기반 이진 탐색(재귀·반복)의 절차·종료 조건·비교 횟수 특성 및 O(n) vs O(log n) 성능 구조 • 고급 탐색 기법: 정렬 배열에서의 색인 순차 탐색(인덱스 테이블+부분구간 이진 탐색, O(m + n/m))과 보간 탐색(키 값 분포 기반 위치 추정 공식, 균등 분포 시 O(log log n), 최악 O(n)) |
||
|
[61강] 균형 이진 탐색 트리 (1)
|
0:
57:
39
|
|
|
균형 이진 탐색 트리 AVL트리 회전과 삽입 핵심 정리
• AVL 트리와 균형 인수: 각 노드의 왼쪽·오른쪽 서브트리 높이 차이(BF)를 |BF|≤1로 유지하는 균형 이진 탐색 트리 개념과 BF 계산 원리 정의 • 불균형 타입과 회전 연산: LL·RR·LR·RL 네 가지 불균형 유형을 BF 부호와 키 관계로 분류하고, 각 경우의 단·이중 회전 구조와 포인터 재배치 규칙 정리 • 삽입과 재균형 알고리즘: 일반 BST 삽입 후 높이 기반 BF 재계산, rebalance 함수로 적절한 회전(LL/RR/LR/RL)을 적용해 트리 높이를 O(log n) 범위로 유지하는 절차 요약 |
||
|
[62강] 균형 이진 탐색 트리 (2)
|
0:
38:
33
|
|
|
2-3 트리와 2-3-4 트리의 구조와 삽입·분할 개념 정리
• M-원 탐색트리 개념: 노드당 여러 키·자식을 허용해 트리 높이를 줄이고, 외부 메모리·디스크 액세스 횟수를 감소시키는 다원 탐색 구조 • 2-3 트리와 삽입/분할: 2-노드·3-노드로 구성된 균형 다원 탐색트리로, 탐색 규칙에 따른 하향 탐색 후 단말·비단말·루트 분리와 가운데 키 승격·포인터 재배치로 균형 유지 • 2-3-4 트리와 top-down 분할: 2·3·4-노드(최대 키 3, 자식 4)로 구성된 트리로, 하향 탐색 중 4-노드를 즉시 분할해 backward split/merge 없이 삽입을 수행하는 상향식이 아닌 하향식 분할 전략 사용 |
||
|
[63강] 최적 이진 탐색 트리 (1)
|
1:
03:
35
|
|
|
최적 이진탐색트리와 확장이진트리, 동적계획 개념 정리
• 최적 이진탐색트리 개념: 탐색 성공·실패 확률 분포를 고려해 평균 비교 횟수(총 비용)를 최소화하는 트리 구조와 비용식 정의, 내부/외부 경로길이와 관계식 E = I + 2n, 내부 경로길이 최소 트리 조건 및 트리 높이와 평균 탐색비용 관계 정리 • 확장이진트리와 실패노드: 내부노드(성공 노드)와 외부노드(실패노드) 정의, n개 내부노드에 대한 n+1개 NULL 링크(외부노드) 구조, 성공·실패 탐색을 통합한 총 비용식과 외부노드 레벨에서 1을 빼는 이유, 단순 전수 탐색 방식의 지수 시간 복잡도 분석 • 동적 계획 기반 최적화: 부분 트리 T_{ij}, 비용 c_{ij}, 루트 r_{ij}, 가중치 w_{ij} 정의와 경계 조건, w_{ij} = q_i + ∑_{k=i+1}^j(p_k + q_k) = w_{i,j-1} + p_j + q_j 재귀식을 이용한 테이블 구축과 이를 통한 최적 이진탐색트리 T_{0n} 계산 구조 정리 |
||
|
[64강] 최적 이진 탐색 트리 (2)
|
1:
02:
30
|
|
|
최적 이진 탐색 트리 동적 계획법과 예제 정리
• 최적 이진 탐색 트리 개념: 키와 실패 구간 확률 $(p_i,q_i)$에 대한 기대 탐색 비용 최소 트리; 최적 부분 구조를 이용해 부분 트리 $T_{ij}$를 동적 계획으로 계산 • 가중치·비용·루트 점화식: 가중치 $w_{ij}=w_{i,j-1}+p_j+q_j$, 변형 비용 $c_{ij}=w_{ij}+\min_{i • OBST 알고리즘과 복잡도: $w[i][i]=q_i$, $c[i][i]=0$로 초기화 후 구간 길이 증가 순으로 $w,c,r$ 테이블을 채우며 최적 트리 복원, 기본 알고리즘은 $O(n^3)$ 시간 (Knuth 최적화 시 $O(n^2)$ 가능) |
||
|
[65강] 레드-블랙 트리 (1)
|
0:
51:
41
|
|
|
레드-블랙 트리 정의와 삽입, 높이 분석 핵심 정리
• 레드-블랙 트리 구조와 랭크 개념: RB1·RB2·RB3(루트·외부 노드 블랙, 연속 레드 금지, 경로별 블랙 노드 수 동일)와 랭크 r 정의를 통해 경로 길이 범위 r~2r와 높이·노드 수의 수학적 관계(h ≤ 2r, n ≥ 2^r−1, h ≤ 2log₂(n+1))를 정식화 • 보조정리와 BST·AVL 비교: 경로 길이 상한 정리(length(P) ≤ 2·length(Q))와 높이 O(log n) 보장을 기반으로, 일반 이진탐색트리 및 AVL 트리와의 균형 강도·탐색 성능·회전 빈도·구현 복잡도 차이를 구조적 관점에서 비교 • 레드-블랙 트리 삽입 알고리즘: BST 규칙으로 새 노드를 레드로 삽입한 뒤, 조부모-부모-노드 패턴(LLR·LRR 등 R타입 vs LLB·LRB 등 B타입)에 따라 색 변경만 수행하거나 회전+색 변경을 적용하여 레드-레드 위반 제거와 랭크·RB 조건 복구 과정을 단계적으로 정리 |
||
|
[66강] 레드-블랙 트리 (2)
|
1:
03:
42
|
|
|
레드블랙 트리 조인과 분할 연산의 구조와 시간복잡도 핵심 정리
• threeWayJoin 조인 연산: A < x < B 조건과 랭크(black-height) 전제를 바탕으로 새 루트 색을 조절하며 A, x, B를 하나의 레드-블랙 트리로 합치는 연산 구조 정의 • 레드블랙 트리 조인/분할 알고리즘: 랭크가 같은/다른 경우에 따라 경로를 따라 내려가 새 노드를 삽입·조정하고, split에서는 기준 키 노드에서 루트 방향으로 threeWayJoin을 반복해 L( • 랭크 불변식과 시간복잡도: 모든 경로의 블랙 개수 동일 조건을 유지하도록 회전·재색칠을 수행하고, 조인·분할 각각의 누적 연산량이 랭크 O(log n)에 비례함을 증명해 두 연산의 시간복잡도가 O(log n)임을 보장하는 분석 정리 |
||
|
[67강] 스플레이 트리 (1)
|
0:
33:
03
|
|
|
스플레이 트리 상향식 스플레이 연산과 회전 패턴 정리
• 스플레이 트리 개념·특징: 이진 탐색 트리에 스플레이 연산을 결합해 자주 접근하는 노드를 루트 근처로 이동시켜 평균 탐색·갱신 성능을 개선하는 자기조정형 트리 구조 • 상향식 스플레이 연산 절차: 탐색·삽입·삭제·분할 시 지정 노드(q)에서 시작해 루트가 될 때까지 zig(단일 회전) 및 zig-zig/zig-zag 이중 회전을 반복 적용하는 bottom-up 회전 알고리즘 • 회전 패턴 구조(LL, LR, RR, RL): q-부모 p-조부모 g의 상대 위치에 따라 LL·RR(zig-zig), LR·RL(zig-zag) 네 패턴으로 구분하며, 각 패턴에서 서브트리 재배치를 통해 중위 순서와 이진 탐색 트리 성질을 유지하면서 경로 높이를 단축함 |
||
|
[68강] 스플레이 트리 (2)
|
1:
00:
40
|
|
|
스플레이 트리 상향식 분석과 전위(potential) 기법 요약
• 스플레이 트리 랭크·전위 정의: 노드 랭크를 서브트리 크기의 로그로 정의하고(2^{r(i)} ≤ s(i) < 2^{r(i)+1}), 전위를 모든 랭크 합으로 두어 트리 구조 변화와 회전의 비용을 정량화함 • 상환 시간과 전위 기법: i번째 연산의 상환 시간을 실제 시간 + 전위 변화로 정의하고, 망원경 합을 통해 ∑실제 시간 = ∑상환 시간 + P₀ − Pₘ 관계를 사용하여 전체 실제 시간의 상계를 상환 시간 합으로 표현함 • 스플레이 회전 상환 분석과 전체 복잡도: 단일·이중 회전에서 전위 변화 ΔP를 계산해 한 번의 스플레이 상환 비용 상한 3(log₂n − r(q)) + 1을 얻고, 이를 m번의 탐색·삽입·삭제·조인·분할에 합산해 공백 스플레이 트리의 전체 시간 복잡도 O(m log n)을 도출함 |
||
|
[69강] 스플레이 트리 (3)
|
0:
39:
36
|
|
|
스플레이 트리 전위 분석과 하향식 스플레이 트리 구조 요약
• 전위(potential) 기반 상환 분석: 노드 랭크 합을 전위로 정의해 삽입·조인의 전위 증가를 연산당 O(log n)으로 제한하고, 스플레이 상환 비용을 포함한 m개 연산 전체 시간을 O(m log n)으로 도출 • 하향식(top-down) 스플레이 트리 구조: 루트에서 스플레이 노드까지 내려가며 small/big 임시 트리로 키를 분리하고, L·R·LR·RL·LL·RR 패턴별 재배치 규칙으로 스플레이 노드를 루트로 만드는 이진 탐색 트리 재구성 방식 • 상향식 대비 성질: 분할 종료 후 small·big과 스플레이 노드를 결합해 상향식과 동일한 최종 형태를 얻고, 이론적으로 동일한 O(log n) 상환 복잡도를 유지하면서 구현상 상수 인자 측면에서 더 빠른 경향을 보이는 스플레이 기법 |
||
|
[70강] 다원 탐색 트리
|
0:
35:
33
|
|
|
다원 탐색 트리 개념과 m-way search tree 탐색 구조 요약
• m-원 탐색 트리 개념: 한 노드에 여러 키와 포인터를 저장해 트리 높이를 줄이고 메모리·디스크 접근 횟수를 감소시키는 m차 탐색 트리 구조 • m-원 탐색 트리 구조와 용량: 노드 형식 n, A₀, (E₁, A₁)…(Eₙ, Aₙ)과 정렬·구간 조건으로 정의되며, 차수 m·높이 h일 때 최대 노드 수 (m^h−1)/(m−1), 최대 원소 수 m^h−1 관계를 가짐 • m-원 탐색 트리 탐색 알고리즘: 노드 내 키 구간 조건 Eᵢ.K ≤ x < Eᵢ₊₁.K으로 비교해 일치 시 반환, 불일치 시 대응 서브트리 Aᵢ로 이동하는 하향식 검색 절차로 고성능 탐색을 수행함 |
||
|
[71강] B트리 (1)
|
0:
42:
50
|
|
|
B-트리의 정의와 구조, 원소 수 및 탐색 횟수 특성 정리
• B-트리와 특수 형태(2-3 트리, 2-3-4 트리) : 차수 m인 균형 m-원 탐색트리 정의, 루트·내부노드 최소 차수 조건, 단말노드 동일 레벨 구조 및 차수별 내부노드 차수 범위(2-3, 2-3-4, 포화이진트리) 비교 • B-트리의 원소 수·외부노드 수 : 높이 l에 따른 최대·최소 노드/원소 수 공식, 최소 원소 수 N_min와 외부노드 수(N_min+1)의 관계를 통한 구조적 하한·상한 분석 • B-트리의 탐색 횟수와 성능·차수 선택 : 최악 탐색 실패 시 접근 횟수 상한 l ≤ log_{m/2}((N+1)/2)+1에 기반한 O(log N) 성능, 차수 확대에 따른 트리 높이·디스크 I/O 감소 효과, 디스크·메모리 상주 환경에서 인덱스 구조(B/B+트리) 설계 시 차수 선택 원리 정리 |
||
|
[72강] B트리 (2)
|
0:
43:
45
|
|
|
B-트리 삽입 과정과 디스크 접근 분석 정리
• B-트리 삽입 알고리즘: 단말노드 탐색 후 키 삽입, 노드 용량 초과 시 가운데 키 승격·좌우 노드 분할·루트까지 상향 전파로 트리 균형 유지 • 분할 구조와 횟수 상한: 차수 m에서 왼·오른쪽 노드 키 분배 규칙과 루트/일반 분할 시 노드 수 증가 관계를 통해 전체 분할 횟수 상한 p-2 도출 • 디스크 접근 복잡도: 높이 h에서 최악 디스크 접근 3h+1, 노드 최소 원소 수 기반 분할 평균 ≤ 1/(m/2-1), 평균 디스크 접근 ≈ h+1로 대용량 디스크 인덱스 효율성 설명 |
||
|
[73강] B트리 (3)
|
0:
47:
49
|
|
|
B-트리에서의 삭제 연산과 회전·결합, 삭제비트 개선
• B-트리 삭제 연산: 내부 노드 삭제를 단말 노드 삭제로 변환하고 최소 원소 수 조건 위반 시 회전·결합을 통해 구조를 복구하며, 2-3 트리 사례와 함께 디스크 접근 횟수(최악 3h)를 분석함 • 회전(Rotation)·결합(Merge) 연산: 형제 노드의 여분 키를 빌려오는 회전과 최소치 형제와 부모 키를 묶는 결합을 통해 키 순서·서브트리 범위·노드 최소/최대 원소 수 조건을 유지하면서 상향으로 전파 처리함 • 삭제 비트 기반 개선: 각 키에 삭제 비트를 두어 논리 삭제로 회전·결합을 제거하고 노드 구조를 유지하며, 삭제 시 디스크 접근을 h+1로 줄이고 삭제된 엔트리를 이후 삽입 시 재사용해 분할 빈도를 감소시킴 |
||
|
[74강] B+트리 (1)
|
0:
30:
30
|
|
|
B+-트리 노드 구조와 정의, 탐색 알고리즘 정리
• B-트리·B+-트리 기본 개념: 디스크 기반 m-원 탐색 트리로서 높은 차수를 통해 트리 높이를 줄여 디스크 I/O를 최소화하며, B+-트리는 인덱스 노드(키+포인터)와 데이터 노드(키+원소)를 분리하고 모든 데이터 노드를 동일 레벨의 단말로 두는 구조를 가짐 • B+-트리 형식적 정의와 키 구조: 차수 m B+-트리는 인덱스 노드가 차수 m B-트리 형태(n, A₀, (K₁, A₁), …, (Kₙ, Aₙ), 0 ≤ n < m)를 이루고, 모든 데이터 노드가 같은 레벨에서 이중 연결 리스트로 연결되며, 각 서브트리 Aᵢ는 Kᵢ ≤ key < Kᵢ₊₁ 관계를 만족하여 인덱스 키와 데이터 키의 중복을 허용하면서 범위 조건(등호 포함 좌측 경계)을 정의함 • B+-트리 탐색 및 범위 질의: 탐색 시 루트에서 시작해 인덱스 노드마다 K₀=-∞, Kₙ₊₁=+∞를 설정하고 Kᵢ ≤ x < Kᵢ₊₁을 만족하는 i의 서브트리 Aᵢ로 내려가 단말 데이터 노드에서 최종적으로 키 x를 검색하며, [a,b] 범위 탐색은 a가 위치한 데이터 노드까지 위 규칙으로 내려간 뒤 오른쪽 이중 연결 리스트를 따라가며 상한 b 미만(또는 이하)까지 순차적으로 원소를 수집함 |
||
|
[75강] B+트리 (2)
|
0:
36:
16
|
|
|
B+-트리 삽입과 삭제 연산 핵심 과정 정리
• B+-트리 노드 제약과 차수 개념: 데이터노드 최대 원소수 c와 최소 원소수 ⌈c/2⌉, 인덱스노드 차수 m에 따른 키 범위(최대 m-1, 최소 m/2-1) 및 포인터 개수 m 정의 • B+-트리 삽입·분할 절차: 탐색 후 데이터노드 삽입 → 데이터노드 용량 초과 시 분할 및 새 노드 첫 키를 부모 인덱스노드에 삽입 → 인덱스노드 키 초과 시 중앙 키 승격 분할 → 루트 분할 시 새 루트 생성과 트리 높이 증가 • B+-트리 삭제·조정 절차: 데이터노드에서만 키 삭제 후 최소 원소수 위반 시 인접 노드에서 빌려오기 또는 결합 수행, 그 결과 인덱스노드에서 B-트리 규칙(회전·결합·연쇄 조정) 적용, 루트 공백 시 자식 승격으로 트리 높이 감소 처리 |
||
|
[76강] 디지털 탐색 트리. 이진 트라이와 패트리샤
|
1:
09:
54
|
|
|
디지털 탐색트리와 이진 트라이, 패트리샤 구조 및 연산 정리
• 디지털 탐색 트리·이진 트라이·압축 이진 트라이: 키의 비트/자릿수로 분기하는 디지털 탐색 구조, 분기 노드·원소 노드 구분 및 bitNumber로 차수 1 노드 제거를 통한 높이·공간 최적화 개념 정리 • 패트리샤(PATRICIA) 구조와 탐색 알고리즘: 부가 분기 노드(bitNumber, data, lChild, rChild)와 헤더 노드 정의, bitNumber 증가 조건 탐색 루프와 최종 노드 data 비교로 탐색 성공/실패 판정 절차 • 패트리샤 삽입 과정 및 노드 수 관계: 도착 노드와 삽입 키의 최초 상이 비트 위치 j 기반 새 노드 bitNumber 결정·부모 선택·자식 분기 규칙과 N0 = N2 + 1(원소 노드 수 = 분기 노드 수 + 1) 관계 활용한 구조 설계 원리 |
||
|
[77강] 다원 트라이 (1)
|
0:
52:
29
|
|
|
다원 트라이 구조와 종료문자, 탐색 알고리즘 정리
• 다원 트라이(m-ary trie) 구조: 키의 각 자릿값을 인덱스로 사용하는 고차수 탐색 트리로, 분기 노드·원소 노드, 문자/숫자 집합 크기에 따른 자식 포인터 배열로 구성됨 • 종료문자(terminator) 설계: 특수문자를 문자 집합에 추가해 키 끝을 명시함으로써 접두사 모호성을 제거하고 어떤 키도 다른 키의 진접두사가 되지 않도록 표현함 • 탐색 알고리즘(search): 레벨 번호와 키 인덱스를 1:1 대응시키고 getIndex로 자식 포인터를 선택하는 재귀 탐색으로, 경로 추적 후 단말 원소 노드에서 전체 키를 1회 비교함 |
||
|
[78강] 다원 트라이 (2)
|
0:
52:
45
|
|
|
다원 트라이의 샘플링 전략과 압축 트라이 구조 정리
• 샘플링 전략과 상이한 길이 키 처리: 레벨별 자릿수 선택(앞·뒤·난수·혼합)으로 트라이 높이·디스크 접근 최적화, 특수 문자 또는 분기 노드 data 필드로 접두사/접수사 모호성 제거 • 삽입·삭제와 노드 압축: 공통 접두부 공유 기반 삽입, 삭제 시 원소 노드 해제와 NULL 복원, 분기 노드 count 필드로 자식 수 관리 후 자식 1개 분기 노드 상향 병합으로 구조 압축 • 압축 트라이와 digitNumber 구조: 자식 1개 분기 노드 제거로 높이·공간 절감, 분기 자릿수 digitNumber(또는 skip/레이블 간선)로 보존하여 탐색·삽입 시 최초 상이 자릿수 기준 새 분기 노드 삽입 및 O(d) 복잡도 유지 |
||
|
[79강] 다원 트라이 (3)
|
0:
38:
09
|
|
|
압축 트라이 삭제와 생략필드·레이블 간선 개념 정리
• 숫자 번호·skip 필드를 가진 압축 트라이: 분기 자릿수를 숫자 번호 또는 skip으로 표현하며 탐색·삽입·삭제 수행, 삭제 O(d + r), 삽입 O(r·d) 시간 복잡도와 분기노드 병합(자식 1개 시 압축) 규칙 정리 • 생략(skip) 필드·레이블 간선 구조: 분기노드에 skip와 element 필드를 두어 생략 자릿수와 subtrie 대표 원소노드를 기록하고, 숫자 번호 방식과 동치 구조로 동일한 탐색·삽입·삭제 로직을 구현 • 레이블 간선 연산 원리: 탐색·삽입 시 element가 가리키는 키의 skip 구간만 비교해 실제 비교량을 줄이고, 삭제 시 대표 원소노드 삭제 여부에 따라 element 갱신 여부를 결정하는 최적화된 압축 트라이 연산 구조 정리 |
||
|
[80강] 접미 트리 (1)
|
0:
54:
15
|
|
|
다수 패턴 매칭과 접미 트리
• 다수 패턴 매칭 복잡도: KMP 기반 다중 패턴 탐색의 시간복잡도 O(|P₁|+…+|Pₖ|+k|S|) 구조와 긴 텍스트·패턴 다수 환경에서의 k|S| 병목 분석 및 접미 트리 도입 동기 • 접미 트리 구조와 구현: 문자열 S의 모든 접미사에 대한 압축 트라이 정의, suffix trie→suffix tree 압축, 접미 인덱스 기반 리프 표현, 레이블 간선·레벨 번호를 결합한 내부 표현과 친인간적 표기 방식 • 접미 트리 제약과 기호 추가: “어떤 접미사도 다른 접미사의 적합한 접두사가 되지 않는다”는 키 유일성 제약, data 예시의 모호성 문제, 문자열/접미사에 종결 기호 #를 추가하는 두 가지 방법과 모호성 제거 효과 비교 |
||
|
[81강] 접미 트리 (2)
|
0:
48:
11
|
|
|
접미 트리에서 서브스트링 탐색과 주요 응용 정리
• 접미 트리 기반 서브스트링 탐색 원리: “패턴 P가 S의 서브스트링 ⇔ 어떤 접미사의 접두사”라는 정리에 따라 루트에서 패턴 문자를 순차 비교하여 O(|P|) 시간에 존재 여부를 판정하고, 분기 노드·원소 노드 위치에 따라 출현 횟수와 위치를 해석함 • 접미 트리 응용 1 – 출현 위치·다중 스트링 탐색: leaf 사전순 연결과 각 분기 노드의 (first, last) leaf 참조를 이용해 패턴의 모든 출현 위치를 열거하고, 특수 구분자를 붙여 만든 다중 스트링 접미 트리에서 패턴을 포함하는 모든 스트링을 효율적으로 식별함 • 접미 트리 응용 2 – 반복·공통 서브스트링 탐색: 분기 노드 서브트라이의 leaf 개수와 루트까지의 레이블 길이를 이용해 단일 스트링에서 최소 m번 이상 반복되는 최장 서브스트링을 찾고, 두 스트링의 다중 접미 트리에서 양쪽 스트링 leaf를 모두 포함하면서 레이블 길이가 최대인 분기 노드를 선택해 최장 공통 서브스트링을 구함 |
||
|
[82강] 트라이와 인터넷 패킷 전송
|
1:
24:
24
|
|
|
트라이와 IP 라우팅 자료구조 개념 정리
• IP 라우팅과 접두사 기반 라우팅: IPv4/IPv6 주소와 라우팅 테이블 (P, NH)을 이용해 수신지 주소의 가장 긴 접두사 일치(longest prefix match)로 다음 홉을 결정하는 원리와 접두사·주소 집합 구조 정리 • 1-비트 트라이·고정 스트라이드 트라이: 1비트 단위 이진 트라이의 구조·탐색 규칙·시간복잡도 O(W) 특성과, 레벨별 고정 스트라이드 S(다원 트라이)를 사용해 트리 높이·메모리 접근을 줄이는 대신 2^S 메모리 유닛 증가시키는 설계 원리 정리 • 가변 스트라이드 트라이와 트레이드오프: 노드별로 다른 스트라이드를 허용해 접두사 분포·트래픽 밀도에 맞춰 트리 높이와 접근 횟수를 최소화하되, 국부적 메모리 폭증·설계 복잡도 증가를 감수하는 구조적 트레이드오프 및 세 트라이 간 성능 비교 정리 |
||
신흥철 교수님
자료구조 통합과정
