티스토리 뷰
* 자료구조의 분류
선형 구조: 리스트, 스택, 큐, Deque
비선형 구조: 트리, 그래프
* 선형 자료 구조
- List: 흔히 말하는 배열. 메모리에 연속적으로 저장
- Linked List: 연속적인 공간이 없어도 되고 삽입, 삭제가 용이하지만 포인터를 위한 추가 공간 필요
- Stack: 후입선출 (LIFO). 인터럽트 처리, 수식 계산, 서브루틴의 복귀 번지 저장, 0-주소 저장 방식 등에 이용
- Queue: 선입선출 (FIFO). OS의 스케줄링 등에서 이용
- Deque: 리스트의 양쪽 끝에서 삽입, 삭제가 가능. 스택과 큐의 복합 형태. '데크' 라고 써 있는데 자꾸 디큐라고 읽고싶어진다.
* 비선형 자료 구조
- 트리
그래프의 특수한 형태라 할 수 있음. 사이클을 이루지 않는 그래프.
- 트리 관련 용어
> 노드: 트리의 기본 구성요소
> 루트 노드: 최상위에 있는 부모 없는 노드
> 단말 노드 / 잎 노드: 트리 제일 아래쪽에 있는 자식이 없는 노드
> 비단말 노드: 단말 노드가 아닌, 자식을 가지는 노드
> 레벨: 트리의 각 층의 번호
> 높이 / 깊이: 트리의 최대 레벨
> 차수: 노드가 가지고 있는 자식 노드의 수
> 서브트리: 루트 외의 다른 노드가 루트가 되는 또 다른 트리
> 조상, 자손, 형제 노드: 인간 가계도의 그것과 같음
- 이진 트리 (Binary Tree)
최대 차수가 2인 트리. 즉 모든 노드가 자식을 최대 2개까지만 갖는 트리
> 노드 개수가 n개이면 선의 개수는 n-1개
> 높이가 h인 이진 트리의 노드 개수는 최소 h개, 최대 2^h-1개
- 이진 트리의 종류
1) 정이진트리 (Full Binary Tree): 각 레벨에 노드가 꽉 차있는 이진 트리 (노드 2^h-1개)
2) 전이진트리 / 완전이진트리 (Complete Binary Tree): 최대 레벨 -1까지는 노드가 꽉 차있고 마지막 레벨에선 왼쪽부터 순서대로 채워져있는 이진 트리
3) 사향이진트리 (Skewed Binary Tree): 왼쪽/오른쪽 중 한쪽으로만 노드가 쭉 있는 이진 트리
- 이진 트리 순회 (Traversal)
1) 전위순회 (Preorder): Root -> Left -> Right. 루트노드를 제일 먼저 출력하고 왼쪽 먼저, 아래쪽으로 내려가면서 출력
2) 중위순회 (Inorder): Left -> Root -> Right. 왼쪽 아래 끝에서 올라오면서 출력하며 중간에 거치는 부모 노드를 오른쪽보다 먼저 출력
3) 후위순회 (Postorder): Left -> Right -> Root. 왼쪽 아래 끝에서 올라오면서 출력하는데 중간에 거치는 부모 노드보다 오른쪽을 먼저 출력
> 전위순회: A - B - C - D - E - F - G
> 중위순회: C - B - D - A - F - E - G
> 후위순회: C - D - B - F - G - E - A
- 수식 트리 (Expression Tree)
수식을 이진 트리 형태로 표현한 것, 프로그래밍 언어에서 내부적으로 이런 걸 이용해서 수식을 처리한다 (Parsing)
이걸 어떤 식으로 순회하느냐에 따라 다른 수식 표현이 가능
1) 전위 순회 -> Prefix Notation
ex) + * + a b c 7
2) 중위 순회 -> Infix Notation (실생활에서 통용되는 수식 표기법)
ex) a + b * c + 7
3) 후위 순회 -> Postfix Notation
ex) a b + c * 7 +
- 이진 탐색 트리 (Binary Search Tree)
> 이진 탐색: '순차적으로 정렬된 상태인' 자료가 있을 때 반으로 잘라서 입력값보다 큰지 작은지 비교하고, 크면 오른쪽으로 작으면 왼쪽으로 가는 걸 반복하는 탐색 방법 (쉽게 말해서 Up/Down 게임)
cf) 이진 탐색 이외에 선형 탐색 (Linear/Sequential Search), 피보나치 탐색, 블록 탐색 등의 개념이 문제로 나옴
> 이진 탐색을 트리를 이용해 구현한 것이 BST
> 이진 탐색 트리의 규칙
1) 왼쪽 자식 노드는 자신보다 작아야 함
2) 오른쪽 자식 노드는 자신보다 커야 함
3) 해당 노드의 하위 노드도 이진 탐색 트리임
4) 값이 중복되는 노드는 없음
> Complete에 가까운 트리일수록 효율성이 좋고 Skewed 트리인 경우에는 성능이 나빠짐 (이걸 극복하기 위한 개량된 자료구조도 존재한다: AVL Tree 등)
- 그래프
정점 (Vertex) 과 간선 (Edge) 으로 구성
> 인접 행렬 (Adjacency Matrix): 그래프를 프로그램에서 표현하기 위한 것으로 행렬, 즉 2차원 리스트. i에서 j로 가는 길이 있으면 Aij = 1, 없으면 0. 또는 Weight가 있는 그래프일 경우 1 대신 Weight 값.
* 정렬
- 정렬 알고리즘 선택시 고려사항
1) 데이터의 양
2) 초기 데이터의 배열 상태
3) key값들의 분포 상태
4) 사용 시스템의 특성
- 정렬 알고리즘의 종류
> 내부 정렬: 주기억장치에서 이루어지는 정렬.
버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 2-Way 병합 정렬, 힙 정렬
> 외부 정렬: 보조기억장치에서 이루어지는 정렬.
밸런스 병합 정렬, 캐스캐이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬
- 버블 정렬 (Bubble Sort)
앞에서부터 원소를 2개씩 묶어서 보면서, 앞 원소가 더 크면 위치를 바꾼다 (swap)
이를 끝까지 한번 수행하면 맨 뒷자리에는 제일 큰 숫자가 있다는게 보장되며 이를 하나의 pass라고 함.
맨 뒷자리를 빼고 나머지 숫자들을 가지고 다시 pass를 반복한다.
- 삽입 정렬 (Insertion Sort)
두번째 원소부터 하나씩 골라서, 자기 앞에 있는 숫자들을 쭉 보고 적절한 자리에 들어간다.
(자기 바로 앞 숫자부터 보고 앞으로 가면서 자기보다 크면 한 자리 뒤로 밀어냄)
- 선택 정렬 (Selection Sort)
배열 전체를 쭉 보고 최소값을 찾아서 맨 앞으로 뺀다.
맨 앞자리 빼고 나머지를 쭉 보고 최소값을 찾아서 2번째 자리로 뺀다... 이걸 반복한다.
- 퀵 정렬 (Quick Sort)
배열의 숫자들 중 중간값쯤 될만한 적당한 원소를 pivot으로 정한다.
맨 앞에 i, 맨 뒤에 j를 두고 중앙으로 좁혀오면서 i와 j를 비교해서 j가 작을 경우 자리를 바꾼다.
중앙까지 오게 되면 pivot이랑 자리를 바꾼다.
이러고 나면 pivot을 중심으로 좌측에는 pivot보다 작은 숫자들, 우측에는 pivot보다 큰 숫자들이 오게 됨.
좌/우측 부분배열에 대고 각각 퀵 정렬을 재귀적으로 수행한다.
- 병합 정렬 (Merge Sort)
배열을 중간 지점을 기준으로 자르는 걸 반복한다. 최소 단위 (1개) 까지 자르고 나면 다시 합치는데, 합칠 때 양쪽 배열에 각각 index를 두고 비교해서 작은 값 먼저 빼오도록 함. 이것도 재귀함수를 이용한다.
- 힙 정렬 (Heap Sort)
힙이란 Complete Binary Tree이면서 부모노드가 자식노드보다 값이 항상 크거나 (Max heap) 작다 (Min heap) 라는 특성을 만족시키는 트리를 의미.
Min heap을 구성한 다음 [루트 노드를 추출 -> 맨 마지막 리프 노드를 루트로 올림 -> Min heap이 성립하도록 트리 재구성] 을 반복하면 오름차순 정렬이 됨. (Max heap을 쓰면 내림차순)
* 해싱 (Hashing)
- '해시 함수' 를 이용해서 입력값을 고정된 길이의 (압축된) 데이터로 만들어버리는 것.
- 해시값의 범위는 입력값의 범위보다 작기 때문에 서로 다른 입력값이 같은 해시값으로 매핑되는 '충돌' (Collision) 이 발생할 수 있다.
- 해싱을 DB나 파일시스템에서 많이 이용하는데 이때 해시 테이블 (Hash Table) 이라는 용어가 나옴
- 해시 관련 용어들
> 레코드
> 슬롯
> 버킷
> 충돌
> 동의어 (Synonym)
> 오버플로우
- 해시 함수의 종류
1) 제산 (Division): 키값을 prime number로 나누고 그 나머지를 홈 주소로 취하는 방법.
2) 중간 제곱 (Mid-Square): 키값을 제곱하고 그 중간값을 주소로 계산.
3) 중첩 (Folding): 주어진 키를 여러 부분으로 나누고 각 부분을 더하거나 XOR해서 나온 결과를 주소로 취하는 방법.
4) 기수 변환 (Radix Conversion): 키값을 다른 진법으로 변환.
5) 계수 분석 (Digit Analysis): 키를 구성하는 자릿수들의 분포를 조사하는 방법.
- 해시 오버플로우 해결 방법
1) 개방 주소 방법: 충돌이 발생한 다음 버킷을 차례로 검색해서 빈 버킷을 찾으면 거기다가 데이터를 넣음.
2) 폐쇄 주소 방법: 포인터를 이용해 같은 해시함수값을 갖는 레코드들을 링크드리스트로 이어줌.
3) 재해싱: 충돌이 발생하면 해시 함수를 바꿔서 새로 계산한다.
* 인덱싱 방법
인덱스란 레코드에 빨리 접근할 수 있도록 도와주는 별도의 값으로 DB의 물리적 구조와 깊은 연관. 레코드의 삽입/삭제가 자주 발생하면 인덱스 개수를 줄이는 게 효율적이다.
1) B-Tree
BST의 문제점을 보완한 확장판 같은 것으로 하나의 노드 안에 여러 개의 값이 들어가며 서브트리도 여러 개 가질 수 있음. 모든 리프 노드가 같은 레벨에 존재 (완전 균형, Balanced)
2) B+ Tree
B-Tree의 단점인 탐색 시간이 오래 걸리고 데이터를 추가, 삭제할 때 연산 과정이 많이 필요하다는 점을 해결한 것으로, 내부 노드는 모두 키값 (index) 만을 가지고 있으며, 리프 노드만이 실제 값 (data) 을 가지고 있고 그 리프 노드들끼리 링크드 리스트로 이어져 있는 구조
3) 트라이 색인
키 탐색을 위해 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성. 가변 길이 키값을 효율적으로 표현 가능하며 삽입, 삭제시 노드의 분열, 병합이 발생하지 않는다.
- 파일 편성 방법
1) 순차 파일 (Sequential File)
물리적으로 연속된 위치에 입력 데이터를 순차적으로 기록. 처리속도가 빠르고 빈 공간을 만들지 않으므로 기억장치를 효율적으로 쓸 수 있지만 검색 속도는 느리다. 대화식 처리보다 일괄 처리에 적합.
2) 색인 순차 파일 (Indexed Sequential File)
데이터 지역과 데이터에 대한 포인터를 갖고 있는 인덱스 지역으로 나눠서 저장. 기억장치 공간 낭비 발생.
오버플로 영역이라는 것도 있는데 블록이 레코드로 꽉 찼을때 추가 블록을 할당받아 연결시키는 부분.
3) VSAM 파일 (Virtual Storage Access Method File)
색인 순차 파일의 업그레이드 버전으로 동적 인덱스 방법을 이용. 기본 (데이터) 영역과 오버플로우 영역이 구분되지 않는데 대신 제어 영역이란게 또 있음. 레코드를 삭제하면 그 공간을 재사용.
4) 직접 파일 (Direct File)
특정 레코드에 접근하기 위해 디스크의 물리적 주소로 변환가능한 해시함수를 사용.
속도가 빠르고 랜덤 액세스에 적합하나 기억장치 공간 효율은 떨어짐.
5) 역파일 (Inverted File)
파일이나 DB에서 레코드를 빨리 검색하기 위해 별도의 인덱스 파일을 만들어두고 인덱스 파일에 키 필드의 값, 그 키값을 가지는 레코드에 대한 포인터들이 저장됨. 검색 속도 빠르고 처리가 쉽다.
- 정적 vs 동적 인덱싱
> 정적 인덱싱: 레코드가 변하면 인덱스 내용도 변하지만 인덱스의 구조는 변하지 않음 (정적).
> 동적 인덱싱: 레코드가 삽입될때 삽입될 레코드를 위한 빈 공간을 미리 준비해 두는 방법. 레코드가 블록에 가득 차면 동적으로 분열된다.