ExamStudy CBT 대학교 메인

자료구조 중간고사 핵심 용어

과목코드 DATA_STRUCTURES
담당교수 미등록
시험일정 미정 / 미정 ~ 미정
시험장소 미정
용어 그룹 수 5개 그룹
전체 용어 수 90개 용어
비교 그룹 수 5개 그룹
비교 항목 수 30개 항목

Study Mode

용어 요점정리

같은 시험 문제풀기

총 90개 용어를 그룹별로 정리했습니다.

Group 1

파이썬·복잡도·재귀

24개 용어
용어 1 시험 중간고사

변수

객체를 참조하는 이름이다. a=[1]에서 a는 리스트 그 자체의 복사본이 아니며 다른 객체로 다시 바인딩할 수 있다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.3; 1.1. preliminary.mp4, 00:13:58~00:14:28

용어 2 시험 중간고사

객체 참조

이름이나 컨테이너가 객체를 가리키는 연결이다. b=a는 보통 객체를 복제하지 않고 동일 객체에 대한 참조를 공유한다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.3; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.4; 1.1. preliminary.mp4, 00:18:43~00:19:47; 2.2. 배열(1).mp4, 00:20:50~00:23:25

용어 3 시험 중간고사

클래스

속성과 동작을 정의하는 객체의 설계 단위이다. Car 클래스에서 서로 다른 색과 속도의 인스턴스를 만들 수 있다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.5; 1.1. preliminary.mp4, 00:21:53~00:23:19

용어 4 시험 중간고사

인스턴스

특정 클래스에서 생성된 개별 객체이다. 같은 클래스의 a와 b도 서로 다른 인스턴스 속성을 가질 수 있다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.5; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.6; 1.1. preliminary.mp4, 00:24:51~00:25:53

용어 5 시험 중간고사

생성자 초기화

__init__으로 생성된 인스턴스의 초기 속성을 설정하는 과정이다. self.speed=0은 해당 인스턴스의 속도를 초기화한다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.6; 1.1. preliminary.mp4, 00:24:21~00:24:51

용어 6 시험 중간고사

인스턴스 속성

self.color처럼 개별 객체에 속한 상태이다. 한 객체의 속도 변경이 다른 객체의 속도를 자동 변경하지는 않는다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.6; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.7; 1.1. preliminary.mp4, 00:26:23~00:28:40

용어 7 시험 중간고사

메서드

객체에 연결된 연산이다. car.speedUp()은 car의 상태를 변경하는 동작의 예이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.7; 1.1. preliminary.mp4, 00:37:45~00:38:21

용어 8 시험 중간고사

상속

부모 클래스의 속성과 동작을 자식 클래스에서 재사용하고 확장하는 관계이다. 자식 생성자에서 super()로 부모 초기화를 호출할 수 있다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.10; 1.1. preliminary.mp4, 00:34:32~00:35:33

용어 9 시험 중간고사

메서드 재정의

자식 클래스가 부모와 같은 이름의 메서드를 새 동작으로 정의하는 것이다. 터보 차량의 speedUp이 부모 가속 규칙을 바꾸는 예이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.11; 1.1. preliminary.mp4, 00:39:49~00:40:52

용어 10 시험 중간고사

동등성 연산

__eq__ 등으로 두 객체가 의미상 같은지를 판단하는 연산이다. 같은 색인지 비교하는 규칙은 객체 동일성 검사와 구별된다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.8

용어 11 시험 중간고사

문자열 표현

__str__을 통해 제공하는 읽을 수 있는 객체 설명이다. 반환 결과는 문자열이어야 하며 출력 형식을 정하는 데 사용된다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.8

용어 12 시험 중간고사

실험적 분석

구현을 실제 환경에서 실행하여 시간을 측정하는 방법이다. 하드웨어·입력 표본의 영향을 받아 모든 입력에 대한 보장은 주지 않는다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.14; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.16; 1.2. 복잡도분석.mp4, 00:05:36~00:10:03

용어 13 시험 중간고사

이론적 분석

기본 연산 수를 입력 크기의 함수로 모델링하는 분석이다. 구현 환경 차이를 줄이지만 연산 비용에 대한 가정을 명시해야 한다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.16; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.17; 1.2. 복잡도분석.mp4, 00:10:03~00:10:54

