[정보처리기사] 2과목 소프트웨어 개발 - 데이터 입출력 구현

📌 논리 데이터 저장소 확인

자료구조(Data Structure)

자료구조란, 데이터를 효율적으로 저장하기 위한 방법론을 말합니다.

최적의 성능을 보장하기 위해 고안된 것이죠!

 

자료구조는 크게 아래 2가지로 분류할 수 있습니다.

• 선형 구조 : 리스트, 스택(Stack), 큐(Queue), 데크(Deque)
• 비선형 구조 : 트리, 그래프

그럼 각 데이터 구조에 대해 한번 살펴볼까요?

 

리스트

• 데이터를 순차적으로 저장하는 데이터 구조
• 선형 리스트 : 메모리의 연속된 공간에 데이터를 순서대로 저장
• 연결 리스트 : 각 요소가 데이터와 다음 요소에 대한 포인터를 포함해 저장

스택(Stack)

• 입출력이 한쪽 끝으로만 제한된 순서가 있는 리스트
• push, pop 연산으로 데이터를 넣고 꺼냄
• Last In First Out (LIFO)
• 더 이상 삭제할 데이터가 없는 상태에서 삭제하면 언더플로(underflow) 발생

큐(Queue)

• 한쪽 끝에서 삽입(Enqueue) 작업, 반대쪽 끝에서 삭제(Dequeue) 작업이 이뤄짐
• First In First Out (FIFO)

데크(Deque)

• 양방향에서 입출력이 가능
• 2개의 포인터를 이용하여 데크의 양쪽 끝 모두에서 삽입 삭제가 가능

그래프(Graph)

• 정점(Node)와 간선(Edge)으로 구성
• 간선에 방향이 있냐 없냐에 따라 방향 그래프와 무방향 그래프로 구분
  • 정점이 n개인 방향 그래프의 최대 간선 수 : n(n-1)
  • 정점이 n개인 무방향 그래프의 최대 간선 수 : n(n-1)/2

트리(Tree)

• 그래프의 특수한 형태로, 노드(node)와 선분(branch)으로 구성
• 정점 사이에 사이클이 없으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조

트리의 차수 계산법 : 특정 노드에 연결된 자식 노드의 수 중 max

위 트리의 차수는 3

트리의 전위, 중위, 후위 순회 시 운행 결과

• 전위 순회(Preorder Traversal) : 루트 - 왼쪽 - 오른쪽
  ex) A - B - D - E - C - F - G

• 중위 순회(In-order Traversal) : 왼쪽 - 루트 -  오른쪽
  ex) D - B - E - A - F - C - G

• 후위 순회(Preorder Traversal) : 왼쪽 - 오른쪽 - 루트
  ex) D - E - B - F - G - C - A

트리의 종류

• 이진 탐색 트리 (Binary Search Tree, BST)
  • 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큰 트리 (오른쪽으로 갈 수록 값이 커짐)
  • 최악의 경우 검색 효율이 가장 나쁜 트리
• AVL 트리
  • 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하로 유지되는 트리
• 레드-블랙 트리
  • 노드가 빨간색 또는 검정색을 가지고 있고, 특정 규칙에 따라 트리의 균형을 유지하는 트리

탐색 방식에 따른 운행 결과

• 깊이 우선 탐색(DFS)
  • 최대한 깊이 내려간 후 옆으로 이동해 다른 경로를 탐색
  • A - B - D - E - G - F - C
• 너비 우선 탐색(BFS)
  • 계속 옆으로 이동하며 더 이상 탐색할 수 없을 때 아래로 이동
  • A - B - C - D - E - F - G