[정보처리기사 요약 2-7] 자료구조와 정렬 알고리즘 핵심 요약

본문에 오류가 있을 수 있음을 감안하고 봐주시길 바랍니다.
# 문제 풀이 중 오답노트 하면서 나온 내용을 정리한 것

 

자료 구조: 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계·처리 방법 등을 연구 분석하는 것을 말한다. 저장 공간의 효율성과 실행시간의 단축을 위해 사용한다.

자료 구조

• 배열(Array): 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합이다. 반복적인 데이터 처리 작업에 적합한 구조이며 정적인 자료 구조로 기억장소의 추가가 어렵다. 데이터 삭제 시 메모리 낭비가 발생할 수 있다.
• 연속 리스트(Contiguous List): 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다. 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며 삽입·삭제 시 자료의 이동이 필요하다.
• 연결 리스트(Linked List): 자료들을 임의의 기억공간에 기억시키되 자료 항목의 순서에 따라 노드의 포인터(현재 위치에서 다음 노드의 위치를 알려줌) 부분을 이용하여 서로 연결시킨 자료 구조이다. 기억 공간의 이용 효율이 좋지 않고(포인터를 위한 추가 공간이 필요) 접근 속도가 느리다. 연결이 끊어지면 다음 노드를 찾기 어렵다. 노드의 삽입이나 삭제가 쉽다. 체이닝(Chaining): 각 데이터를 해당 주소에 있는 연결 리스트에 삽입하여 해시 함수의 주소값 충돌 해결

연결 리스트

• 스택(Stack): 리스트의 한쪽 끝으로만 자료의 삽입·삭제 작업이 이루어지는 자료 구조이다. 후입선출(LIFO) 방식으로 자료를 처리한다. 기억 공간이 다 찬 상태로 삽입하면 오버플로우(Overflow)가 발생하고 기억 공간에 데이터가 없는 상태로 삭제하면 언더플로우(Underflow)가 발생한다. # 인터럽트의 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등

스택(Stack)

• 큐(Queue): 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조이다. 선입선출(FIFO) 방식으로 처리하며 시작을 표시하는 프런트(Front) 포인터와 끝을 표시하는 리어(Rear) 포인터가 있다. # 작업 스케줄링 등

큐(Queue)

• 덱(Deque): 리스트의 양쪽 끝에서 삽입과 삭제 작업이 모두 이루어지는 자료 구조이다. 스택과 큐의 장점을 복합한 형태로 입력이 한쪽에서만 발생하는 입력 제한 덱(Scroll)과 출력이 한쪽에서만 발생하는 출력 제한 덱(Shelf)이 있다.

덱(Deque)

• 그래프(Graph): 정점(Vertex)과 간선(Edge)의 두 집합으로 이루어지는 자료 구조이다. 사이클이 없는 그래프를 트리라고 한다. 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
  • 방향 그래프의 최대 간선의 수: n(n-1)
  • 무방향 그래프의 최대 간선의 수: n(n-1)/2

그래프

• 트리(Tree): 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다. 트리는 하나의 기억 공간을 노드(Node)라고 하며 노드와 노드를 연결하는 선을 링크(Link)라고 한다.
  • 근노드(Root Node): 트리의 맨 위에 있는 노드
  • 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수 # 보통은 최대 개수를 이야기함
  • 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
  • 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
  • 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
  • 레벨(Level): 근 노드의 Level을 1로 가정한 후 어떤 Level이 n이면 자식 노드는 n+1이다.
  • 깊이(Depth, Height): 트리에서 노드가 가질 수 있는 최대의 레벨
• 이진트리(Binary Tree): 차수(Degree)가 2 이하인 노드들로 구성된 트리, 즉, 자식이 둘 이하인 노드들로만 구성된 트리를 말한다.
  • 이진 트리(Binary Tree): 이진 탐색 트리(BST)
  • 균형 트리(Balanced Tree): AVL 트리, 2-3 트리, 레드-블랙 트리

이진 트리(Binary Tree)

 

트리의 운행법: 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다. 이진트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.

• Preorder 운행(RoLR): Root → Left → Right
• Inorder 운행(LRoR): Left → Root → Right
• Postorder 운행(LRRo): Left → Right → Root

 

수식의 표기법: 이진 트리로 만들어진 수식을 Inorder, Preorder, Postorder로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.

• 전위 표기법(PreFix): 연산자 → Left → Right, +AB
• 중위 표기법(InFix): Left → 연산자 → Right, A+B
• 후위 표기법(PostFix): Left → Right → 연산자, AB+

 

 

정렬 알고리즘

• 삽입 정렬(Insertion Sort): 가장 간단한 정렬 방식으로 이미 순서화된 파일에서 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식이다. 평균과 최악 모두 수행시간 복잡도는 O(n²)이다.

삽입 정렬(Insertion Sort)

• 선택 정렬(Selection Sort): n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고 나머지 (n-1) 개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다. 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

선택 정렬(Selection Sort)

• 버블 정렬(Bubble Sort): 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다. 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.

버블 정렬(Bubble Sort)

• 쉘 정렬(Shell Sort): 입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식이다. 삽입 정렬을 확장한 개념이다. 평균 수행 시간 복잡도는 O(n^1.5)이고, 최악 수행 시간 복잡도는 O(n²)이다. K(간격)는 홀수여야 한다(K = 개수//2, 짝수시 +1)

쉘 정렬(Shell Sort)

• 퀵 정렬(Quick Sort): 키를 기준으로 작은 값은 왼쪽 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식이다. 하나의 파일을 부분적으로 나누어가면서 정렬한다. 평균 수행 시간 복잡도는 O(nlog₂n)이고, 최악 수행 시간 복잡도는 O(n²)이다. 피벗(Pivot)은 랜덤한 선택값이며 피벗 기준으로 왼쪽에는 낮은 값을 오른쪽에는 큰 값으로 정렬한다. 최악의 경우 n(n-1)/2회를 비교 수행

퀵 정렬(Quick Sort)

• 힙 정렬(Heap Sort): 완전 이진 트리(Complete Binary Tree)를 이용한 정렬 방식이다. 구성된 완전 이진트리를 Heap Tree로 변환하며 정렬한다. 평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.

힙 정렬(Heap Sort)

• 2-Way 합병 정렬(Merge Sort): 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다. 평균과 최악 모두 시간 복잡도는 O(nlog₂n)이다.
• 기수 정렬(Radix Sort, Bucket Sort): Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식이다. 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬한다. 평균과 최악 모두 시간 복잡도는 O(dn)이다.

기수 정렬(Radix Sort)