용어 14 시험 중간고사

시간 복잡도

입력 크기에 따라 연산량이 증가하는 형태이다. 한 번 순회는 선형, 모든 원소 쌍 검사는 이차 시간이 대표적이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.14; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.17; 1.2. 복잡도분석.mp4, 00:03:33~00:05:06

용어 15 시험 중간고사

공간 복잡도

수행에 필요한 메모리 양의 증가를 분석한 것이다. 보조 공간을 말할 때는 입력 저장공간 포함 여부를 구별한다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.14; 1.2. 복잡도분석.mp4, 00:05:06~00:05:36

용어 16 시험 중간고사

Big-O

충분히 큰 입력에서 양의 상수배로 제한되는 점근적 상한이다. n²는 O(n²)인 동시에 O(n³)이므로 항상 타이트한 차수를 뜻하지 않는다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.19; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.20; 1.2. 복잡도분석.mp4, 00:24:04~00:25:38

용어 17 시험 중간고사

Big-Omega

충분히 큰 입력에서 양의 상수배 이상이 되는 점근적 하한이다. 입력의 최선 사례라는 뜻과는 다르다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.26; 1.2. 복잡도분석.mp4, 00:43:17~00:43:46

용어 18 시험 중간고사

Big-Theta

같은 기준 함수에 대한 점근적 상한과 하한이 함께 성립하는 관계이다. 3n+2는 Θ(n)이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.26; 1.2. 복잡도분석.mp4, 00:43:46~00:44:04

용어 19 시험 중간고사

최선 사례

동일 크기의 입력들 중 비용이 가장 작은 경우이다. 선형 탐색에서 첫 원소가 목표인 경우가 예이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.27; 2.1. 순환(Recursion).mp4, 00:04:45~00:05:17

용어 20 시험 중간고사

최악 사례

동일 크기의 입력들 중 비용이 가장 큰 경우이다. 선형 탐색에서 목표가 없는 입력이 예이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.27; 2.1. 순환(Recursion).mp4, 00:05:17~00:07:30

용어 21 시험 중간고사

재귀

함수가 자기 자신을 호출해 더 작은 문제의 결과로 답을 구성하는 방법이다. 종료 조건과 문제 크기 감소가 함께 필요하다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.28; 2.1. 순환(Recursion).mp4, 00:11:03~00:11:34

용어 22 시험 중간고사

기저 사례

추가 재귀 호출 없이 답을 반환하는 조건이다. 0!까지 다루려면 0에 대한 종료도 설계해야 한다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.28; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.29; 2.1. 순환(Recursion).mp4, 00:12:58~00:13:57

용어 23 시험 중간고사

반복

for·while 등의 반복문으로 상태를 갱신해 문제를 해결하는 방식이다. 재귀와 같은 시간 차수여도 호출 스택 비용은 다를 수 있다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.30; 2.1. 순환(Recursion).mp4, 00:20:36~00:22:37

용어 24 시험 중간고사

제곱 거듭제곱

밑을 제곱하고 지수를 절반으로 줄여 거듭제곱을 계산하는 방식이다. 한 번씩만 재귀하면 산술 연산 수와 깊이가 O(log n)이다. 출처: 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.31; 1. Preliminary+복잡도표현+Recursion.pdf, PDF p.32; 2.1. 순환(Recursion).mp4, 00:31:56~00:39:46

Group 2

배열 기반 시퀀스

16개 용어
용어 25 시험 중간고사

배열

동일 크기 셀을 연속된 메모리 영역에 배치한 구조이다. 시작 주소와 인덱스로 셀 위치를 계산한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.6; 2.2. 배열(1).mp4, 00:11:05~00:13:04

용어 26 시험 중간고사

참조 배열

객체 본체 대신 객체 참조를 저장하는 배열이다. 크기가 다른 문자열 객체도 같은 크기의 참조 셀로 가리킬 수 있다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.7; 2.2. 배열(1).mp4, 00:18:10~00:20:16

용어 27 시험 중간고사

compact array

같은 유형의 원시값을 셀에 직접 저장하는 배열이다. array 모듈은 유형 코드로 원소 표현을 정한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.10; 2.2. 배열(1).mp4, 00:36:47~00:39:57

