소프트웨어 개발(1)

자료 구조의 분류

• 선형 구조 : 배열, 선형 리스트, 스택, 큐, 데크
• 비선형 구조 : 트리, 그래프

스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리한다.

스택의 응용 분야

• 인터럽트의 처리
• 수식 계산 및 수식 표기법
• 서브루틴 호출 및 복귀 주소 저장

스택의 삽입(Push)과 삭제(Pop)

• PUSH : 스택에 자료를 입력하는 명령
• POP : 스택에서 자료를 출력하는 명령
• 순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력하였다가 B, C, D, A 순서로 출력하는 과정을 나열하시오.

​

방향/무방향 그래프의 최대 간선 수

• 무방향 그래프의 최대 간선 수 : n(n-1)/2
• 방향 그래프의 최대 간선 수 : n(n-1)

트리(Tree)

정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.

 

 

• 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수
  
  • 예) A = 3, B = 2, C = 1, D = 3
• 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드
  • 예) K, L, F, G, M, I, J

이진 트리의 운행법

다음 트리를 Inorder, Preorder, Postorder 방법으로 운행했을 때 각 노드를 방문한 순서는?

• Preorder 운행법의 방문 순서
  1. Preorder는 Root → Left → Right이므로 A13이 된다.
  2. 1은 B2E이므로 AB2E3이 된다.
  3. 2는 DHI이므로 ABDHIE3이 된다.
  4. 3은 CFG이므로 ABDHIECFG가 된다.

              💡방문 순서 : ABDHIECFG

• Inorder 운행법의 방문 순서
  
  1. Inorder는 Left → Root → Right이므로 1A3이 된다.
  2. 1은 2BE이므로 2BEA3이 된다.
  3. 2는 HDI이므로 HDIBEA3이 된다.
  4. 3은 FCG이므로 HDIBEAFCG가 된다.

              💡방문 순서 : HDIBEAFCG

• Postorder의 방문 순서
  1. Postorder는 Left → Right → Root이므로 13A가 된다.
  2. 1은 2EB이므로 2EB3A가 된다.
  3. 2는 HID이므로 HIDEB3A가 된다.
  4. 3은 FGC이므로 HIDEBFGCA가 된다.

              💡방문 순서 : HIDEBFGCA