자료구조 용어 단어장
정보처리기사·CS 자료구조 용어 21개의 뜻을 한 줄씩 정리했어요. 용어를 누르면 그림으로 단계별 설명을 보며 칠 수 있어요.
이 단어장 타자로 외우기 →타자 연습은 키보드가 있는 컴퓨터에서 해 보세요.
- 스택stack
나중에 넣은 것을 먼저 꺼내는(LIFO) 자료구조
- 큐queue
먼저 넣은 것을 먼저 꺼내는(FIFO) 자료구조
- 연결 리스트linked list
각 노드가 다음 노드를 가리키며 줄줄이 이어진 자료구조
- 이진 트리binary tree
각 노드가 자식을 최대 둘까지 가지는 트리
- 힙heap
부모가 항상 자식보다 작은(최소 힙) 완전 이진 트리
- 해시 테이블hash table
키를 해시 함수로 바꾼 위치에 값을 저장해 빠르게 찾는 자료구조
- 덱deque
양쪽 끝에서 넣고 뺄 수 있는 자료구조
- 우선순위 큐priority queue
들어온 순서와 상관없이 우선순위가 높은 것부터 꺼내는 자료구조
- 트라이trie
단어를 글자 단위로 나무처럼 저장해 앞부분으로 빨리 찾는 자료구조
- 그래프graph
정점과 그 정점들을 잇는 간선으로 이루어진 자료구조
- 배열array
같은 크기의 칸을 연속으로 두어 번호로 바로 접근하는 자료구조
- 이진 탐색 트리binary search tree
왼쪽에는 작은 값, 오른쪽에는 큰 값을 두어 빨리 찾는 이진 트리
- 유니온 파인드union find
원소들이 같은 집합인지 대표를 따라가 빠르게 확인하는 자료구조
- 원형 큐circular queue
배열의 끝과 처음을 이어 빈자리를 다시 쓰는 큐
- 선형 탐사linear probing
해시 충돌이 나면 다음 빈 칸을 차례로 찾아 넣는 방법
- AVL 트리avl tree
삽입과 삭제 때 회전으로 양쪽 높이 차이를 1 이하로 유지하는 이진 탐색 트리
- 인접 행렬adjacency matrix
정점끼리 연결 여부를 행과 열의 표로 나타낸 그래프 표현
- 이중 연결 리스트doubly linked list
각 노드가 다음과 이전 노드를 모두 가리키는 연결 리스트
- 전위 순회preorder traversal
자신을 먼저 방문하고 왼쪽, 오른쪽 서브트리 순서로 방문하는 트리 순회
- 중위 순회inorder traversal
왼쪽 서브트리, 자신, 오른쪽 서브트리 순서로 방문하는 트리 순회
- 후위 순회postorder traversal
왼쪽 서브트리, 오른쪽 서브트리를 먼저 방문하고 마지막에 자신을 방문하는 트리 순회