용어 28 시험 중간고사

얕은 복사

바깥 컨테이너를 새로 만들되 원소 객체의 참조는 공유하는 복사이다. 중첩 리스트의 내부 변경은 원본에서도 보일 수 있다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.8; 2.2. 배열(1).mp4, 00:25:05~00:27:03

용어 29 시험 중간고사

동적 배열

실제 원소 수와 별도로 여유 용량을 관리하며 필요하면 더 큰 배열로 교체하는 구조이다. 리스트의 가변 길이를 지원한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.14; 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.16; 3.1. 배열(2)-dynamic_array.mp4, 00:02:38~00:05:38

용어 30 시험 중간고사

용량

기반 배열에 확보한 셀 수이다. 저장된 실제 원소 수와 같을 필요가 없으며 빈 셀도 포함한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.14; 3.1. 배열(2)-dynamic_array.mp4, 00:11:54~00:12:51

용어 31 시험 중간고사

크기

현재 논리적으로 저장한 원소 수이다. 용량 8 배열에 원소 5개라면 크기는 5이다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.16; 3.1. 배열(2)-dynamic_array.mp4, 00:11:54~00:12:23

용어 32 시험 중간고사

상각 분석

드물게 발생하는 큰 비용을 포함해 연산열 전체 비용을 분석하는 방법이다. 입력 분포를 가정한 평균 분석과 다르다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.19; 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.20; 3.1. 배열(2)-dynamic_array.mp4, 00:20:23~00:27:24

용어 33 시험 중간고사

기하 증가

용량을 일정 배수로 늘리는 정책이다. 두 배 증가의 누적 복사량은 기하급수 합으로 선형 범위에 머문다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.20; 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.21; 3.1. 배열(2)-dynamic_array.mp4, 00:27:53~00:30:16

용어 34 시험 중간고사

산술 증가

용량을 고정된 칸 수씩 늘리는 정책이다. 긴 append 연산열에서는 누적 재할당 비용이 이차 차수가 된다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.22; 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.23; 3.1. 배열(2)-dynamic_array.mp4, 00:33:25~00:34:23

용어 35 시험 중간고사

배열 축소

사용률이 충분히 낮아졌을 때 용량을 줄이는 작업이다. 확장 경계와 축소 경계를 벌려 반복 진동을 피한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.24; 3.1. 배열(2)-dynamic_array.mp4, 00:43:47~00:44:58

용어 36 시험 중간고사

배열 중간 삽입

원하는 인덱스 뒤의 기존 원소들을 한 칸 뒤로 옮기고 새 값을 놓는 연산이다. 앞쪽 삽입일수록 이동이 많다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.28; 3.2. 배열(3).mp4, 00:06:32~00:09:42

용어 37 시험 중간고사

배열 중간 삭제

제거 위치 뒤의 원소들을 당겨 빈 셀을 메우는 연산이다. pop(0)의 이동 비용은 길이에 비례한다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.29; 3.2. 배열(3).mp4, 00:12:44~00:13:41

용어 38 시험 중간고사

삽입 정렬

정렬된 접두 구간에 다음 원소를 적절히 삽입하는 정렬이다. 엄격한 >로 이동하면 안정적이며 최악 시간은 Θ(n²)이다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.38; 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.39; 3.2. 배열(3).mp4, 00:35:58~00:41:21

용어 39 시험 중간고사

시저 암호

알파벳 인덱스에 일정 이동량을 더하고 26으로 나눈 나머지로 치환하는 방식이다. 예를 들어 3칸 이동은 Z를 C로 바꾼다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.40; 3.2. 배열(3).mp4, 00:41:56~00:44:01

용어 40 시험 중간고사

이차원 리스트

행 리스트들을 원소로 갖는 리스트이다. 각 행을 별도로 생성해야 행 하나의 변경이 다른 행에 전파되지 않는다. 출처: 2. Chapter_5_-_Array-Based_Sequences.pdf, PDF p.44; 3.2. 배열(3).mp4, 00:45:36~00:50:40

Group 3

스택·큐·덱

12개 용어
용어 41 시험 중간고사

