[컴퓨터] 자료구조 키워드

 

 

1. 데이터

1. 저장 방식

1) 선형 구조 (1:1)

- 배열: 저장, 검색

- 연결리스트: 삽입, 삭제

- 스택: LIFO

- 큐: FIFO

 

2) 비선형 구조

- 트리: 1:n, 계층적

- 그래프: n:m, 순환적

 

 

2. 정렬

1) 값의 비교 후

- 버블, 선택, 삽입

- 퀵, 2-way merge, 합

 

2) 비교X

- 기수

 

 

3. 탐색

1) 순차

- 정렬X

 

2) 이진

- 정렬O, 배열 저장

 

3) 이진 탐색

- 정렬X, 탐색 효율적

 

4) 탐색 구조

- B-트리

- AVL

 

5) 해싱

- 주소 계산

 

 

 

2. 배열

: 공통된 성질을 갖는 데이터 집합

- 인덱스에 따라 직접 접근

 

1. 2차원 배열

1) 행 우선

- COBOL, C, PASCAL, ...

 

2) 열 우선

- FORTRAN, ...

 

vs. 구조체

: 타입이 다른 데이터를 묶는 방법

- 사용자 정의 데이터

- struct

- 자기 참조 구조체: 연결리스트, 트리, ... (생성 코드O)

 

 

 

3. 연결리스트

1. 포인터

- 포인터 변수: 다른 변수의 주소O

- &변수: 변수의 주소

- *: 포인터 변수가 가리키는 메로리 내용

 

 

2. 메모리 할당

1) 정적

- 미리 정해진 크기

 

2) 동적

- void *malloc(int size): 할당

- void free(): 반납

 

 

3. 연결리스트

: 선형 구조, 포인터만큼 기억공간 낭비 발생

 

1) 종류

- 단순, 원형, 이중

 

 

 

4. 스택

1. 특성

- LIFO: 모든 작업은 최근 위치에 국한

- 작업: 삽입(push), 삭제(pop)

- 시간 복잡도: O(1)

- Top(: 스택 포인터)로 최근 입력 데이터 위치

 

 

2. 삽입, 삭제

- 삽입: void push (element item)

- 삭제: element pop()

 

 

3. 응용

- 복귀 주소 관리 (서브루틴 호출, 인터럽트)

- 순환

- 연산 표기식: 전위, 후위, 중위...

- 이진트리 순회

(전위 +AB, 중위 A+B, 후위 AB+)

- 퀵 정렬

- 깊이 우선 탐색

 

 

 

5. 큐

1. 특성

- FIFO: 먼저 입력값 출력, 입력은 뒤쪽

- 작업: 삽입(push), 삭제(pop)

- 시간 복잡도: O(1)

 

 

2. 순차큐

- 삽입: void addq(element item)

- 삭제: element deleteq()

 

 

3. 원형큐

- 삽입

- 삭제

 

 

4. 응용

- 작업 스케줄링

- 너비 우선 탐색

- level 순회

- 스풀링

 

 

 

6. 트리

1. 정의

- 계층적 구조

- 근 노드, 가지

- 사이클X, 연결 그래프

 

2. 용어

- 근 (root)

- 단말 노드 (terminal)

- 비단말 노드 (non-terminal)

- A의 차수 (degree)

- 트리의 차수

- 높이, 깊이 (height, depth)

 

 

3. 이진 트리 종류

- 포화 이진트리 (배열로 표현)

- 완전 이진트리 (배열로 표현)

- 사향 이진트리 (연결리스트로 표현)

 

 

4. 순회

- 전위: 루트 - L - R

- 중위: L - 루트 - R

- 후위: L - R - 루트

- 레벨

 

 

 

7. 그래프

1. 무방향 그래프

- 순서X

- 최대 간선: n(n-1) / 2개

 

 

2. 방향 그래프

- 최대 간선: n(n-1)

 

 

3. 순회

1) 깊이 우선

- 스택

- Backtracking

 

2) 너비 우선

- 큐

 

 

 

8. 최소 비용 신장트리 (MST)

: 모든 간선의 길이 합이 최소인 것

- 신장 트리의 간선 수: n-1개

 

1. 종류

1) 크루스컬

- 가중치 기준 오름차순 정렬

- 간선: n-1

 

2) 프림

- 시작 정점 기준 인접 정점 중 최소 간선

- 간선: n-1

 

 

* AOE 네트워크

- 프로젝트를 완료하는 최소 시간

 

 

 

9. 정렬

1. 버블 정렬

- i키와 (i+1) 키 비교

 

 

2. 선택 정렬

- 최소값을 선택해서 첫 레코드와 교환

 

 

3. 삽입 정렬

- 두 번째 레코드부터 순서에 맞는 위치

 

 

4. 퀵 정렬

- 평균 수행 시간 짧음

- 정렬된 입력 최악

 

 

5. 힙 정렬

- 완전 이진트리

- 힙 트리의 삭제 동작 반복

 

 

6. 2-way merge 정렬

- 2개의 정렬된 파일 병합

 

 

7. 기수 정렬

- 분배에 의한 정렬

- 고속 처리

- 공간 복잡도 증가

 

 

 

10. 탐색

1. 순차 탐색

- 차례로 k와 비교

- 정렬X

 

 

2. 이진 탐색

- 정렬O, 고정 데이터

- 한 번 비교로 범위 반이 줄어듦

 

 

3. 이진 탐색 트리

- AVL 트리: 균형

- m차 B-트리: 최소 2개의 자식, 최대 m개 자노드

 

 

4. 해싱

1) 절차

- 키

→ 해시함수 → 해시주소 → 해시

 

2) 용어

- 버켓, 해시표, 해시함수, 해시주소, 충돌, 오버플로, 동의어

 

3) 오버플로우 해결

- 개방 주소법: 선형 조사법, 이차 조사법, 이중 해싱

- 폐쇄 주소법: 체이닝(연결리스트)