[정보처리기사 실기] 자료구조와 정렬 정리

자격증 준비하면서 내가 이해하기 편하게, 다시 보기 좋게 정리하는 정보처리기사의 내용 (자격증 상세 내용은 아래)

http://www.q-net.or.kr/crf005.do?id=crf00505&gSite=Q&gId=

http://www.q-net.or.kr/crf005.do?gId=&gSite=Q&id=crf00505

자료구조와 정렬 부분을 정리한 내용

---

배열

• 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합
• 반복적인 데이터 처리 작업에 적합한 구조
• 데이터 삭제 시 기억장소에 빈 공간으로 남아 메모리의 낭비가 발생

연속 리스트

• 배열과 같이 연속되는 기억장소에 저장되는 자료 구조
• 중간에 데이터 삽입을 위해 연속된 빈 공간 필요
• 삽입, 삭제 시 자료의 이동 필요

연결 리스트

• 자료들의 임의의 기억공간에 노드의 포인터 부분을 이용하여 서로 연결시켜 기억시킨 자료 구조
• 연결을 위한 링크(포인터)가 필요하기 때문에 기억 공간의 이용 효율 나쁨
• 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어려움

스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제가 이루어지는 자료 구조
• 후입선출(LIFO) 방식으로 자료 처리
• 저장할 기억 공간이 없는 상태에서 데이터가 삽입(push)되면 오버플로우(Overflow) 발생
• 삭제할 데이터가 없는 상태에서 데이터를 삭제(pop)하면 언더플로우(underflow)가 발생

큐(Queue)

• 리스트의 한쪽에서 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
• 선입선출(FIFO) 방식으로 자료 처리
• 시작을 표시하는 프런트(Front)와 끝을 표시하는 리어(Rear) 포인터 존재

그래프(Graph)

• 정점과 간선의 두 집합으로 이루어진 자료 구조
• 사이클이 없는 그래프는 트리
• 간선의 방향성 유무에 따라 방향 그래프(최대 간선수 n(n-1)), 무방향 그래프로 구분(최대 간선수 n(n-1)/2))

트리(Tree)

• 정점(노드)과 선분(가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수형태
• 노드 : 트리의 기본 요소로 자료 항목과 다른 항목에 대한 가지를 합친 것
• 근 노드 : 트리의 맨 위에 있는 노드
• 차수(degree) : 각 노드에서 뻗어 나온 가지의 수
• 단말 노드(잎 노드) : 자식이 하나도 없는 노드 (차수 = 0)
• 비단말 노드 : 자식이 하나라도 있는 노드 (차수 > 0)
• 조상 노드 : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드
• 자식 노드 : 어떤 노드에 연결된 다음 레벨의 노드
• 부모 노드 : 어떤 노드에 연결된 이전 레벨의 노드
• 형제 노드 : 동일한 부모를 갖는 노드
• 레벨(Level) : 근 노드의 레벨을 1로 가정한 후, 어떤 레벨이 x면 자식 노드는 x+1
• 깊이 : 트리에서 노드가 가질 수 있는 최대 레벨
• 숲 : 여러 개의 트리가 모여 있는 것
• 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

이진트리

• 차수가 2 이하인 노드들로 구성된 트리
• 레벨 x에 대해 최대 노드의 수는 2^(x-1)
• 단말노드의 수가 a, 차수가 2인 노드의 수를 b라 하면 a= b+1

전위 순회(Preorder) 운행법

• 이진트리를 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드의 순서로 찾아가는 방법

순회 과정

• 전위 순회로 순차적으로 순회할 경우 탐색 순서는 0 → 1 → 3의 순서로 탐색
• 여기서 1의 왼쪽 서브트리에 2가 있으므로 0 → 1 → 2 → 3으로 탐색
• 노드 순서는 A → B → D → H → I → E → C → F → G

반응형

중위 순회(inorder traversal)

• 왼쪽 자식노드 → 부모 노드 → 오른쪽 자식 노드 순으로 방문

순회 과정

• 중위 순회로 순차적으로 순회할 경우 탐색 순서는 1 → 0 →3의 순서로 탐색
• 여기서 1의 왼쪽 서브트리에 2가 있으므로 2 → 1 → 0 → 3 →으로 탐색
• 노드 순서는 H → D → I → B → E → A → F → C → G

후위 순회(postorder traversal)

• 왼쪽 자식노드 → 오른쪽 자식 노드 → 부모 노드 순으로 방문

순회 과정

• 후위 순회로 순차적으로 순회할 경우 탐색 순서는 1 → 3 → 0
• 여기서 1의 왼쪽 서브트리에 2가 있으므로 2 → 1 → 3→ 0으로 탐색
• 노드 순서는 H → I → D → E → B → F → G → C → A

수식의 표기법

ex) X = A/B *(C+D) + E