스택

삽입과 삭제가 한쪽 top에서 일어나는 후입선출 ADT이다. 마지막에 넣은 작업을 먼저 되돌리는 실행 취소가 응용이다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.4; 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.5; 4.1. Stack.mp4, 00:07:47~00:08:44

용어 42 시험 중간고사

LIFO

Last In, First Out의 약자로 마지막 삽입 원소가 먼저 제거되는 규칙이다. 큐의 FIFO와 구별한다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.4; 4.1. Stack.mp4, 00:02:23~00:03:20

용어 43 시험 중간고사

push

스택 top에 새 원소를 넣는 연산이다. 리스트 기반 구현에서는 내부 리스트의 append를 사용한다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.5; 4.1. Stack.mp4, 00:02:51~00:03:20

용어 44 시험 중간고사

pop

스택 top 원소를 제거해 반환하는 연산이다. 빈 스택에서는 오류가 발생하며 조회만 하는 top과 다르다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.5; 4.1. Stack.mp4, 00:09:44~00:10:43

용어 45 시험 중간고사

top

스택의 가장 최근 원소를 제거하지 않고 반환하는 조회이다. 호출 전후 크기는 동일하다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.5; 4.1. Stack.mp4, 00:18:25~00:18:55

용어 46 시험 중간고사

어댑터 패턴

기존 객체를 내부 필드로 감싸 원하는 다른 인터페이스를 제공하는 패턴이다. 리스트를 감싼 ArrayStack이 예이다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.8; 4.1. Stack.mp4, 00:16:00~00:18:04

용어 47 시험 중간고사

큐

뒤에서 삽입하고 앞에서 삭제하는 선입선출 ADT이다. 대기열의 도착 순서를 보존한다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.18; 4.2. Queue-Deque.mp4, 00:01:10~00:04:55

용어 48 시험 중간고사

FIFO

First In, First Out의 약자로 가장 먼저 들어온 원소가 먼저 제거되는 규칙이다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.18; 4.2. Queue-Deque.mp4, 00:01:10~00:02:16

용어 49 시험 중간고사

enqueue

큐의 뒤에 원소를 추가하는 연산이다. 순환 배열에서는 (front+size)%N 위치를 사용한다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.18; 4.2. Queue-Deque.mp4, 00:02:48~00:03:55

용어 50 시험 중간고사

dequeue

큐의 첫 원소를 제거해 반환하는 연산이다. 순환 배열은 셀을 비우고 front를 전진시키며 size를 감소시킨다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.18; 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.24; 4.2. Queue-Deque.mp4, 00:29:56~00:32:02

용어 51 시험 중간고사

순환 배열 큐

나머지 연산으로 배열 끝에서 처음으로 돌아오며 빈 셀을 재사용하는 큐이다. 물리 인덱스 순서와 논리적 FIFO 순서를 구별한다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.21; 4.2. Queue-Deque.mp4, 00:15:57~00:21:27

용어 52 시험 중간고사

덱

양 끝 모두에서 삽입과 삭제를 지원하는 ADT이다. 스택이나 큐의 연산을 제한된 형태로 구현할 수도 있다. 출처: 3. Chapter_6_-_Stacks__Queues__and_Deques.pdf, PDF p.29; 4.2. Queue-Deque.mp4, 00:39:30~00:41:30

Group 4

연결 리스트·위치·접근 빈도

16개 용어
용어 53 시험 중간고사

단일 연결 리스트

각 노드가 원소와 다음 노드 참조를 저장하는 선형 구조이다. 앞 삭제는 빠르지만 선행자를 모르는 뒤 삭제는 순회가 필요하다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.5; 5.1. Linked-List(1).mp4, 00:21:37~00:23:05

용어 54 시험 중간고사

head

연결 리스트의 첫 노드를 가리키는 참조이다. 비어 있으면 None이며 연결 스택에서는 top의 위치가 된다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.5; 5.1. Linked-List(1).mp4, 00:28:58~00:29:27

용어 55 시험 중간고사

tail

마지막 노드를 가리키는 참조이다. 단일 연결 큐에서 뒤 삽입을 상수 시간으로 지원하지만 이전 노드를 직접 알려 주지는 않는다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.5; 4. Chapter_7_-_Linked_List.pdf, PDF p.8; 5.1. Linked-List(1).mp4, 00:30:25~00:31:32

