필기 - 2. 소프트웨어 개발_ch1. 데이터 입출력 구현

1. 논리 데이터 저장소 확인

(1) 자료 구조

1️⃣ 자료 구조의 개념

• 자료 구조는 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조

2️⃣ 자료 구조의 분류

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료 구조	트리, 그래프

3️⃣ 선형 구조

① 리스트

• 선형 리스트와 연결 리스트가 존재

② 스택

• LIFO 형식

PUSH	삽입 연산
POP	삭제 연산

 

③ 큐

• 한쪽에서 삽입, 반대쪽에서는 삭제
• FIFO 형식
• Head(삭제에서 가장 가까운 데이터) - Tail(입력에서 가장 가까운 데이터)

ENQUEUE	삽입 연산
DEQUEUE	삭제 연산

 

④ 데크

• 큐의 양쪽 끝에서 삽입, 삭제를 할 수 있음
• 큐 2개 중 1개를 뒤집은 느낌
• 데크를 이용해 큐, 스택 구현 가능

PUSH	삽입 연산
POP	삭제 연산

 

4️⃣ 비선형 구조

① 트리

• 트리는 데이터들을 계층화시킨 자료 구조
• 인덱스를 조작하는 방법
• 노드의 상한성이 없다
• 레벨 - 루트 노드를 기준으로 특정 노드까지의 경로 길이
• 깊이 - 루트 노드를 기준으로 특정 노드까지의 간선의 수
• 차수 - 자식 노드의 수

② 트리 순회방법

• 전위 순회 - CLR
• 중위 순회 - LCR
• 후위 순회 - LRC

③ 트리 종류

• 이진 탐색 트리
  • 자식이 둘 이하로 구성된 트리
  • 부모 노드보다 작은 값 L, 큰 값 R
• AVL 트리
  • 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 나도록 균형 잡힌 이진 탐색 트리
• 2-3 트리
  • 차수가 2 또는 3인 내부 노드를 갖는 탐색트리
• 레드-블랙 트리
  • 색깔에 따른 규칙이 있는 이진 탐색 트리

④ 그래프

• 개념
  • 그래프는 노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조
• 유형
  • 방향 그래프 - 최대 간선 수 n(n-1)
  • 무방향 그래프 - 최대 간선 수 n(n-1)/2
• 그래프 용어
  • 경로
  • 경로 길이
  • 단순 경로
  • 사이클
• 그래프 탐색 방법
  • 깊이 우선 탐색 DFS - 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
  • 넓이 우선 탐색 BFS - 최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동