2. 소프트웨어 개발 - 데이터 입출력 구현(자료 구조, 트리, 정렬)
36. 자료 구조
: 저장 공간의 효울성과 실행시간의 신속성을 위한 자료의 표현과 관련 연산
프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등의 연구 분석
- 어떠한 자료 구조를 이용해도 필요한 모든 연산을 처리할 수 있다
- 자료 구조에 따라 프로그램의 실행 시간이 달라진다
- 자료 구조의 분류
- 선형구조 (Linear Structure) : 자료를 구성하는 데이터가 1:1 관계로 연결되어 순차적으로 나열되는 형태의 자료 구조
- 배열(Array), 연결리스트(Linked List), 스택(Stack), Queue(큐)
- 비선형 구조 (Non-linear Structure) : 자료를 구성하는 데이터가 1 : N 또는 N : M 관계를 가지고 비선형적으로 구성되는 자료 구조
- 트리(Tree), 그래프(Graph)
1) 배열 (Array)
: 동일한 자료형의 데이터들이 같은 크기로 순서를 갖고 나열된 구조.
- 정적인 자료구조로 기억장소의 추가가 어렵다.
- 데이터 삭제 시 해당 데이터가 저장되어 있던 공간은 빈 공간으로 남아있어 메모리의 낭비가 발생한다
- index(첨자)를 이용해 각 데이터에 접근한다
- 반복적인 데이터 처리 작업에 적합하다
- 데이터마다 동일한 이름의 변수를 사용해 처리가 편하다
- 배열의 각 원소가 배열이 되면 데이터의 차원이 늘어나고 N차원 배열이라고 부른다
2) 선형 리스트 (Linear List)
: 일정한 순서에 의해 나열된 자료 구조
- 연속 리스트 (Contiguous List) : 배열을 이용하여 나타낸 리스트
- 연결 리스트 (Linked List) : 다음 데이터를 가리키는 포인터를 이용해 만든 리스트
1. 연속 리스트 (Contiguous List)
- 배열처럼 연속되는 기역장소에 저장되는 리스트 구조 -> 1의 밀도를 가져 기억장소 이용 효율이 높다
- 배열과 달리 빈 공간을 허용하지 않으므로 데이터의 삽입 및 삭제시 데이터의 이동이 필요하다
2. 연결 리스트 (Linked List)
: 자료를 임의의 기억공간에 저장하되, 데이터를 저장하는 노드의 포인터 부분을 연결시켜 순서를 만든 리스트 구조
- 노드의 삽입과 삭제 작업이 용이하다
- 기억공간이 연속적으로 놓여있지 않아도 저장이 가능하다
- 포인터를 저장할 링크부분이 필요하기 때문에 연속 리스트에 비해서 기억 공간의 이용 효율이 좋지 않다
- 한 데이터의 다음 데이터를 찾을 때 포인터를 이용하므로 접근 속도가 느리다
- 중간에 노드 간 연결이 끊어지면 찾기 힘들다
3) 스택 (Stack)
: 리스트의 한쪽 끝으로만 자료의 삽입과 삭제 작업이 이루어지는 자료 구조
- 후입선출 구조 (LIFO; Last In First Out) : 가장 나중에 삽입한 자료가 가장 먼저 삭제된다
- 용도 : 재귀 호출, 후위 표기법, 서브루틴 호출, 인터럽트 처리, 깊이 우선 탐색 등 왔던 길을 다시 되돌아가는 방식의 작업
- 가장 마지막으로 자료가 삽입된 공간을 가리키는 Top 포인터를 이용해 자료를 삽입, 삭제한다
- 스택에서의 자료 삽입 (Push)
- 스택의 Top 포인터를 1 증가시킨다.
- Top 포인터가 스택의 용량 한계를 넘었다면 Overflow가 발생한다
- 그렇지 않으면 Top 포인터에 위치에 자료를 저장한다
- 스택에서의 자료 삭제 (Pop)
- Top 포인터가 0이라면 삭제할 데이터가 없는 것이므로 Underflow가 발생한다
- 그렇지 않으면 Top 포인터가 가리키는 위치에서 item을 꺼내오고 Top 포인터를 1 감소시킨다.
4) 큐 (Queue)
: 리스트의 한 쪽에서는 삽입이, 다른 한 쪽에서는 삭제가 이루어지는 자료 구조
- 선입선출 구조 (FIFO; First In First Out) : 가장 먼저 삽입된 자료가 가장 먼저 삭제된다
- Front와 Back의 두가지 포인터를 사용한다
- Front : 가장 먼저 삽입된 자료를 가리키는 포인터. 삭제 작업에 이용된다
- Back : 가장 나중에 삽입된 자료를 가리키는 포인터. 삽입 작업에 이용된다
※ 데크 (Deque) : Front와 Back 양쪽에서 삽입과 삭제 작업이 모두 가능한 Queue 구조의 한 종류
5) 그래프 (Graph)
: 정점(Vertex)과 정점을 연결하는 간선(Edge)으로 이루어진 자료 구조
- 간선에 방향성이 있다면 방향 그래프, 방향성이 없다면 무방향 그래프가 된다
- 그래프의 용도 : 통신망, 교통망, 이항관계, 연립방정식, 화학 구조식, etc.
※ 트리 (Tree) : 사이클(한 정점에서 시작해 간선을 타고 다시 해당 정점으로 돌아올 수 있는 구조)가 없는 그래프
37. 트리 (Tree)
: 정점(또는 노드)와 간선(또는 가지)을 이용해 사이클이 없도록 구성한 그래프의 특수 형태
- 가족 계보, 조직도 등을 표현하는데 적합하다
- 이진 트리 (Binary Tree) : 모든 노드가 최대 2개까지의 자식노드를 가질 수 있도록 한 트리
- 트리의 구성 요소
- 노드 (Node) : 트리에서 하나의 자료를 저장하는 기억공간
- 가지 (Branch, 링크) : 노드와 노드를 연결하는 선
- 차수 (Degree) : 노드에서 뻗어나오는 가지의 수 / 트리의 차수 : 노드의 차수 들 중 가장 큰 수
- 레벨 (Level, 높이) : 노드가 연속적으로 연결되어 만들어지는 트리의 깊이
- 부모 노드 (Parent Node) : 어떤 노드와 연결된 상위 레벨의 노드
- 자식 노드 (Child Node) : 어떤 노드와 연결된 하위 레벨의 노드
- 형제 노드 (Sibling Node) : 동일한 부모 노드를 가진 자식 노드들의 모임
- 루트 노드 (Root Node) : 트리의 맨 위에 있어 부모 노드를 가지지 않는 노드. 최상위 노드
- 리프 노드 (Leaf Node, 단말 노드) : 자식 노드를 가지지 않는 노드
1) 운행법 (Traverse)
: 트리를 구성하는 모든 노드들을 한번씩 방문하는 방법
- 이진 트리에서의 운행법
- Preorder Traverse : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 운행
- Inorder Traverse : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 운행
- Postorder Traverse : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순으로 운행
옆의 이진 트리 구조에서의 Traverse 방법
- Preorder Traverse
A-B-D-H-I-E-C-F-J-G
- Inorder Traverse
H-D-I-B-E-A-F-J-C-G
- Postorder Traverse
H-I-D-E-B-J-F-G-C-A
38. 정렬
: 자료 구조에서 무작위로 배열된 데이터를 일정한 기준에 따라 순서대로 재배열하는 알고리즘
- 정렬된 데이터는 이진탐색을 위해 필수적이므로, 효율적인 정렬 알고리즘을 이용하는 것이 중요하다.
1) 삽입 정렬(Insertion Sort)
: 배열의 모든 요소를 앞에서부터 이미 정렬된 부분과 비교하여 알맞는 자리에 삽입하여 정렬을 완성하는 방식
- 평균 시간 복잡도 O(n²)
- 최대 시간 복잡도 O(n²)
2) 쉘 정렬 (Shell Sort)
: 전체 데이터를 특정 구간(매개변수) h 만큼 떨어져있는 값들로 부분을 만들고 각 부분에서 삽입 정렬 방식으로 순서를 배열하는 과정을 h를 줄여가며 반복하는 방식
- 쉘 정렬을 간단히 설명하는 영상
- 데이터가 부분적으로 정렬되어 있는 경우에 유리한 방식이다
- 평균 시간 복잡도 O(n^1.5)
- 최대 시간 복잡도 O(n²)
3) 선택 정렬 (Selection Sort)
: 전체 레코드 중에서 최솟값(또는 최댓값)을 찾아 첫번째 위치에 놓고 나머지 중에서 다시 최솟값(또는 최댓값)을 찾아 그 다음 위치에 놓는 것을 반복하여 정렬하는 방식
- 평균 시간 복잡도 O(n²)
- 최대 시간 복잡도 O(n²)
4) 버블 정렬 (Bubble Sort)
: 인접한 두 개의 데이터 값을 비교하여 크기에 따라 교환하는 것을 전체 데이터에 대해 반복하는 방식
- 평균 시간 복잡도 O(n²)
- 최대 시간 복잡도 O(n²)
5) 퀵 정렬 (Quick Sort)
: 전체 데이터 집합에서 임의로 키(주로 중앙값)를 선정하여 해당 키보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시키는 것을 집합의 크기를 줄여가며 반복하는 방식
▲ 위의 예시에선 키를 가장 앞의 값으로 잡았다.
- 정렬 방식 중에서 가장 빠른 방법
- 분할 정복 방식 (Divide and Conquer)
- 평균 시간 복잡도 O(n * log2 n)
- 최대 시간 복잡도 O(n²)
6) 힙 정렬 (Heap Sort)
: 데이터를 완전 이진 트리에 삽입하여 정렬하는 방식
※ 완전 이진 트리 (Complete Binary Tree) : 노드가 왼쪽부터 차례대로 채워져있는 이진트리
- 평균 시간 복잡도 O(n * log2 n)
- 최대 시간 복잡도 O(n * log2 n)
7) 합병 정렬 (Merge Sort)
: 전체 데이터를 가능한 작게 쪼갠 뒤에 각 부분을 정렬하고 합치는 과정을 반복하는 방식
- 평균 시간 복잡도 O(n * log2 n)
- 최대 시간 복잡도 O(n * log2 n)
8) 기수 정렬 (Radix Sort, Bucket Sort)
: 데이터를 자릿수(Digit) 별로 나누어 각 버킷에 분배하였다가 버킷 순서대로 데이터를 꺼내 정렬하는 방식
- 기수 정렬을 간단히 보여주는 영상
- 평균, 최대 시간 복잡도 O(dn) (d는 키의 자릿수)