용어 56 시험 중간고사

이중 연결 리스트

노드마다 prev와 next를 두어 양쪽 이웃으로 이동하는 구조이다. 유효 노드를 이미 알면 삭제를 상수 시간에 수행할 수 있다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.23; 5.2. Linked-List(2).mp4, 00:40:57~00:43:06

용어 57 시험 중간고사

센티널

사용자 원소가 없는 경계용 노드이다. 빈 이중 연결 리스트에서는 header.next=trailer, trailer.prev=header로 연결한다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.23; 4. Chapter_7_-_Linked_List.pdf, PDF p.24; 4. Chapter_7_-_Linked_List.pdf, PDF p.28; 5.2. Linked-List(2).mp4, 00:44:02~00:47:43

용어 58 시험 중간고사

원형 연결 리스트

마지막 노드의 next가 첫 노드로 돌아가는 연결 구조이다. tail 하나로 head=tail.next를 얻을 수 있다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.18; 4. Chapter_7_-_Linked_List.pdf, PDF p.20; 5.2. Linked-List(2).mp4, 00:25:03~00:26:16

용어 59 시험 중간고사

LinkedStack

단일 연결 리스트의 head를 top으로 쓰는 스택 구현이다. push·pop·top은 재할당 없이 최악 O(1)이다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.11; 4. Chapter_7_-_Linked_List.pdf, PDF p.14; 5.2. Linked-List(2).mp4, 00:09:01~00:13:07

용어 60 시험 중간고사

LinkedQueue

head에서 제거하고 tail에 추가하는 단일 연결 큐이다. 마지막 원소 제거 시 head와 tail 모두 None으로 맞춘다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.15; 4. Chapter_7_-_Linked_List.pdf, PDF p.16; 5.2. Linked-List(2).mp4, 00:18:58~00:23:29

용어 61 시험 중간고사

Position

특정 컨테이너의 노드를 외부에 안전하게 표현하는 위치 객체이다. p.element()로 값에 접근하며 다른 곳의 삽입에도 지시 노드는 유지된다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.34; 4. Chapter_7_-_Linked_List.pdf, PDF p.37; 5.3. Linked-List(3).mp4, 00:12:05~00:13:02

용어 62 시험 중간고사

PositionalList

Position을 기준으로 앞뒤 이동·삽입·삭제·교체를 제공하는 ADT이다. 유효 위치가 주어지면 이중 연결 기반 갱신은 O(1)이다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.34; 4. Chapter_7_-_Linked_List.pdf, PDF p.35; 5.3. Linked-List(3).mp4, 00:01:35~00:02:41

용어 63 시험 중간고사

위치 검증

Position의 유형·소속 컨테이너·삭제 여부를 확인하고 내부 노드를 얻는 과정이다. 잘못된 리스트의 위치를 사용하지 못하게 한다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.38; 5.3. Linked-List(3).mp4, 00:20:59~00:21:31

용어 64 시험 중간고사

위치 무효화

노드 삭제로 기존 Position을 더 이상 사용할 수 없게 만드는 처리이다. 삭제 노드의 링크를 None으로 비우는 관례를 사용할 수 있다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.29; 4. Chapter_7_-_Linked_List.pdf, PDF p.38; 5.3. Linked-List(3).mp4, 00:12:05~00:12:33

용어 65 시험 중간고사

위치 기반 삽입 정렬

정렬된 접두 구간 뒤 pivot을 이전 위치들 사이에서 적절히 재삽입하는 정렬이다. 링크 갱신은 빨라도 위치 탐색 때문에 최악 Θ(n²)이다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.42; 5.3. Linked-List(3).mp4, 00:32:03~00:40:30

용어 66 시험 중간고사

빈도순 즐겨찾기

각 항목의 누적 접근 횟수를 세고 그 내림차순으로 유지하는 구조이다. 접근 시 횟수 증가에 따라 앞으로 재배치한다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.44; 4. Chapter_7_-_Linked_List.pdf, PDF p.45; 5.3. Linked-List(3).mp4, 00:42:01~00:44:59

