자료구조 분류
| 구분 | 자료구조 |
|---|---|
| 선형 구조 | 리스트, 스택, 큐, 데크 |
| 비선형 구조 | 트리, 그래프 |
외우기:
선형 = 한 줄
비선형 = 가지치기/연결 복잡
선형 자료구조
| 자료구조 | 의미 | 특징 |
|---|---|---|
| 리스트 | 순서대로 저장 | 일반적인 목록 |
| 스택 | 한쪽에서 삽입/삭제 | 후입선출 |
| 큐 | 뒤로 넣고 앞으로 뺌 | 선입선출 |
| 데크 | 양쪽 삽입/삭제 가능 | Double Ended Queue |
외우기:
스택 = LIFO = 나중에 들어온 게 먼저
큐 = FIFO = 먼저 들어온 게 먼저
데크 = 양쪽 가능
비선형 자료구조
| 자료구조 | 의미 |
|---|---|
| 트리 | 부모-자식 계층 구조 |
| 그래프 | 정점과 간선으로 연결된 구조 |
트리 용어
| 용어 | 의미 |
|---|---|
| 루트 | 가장 위 노드 |
| 노드 | 자료가 들어가는 점 |
| 부모 노드 | 위에 연결된 노드 |
| 자식 노드 | 아래에 연결된 노드 |
| 단말 노드 | 자식이 없는 노드 |
| 차수 | 자식 노드 수 |
외우기:
트리 = 루트에서 시작하는 계층 구조
힙 Heap
| 키워드 | 정리 |
|---|---|
| 힙 | 완전 이진 트리 기반 자료구조 |
| 최대 힙 | 부모가 자식보다 큼 |
| 최소 힙 | 부모가 자식보다 작음 |
배열에서 자식 위치
| 구분 | 공식 |
|---|---|
| 왼쪽 자식 | 2i |
| 오른쪽 자식 | 2i + 1 |
| 부모 | i / 2 |
외우기:
힙 자식 = 왼쪽 2i, 오른쪽 2i+1
레코드 / 필드
| 개념 | 의미 |
|---|---|
| 필드 | 하나의 항목, 열 |
| 레코드 | 관련 있는 필드들의 묶음, 행 |
| 파일 | 레코드들의 모음 |
예시:
| 학번 | 이름 | 점수 |
|---|---|---|
| 1 | 철수 | 90 |
학번/이름/점수 = 필드
한 줄 전체 = 레코드
중위식 / 후위식
| 구분 | 의미 | 예시 |
|---|---|---|
| 중위식 | 연산자가 가운데 | A + B |
| 후위식 | 연산자가 뒤 | AB+ |
| 전위식 | 연산자가 앞 | +AB |
후위식 변환 기본
| 중위식 | 후위식 |
|---|---|
A + B | AB+ |
A * B | AB* |
(A + B) * C | AB+C* |
A / B * (C + D) + E | AB/CD+*E+ |
외우기:
중위식 = 사람 방식
후위식 = 연산자를 뒤로
통신 회선 수
| 상황 | 공식 |
|---|---|
| n개 지점이 서로 직접 연결 | n(n-1)/2 |
예시
| 지점 수 | 회선 수 |
|---|---|
| 7개 | 21개 |
| 8개 | 28개 |
| 10개 | 45개 |
외우기:
서로 연결 = n(n-1)/2
그래프 간선 수
| 구분 | 공식 | 예시: 정점 5개 |
|---|---|---|
| 무방향 그래프 | n(n-1)/2 | 10개 |
| 방향 그래프 | n(n-1) | 20개 |
외우기:
무방향 = 나누기 2
방향 = 나누기 안 함