16.3 용어집¶
아래 표(16-1)에는 이 책에 나오는 주요 용어를 정리했다. 영어 문헌을 읽을 때 도움이 되므로 각 용어의 영어 명칭을 기억해 두기를 권장한다.
표 16-1 자료 구조와 알고리즘의 주요 용어
| English | 한국어 |
|---|---|
| algorithm | 알고리즘 |
| data structure | 자료 구조 |
| code | 코드 |
| file | 파일 |
| function | 함수 |
| method | 메서드 |
| variable | 변수 |
| asymptotic complexity analysis | 점근적 복잡도 분석 |
| time complexity | 시간 복잡도 |
| space complexity | 공간 복잡도 |
| loop | 반복문 |
| iteration | 반복 |
| recursion | 재귀 |
| tail recursion | 꼬리 재귀 |
| recursion tree | 재귀 트리 |
| big-\(O\) notation | 빅 \(O\) 표기법 |
| asymptotic upper bound | 점근적 상한 |
| sign-magnitude | 부호와 크기 표현 |
| 1’s complement | 1의 보수 |
| 2’s complement | 2의 보수 |
| array | 배열 |
| index | 인덱스 |
| linked list | 연결 리스트 |
| linked list node, list node | 연결 리스트 노드 |
| head node | 머리 노드 |
| tail node | 꼬리 노드 |
| list | 리스트 |
| dynamic array | 동적 배열 |
| hard disk | 하드 디스크 |
| random-access memory (RAM) | 메모리 |
| cache memory | 캐시 메모리 |
| cache miss | 캐시 미스 |
| cache hit rate | 캐시 적중률 |
| stack | 스택 |
| top of the stack | 스택의 맨 위 |
| bottom of the stack | 스택의 맨 아래 |
| queue | 큐 |
| double-ended queue | 덱 |
| front of the queue | 큐의 앞 |
| rear of the queue | 큐의 뒤 |
| hash table | 해시 테이블 |
| hash set | 해시 집합 |
| bucket | 버킷 |
| hash function | 해시 함수 |
| hash collision | 해시 충돌 |
| load factor | 적재율 |
| separate chaining | 체이닝 |
| open addressing | 개방 주소법 |
| linear probing | 선형 탐사 |
| lazy deletion | 지연 삭제 |
| binary tree | 이진 트리 |
| tree node | 트리 노드 |
| left-child node | 왼쪽 자식 노드 |
| right-child node | 오른쪽 자식 노드 |
| parent node | 부모 노드 |
| left subtree | 왼쪽 서브트리 |
| right subtree | 오른쪽 서브트리 |
| root node | 루트 노드 |
| leaf node | 리프 노드 |
| edge | 간선 |
| level | 레벨 |
| degree | 차수 |
| height | 높이 |
| depth | 깊이 |
| perfect binary tree | 포화 이진 트리 |
| complete binary tree | 완전 이진 트리 |
| full binary tree | 정 이진 트리 |
| balanced binary tree | 균형 이진 트리 |
| binary search tree | 이진 탐색 트리 |
| AVL tree | AVL 트리 |
| red-black tree | 레드-블랙 트리 |
| level-order traversal | 레벨 순서 순회 |
| breadth-first traversal | 너비 우선 순회 |
| depth-first traversal | 깊이 우선 순회 |
| pre-order traversal | 전위 순회 |
| in-order traversal | 중위 순회 |
| post-order traversal | 후위 순회 |
| balanced binary search tree | 균형 이진 탐색 트리 |
| balance factor | 균형 인수 |
| heap | 힙 |
| max heap | 최대 힙 |
| min heap | 최소 힙 |
| priority queue | 우선순위 큐 |
| heapify | 힙 재정렬 |
| top-\(k\) problem | Top-\(k\) 문제 |
| graph | 그래프 |
| vertex | 정점 |
| undirected graph | 무방향 그래프 |
| directed graph | 방향 그래프 |
| connected graph | 연결 그래프 |
| disconnected graph | 비연결 그래프 |
| weighted graph | 가중 그래프 |
| adjacency | 인접 |
| path | 경로 |
| in-degree | 진입 차수 |
| out-degree | 진출 차수 |
| adjacency matrix | 인접 행렬 |
| adjacency list | 인접 리스트 |
| breadth-first search | 너비 우선 탐색 |
| depth-first search | 깊이 우선 탐색 |
| binary search | 이진 탐색 |
| searching algorithm | 탐색 알고리즘 |
| sorting algorithm | 정렬 알고리즘 |
| selection sort | 선택 정렬 |
| bubble sort | 버블 정렬 |
| insertion sort | 삽입 정렬 |
| quick sort | 퀵 정렬 |
| merge sort | 병합 정렬 |
| heap sort | 힙 정렬 |
| bucket sort | 버킷 정렬 |
| counting sort | 계수 정렬 |
| radix sort | 기수 정렬 |
| divide and conquer | 분할 정복 |
| hanota problem | 하노이의 탑 문제 |
| backtracking algorithm | 백트래킹 알고리즘 |
| constraint | 제약 조건 |
| solution | 해 |
| state | 상태 |
| pruning | 가지치기 |
| permutations problem | 모든 순열 구하기 |
| subset-sum problem | 부분 집합의 합 문제 |
| \(n\)-queens problem | \(n\)-퀸 문제 |
| dynamic programming | 동적 계획법 |
| initial state | 초기 상태 |
| state-transition equation | 상태 전이 식 |
| knapsack problem | 배낭 문제 |
| edit distance problem | 편집 거리 문제 |
| greedy algorithm | 탐욕 알고리즘 |