• 전위 표기 방법
  1. 연산 우선순위에 따라 괄호를 묶는다. → (X = (((A/B)*(C+D))+E))
  2. 연산자를 해당 괄호의 앞으로 옮긴다. → =(X+(*(/(AB)+(CD))E))
  3. 괄호 제거 → =X+*/AB+CDE
• 후위 표기 방법
  1. 연산 우선순위에 따라 괄호를 묶는다. (X = (((A/B)*(C+D))+E))
  2. 연산자를 해당 괄호의 뒤로 옮긴다. → (X((AB)/(CD)+)*)+)=
  3. 괄호 제거 → XAB/CD+*E+=

삽입 정렬

• 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
• 평균과 최악 모두 수행 시간 복잡도 O(n²)
• ex ) 8, 5, 6, 2 4를 삽입 정렬로 정렬
  • 1회 → 5, 8, 6, 2, 4 (두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입)
  • 2회 → 5, 6, 8, 2, 4 (세 번째 값을 첫 번째 값과 비교하여 6을 8자리에 삽입)
  • 3회 → 2, 5, 6, 8, 4 (네 번째 값을 처음부터 비교하여 맨 처음에 삽입)
  • 4회 → 2, 4, 5, 6, 8 (다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입)

선택 정렬

• 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하는 정렬 방식
• 평균과 최악 모두 수행 시간 복잡도 O(n²)
• ex ) 8, 5, 6, 2 4를 선택 정렬로 정렬
  • 1회 → 2, 8, 6, 5, 4 (첫 번째 레코드와 뒤 레코드를 반복해서 비교 후, 최솟값을 첫 번째 레코드에 놓기 반복)
  • 2회 → 2, 4, 8, 6, 5 (두 번째 레코드와 뒤 레코드를 반복해서 비교 후, 최솟값을 두 번째 레코드에 놓기 반복)
  • 3회 → 2, 4, 5, 8, 6 (세 번째 레코드와 뒤 레코드를 반복해서 비교 후, 최솟값을 세 번째 레코드에 놓기 반복)
  • 4회 → 2, 4, 5, 6, 8 (네 번째 레코드와 뒤 레코드를 반복해서 비교 후, 최솟값을 네 번째 레코드에 놓기 반복)

버블 정렬

• 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬
• 평균과 최악 모두 수행 시간 복잡도 O(n²)
• ex ) 8, 5, 6, 2 4를 버블 정렬로 정렬
  • 1회 → 5, 6, 2, 4, 8 (첫 번째 레코드와 두 번째 레코드 비교, 두 번째 레코드와 세 번째 레코드 비교 ··· )
  • 2회 → 5, 2, 4, 6, 8
  • 3회 → 2, 4, 5, 6, 8
  • 4회 → 2, 4, 5, 6, 8

쉘 정렬

• 매개변수의 값으로 서브파일을 구성하고 각 서브 파일을 삽입 정렬 방식으로 순서 배열하는 정렬 방식
• 삽입 정렬을 확장한 개념
• 평균 수행 시간 복잡도는 O(n^1.5), 최악의 경우 O(n²)

퀵 정렬

• 키(Pivot)를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 정렬 방식
• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가며 정렬
• 평균 수행 시간 복잡도는 O(nlog₂n) 최악의 경우 O(n²)

힙 정렬

• 전이진트리를 이용한 정렬 방식
• 구성된 전 이진트리를 힙 트리로 변환하여 정렬
• 평균과 최악 모두 수행 시간 복잡도 O(nlog₂n)

2-way 합병 정렬

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 평균과 최악 모두 수행 시간 복잡도 O(nlog₂n)

기수 정렬

• 큐(Queue)를 이용하여 자릿수(Digit) 별로 정렬하는 방식
• 평균과 최악 모두 수행 시간 복잡도 O(dn)

---

뒤로 이어지는 내용

https://edder773.tistory.com/183

[정보처리기사 실기] 통합 구현 정리