용어 67 시험 중간고사

Move-to-Front

접근한 항목을 무조건 리스트 맨 앞으로 옮기는 휴리스틱이다. 최근성을 반영하므로 앞에서 k개가 누적 최빈 k개라는 보장은 없다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.48; 5.3. Linked-List(3).mp4, 00:46:27~00:47:27

용어 68 시험 중간고사

시간 지역성

참조 지역성 중 최근 사용한 항목을 가까운 미래에 다시 사용할 가능성이 높은 경향이다. MTF가 최근 접근 항목을 앞에 두는 근거가 되며 인접 주소를 사용하는 공간 지역성과 구별한다. 출처: 4. Chapter_7_-_Linked_List.pdf, PDF p.48; 5.3. Linked-List(3).mp4, 00:46:59~00:48:56

Group 5

트리·순회·수식 트리

22개 용어
용어 69 시험 중간고사

트리

루트를 기준으로 부모·자식의 계층 관계를 표현하는 비선형 자료구조이다. 루트가 아닌 노드는 유일한 부모를 가진다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.4; 6.1. Tree(1).mp4, 00:10:29~00:11:30

용어 70 시험 중간고사

루트

부모가 없는 특별한 노드이다. 비어 있지 않은 트리에서 하나 존재하며 깊이는 0이다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.5; 6.1. Tree(1).mp4, 00:11:30~00:12:32; 6.2. Tree(2).mp4, 00:02:01~00:02:32

용어 71 시험 중간고사

부모

특정 노드의 바로 위에 연결된 노드이다. 루트 외의 각 노드는 유일한 부모를 가진다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.4; 5. Chapter_8_-_Trees.pdf, PDF p.5; 6.1. Tree(1).mp4, 00:12:00~00:13:02

용어 72 시험 중간고사

형제

같은 직접 부모를 공유하는 노드들이다. 단지 깊이가 같다는 것만으로는 형제가 아니다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.5; 6.1. Tree(1).mp4, 00:19:42~00:20:45

용어 73 시험 중간고사

리프

자식이 없는 외부 노드이다. 간선 수 기준 높이는 0이며 수식 트리에서는 피연산자를 저장한다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.5; 5. Chapter_8_-_Trees.pdf, PDF p.10; 6.1. Tree(1).mp4, 00:20:45~00:21:51

용어 74 시험 중간고사

내부 노드

하나 이상의 자식을 가진 노드이다. 정이진 트리에서는 정확히 두 자식을 가지며 수식 트리에서는 연산자를 저장한다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.5; 6.1. Tree(1).mp4, 00:21:51~00:22:55

용어 75 시험 중간고사

깊이

루트에서 해당 노드까지의 간선 수이다. 부모의 깊이에1을 더하면 자식의 깊이가 된다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.9; 6.2. Tree(2).mp4, 00:01:32~00:03:01

용어 76 시험 중간고사

높이

해당 노드에서 가장 먼 하위 리프까지의 간선 수이다. 리프는0, 내부 노드는 자식 높이 최댓값+1이다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.10; 6.2. Tree(2).mp4, 00:15:58~00:17:41

용어 77 시험 중간고사

일반 트리

노드의 자식 수에 고정된2개 상한을 두지 않는 트리이다. 자식 참조들을 별도 컨테이너에 저장할 수 있다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.4; 5. Chapter_8_-_Trees.pdf, PDF p.31; 6.3. Tree(3).mp4, 00:54:33~00:56:35; 7.1. Tree(4).mp4, 00:03:01~00:03:33

용어 78 시험 중간고사

이진 트리

각 노드에 최대 두 자식을 허용하고 왼쪽·오른쪽을 구별하는 순서 있는 트리이다. 한쪽 자식만 존재할 수도 있다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.14; 5. Chapter_8_-_Trees.pdf, PDF p.15; 6.3. Tree(3).mp4, 00:00:32~00:03:11; 7.1. Tree(4).mp4, 00:25:56~00:26:52

용어 79 시험 중간고사

정이진 트리

교안의 proper/full binary tree로 모든 내부 노드가 정확히 두 자식을 가진다. 리프 수는 내부 노드 수+1이며 전체 노드 수는 홀수이다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.14; 5. Chapter_8_-_Trees.pdf, PDF p.19; 6.3. Tree(3).mp4, 00:25:48~00:26:55

용어 80 시험 중간고사

이진 탐색 트리

왼쪽 서브트리 값은 현재 값보다 작고 오른쪽은 큰 순서 규칙을 만족하는 이진 트리이다. 균형 보장이 없으면 탐색 최악은 선형이다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.40; 7.1. Tree(4).mp4, 00:36:34~00:39:07

용어 81 시험 중간고사

전위 순회

노드를 먼저 방문한 뒤 자식 서브트리를 순서대로 방문하는 순회이다. 목차 출력처럼 부모를 먼저 처리하는 용도에 맞는다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.34; 7.1. Tree(4).mp4, 00:04:03~00:04:34; 7.2. Tree(5).mp4, 00:02:00~00:03:26

용어 82 시험 중간고사

후위 순회

자식 서브트리를 모두 방문한 뒤 노드를 방문하는 순회이다. 디렉터리 총 공간이나 수식 값의 하위 결과 합산에 적합하다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.35; 5. Chapter_8_-_Trees.pdf, PDF p.49; 7.1. Tree(4).mp4, 00:11:28~00:12:33; 7.2. Tree(5).mp4, 00:17:57~00:20:26

용어 83 시험 중간고사

중위 순회

이진 트리에서 왼쪽 서브트리·현재 노드·오른쪽 서브트리 순으로 방문한다. 일반 트리에는 동일한 표준 정의가 없다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.39; 7.1. Tree(4).mp4, 00:25:56~00:27:50

용어 84 시험 중간고사

너비우선 순회

깊이가 낮은 레벨의 노드를 먼저 방문하는 순회이다. FIFO 큐로 발견한 노드들을 대기시키며 최악 보조 공간은 선형일 수 있다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.37; 7.1. Tree(4).mp4, 00:18:40~00:20:16

용어 85 시험 중간고사

연결 이진 트리

각 노드가 원소·부모·왼쪽·오른쪽 참조를 가진 구현이다. 유효 위치에서 국소적 링크 변경은 상수 시간이 가능하다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.22; 5. Chapter_8_-_Trees.pdf, PDF p.28; 6.3. Tree(3).mp4, 00:32:23~00:34:46

용어 86 시험 중간고사

배열 이진 트리

루트0, 왼쪽2i+1, 오른쪽2i+2의 레벨 번호로 셀을 배정하는 구현이다. 편향 트리는 빈 셀이 많아 공간이 커질 수 있다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.29; 5. Chapter_8_-_Trees.pdf, PDF p.30; 6.3. Tree(3).mp4, 00:46:41~00:48:50

용어 87 시험 중간고사

수식 트리

이항 연산자를 내부 노드, 수치 피연산자를 리프에 저장하는 이진 트리이다. 자식 값을 먼저 평가하는 후위 계산을 적용한다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.52; 5. Chapter_8_-_Trees.pdf, PDF p.55; 6.3. Tree(3).mp4, 00:07:03~00:07:33; 7.2. Tree(5).mp4, 00:22:56~00:23:58

용어 88 시험 중간고사

토큰화

수식 문자열을 연산자·괄호·수치 등 의미 있는 단위로 나누는 과정이다. 여러 자리 수12를 '1','2'로 쪼개지 않고 하나로 처리한다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.56

용어 89 시험 중간고사

트리 괄호 표현

노드 뒤 괄호 안에 자식 서브트리를 쉼표로 나열하는 표현이다. A(B,C)는 A의 두 자식 B와 C를 명확히 표시한다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.47; 5. Chapter_8_-_Trees.pdf, PDF p.48; 7.2. Tree(5).mp4, 00:11:52~00:14:33

용어 90 시험 중간고사

서브트리

선택한 노드를 루트로 하여 그 아래의 모든 후손을 포함하는 트리이다. 이진 트리는 좌우 서브트리를 재귀적으로 갖는다. 출처: 5. Chapter_8_-_Trees.pdf, PDF p.5; 5. Chapter_8_-_Trees.pdf, PDF p.15; 6.1. Tree(1).mp4, 00:25:41~00:27:47