소프트웨어 개발 - 자료구조

#자료 구조

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

자료 구조의 분류

■ 선형구조 (연속적 연결)

리스트, 스택, 큐, 데크

＠리스트

1. 선형 리스트

• 배열과 같이 연속되는 기억장소에 저장되는 리스트
• 가장 간편한 자료 구조
• 접근 구조가 빠름
• 자료의 삽입, 삭제 시 이동이 필요

2. 비선형 리스트

• 노드의 포인터 부분으로 서로 연결시킨 리스트
• 연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요
• 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

※ 노드: 데이터 저장부분과 포인터 부분으로 구성
※ 포인터: 메모리 공간 주소를 가리키는 변수

@스택

• LIFO (Last-in First-out)
• 한 방향으로만 자료를 넣고 꺼낼 수 있는 자료구조
• 가장 나중에 넣은 것을 먼저 꺼냄
• PUSH, POP을 사용해 자료를 넣고 꺼냄

If Top = n Then
  Overflow
Else {
  Top = Top + 1
  insert S(TOP)
}

스택에 데이터가 n개면 삽입할 공간이 없기 때문에 오버플로우
스택에 데이터가 n개 미만이면 스택 포인터 Top 값을 1 증가, 스택 포인터 Top이 가르키는 곳에 데이터 삽입

If Top = 0 Then
  Underflow
Else {
  remove S(Top)
  Top = Top - 1
}

스택에 데이터가 0개면 꺼낼 데이터가 없으므로 언더플로우
스택에 데이터가 1개 이상이라면 스택 포인터 Top이 가르키는 곳의 데이터 삭제, 스택 포인터 Top 값을 1 감소

@ 큐

• FIFO (First-in First-out)
• 먼저 들어온 데이터가 먼저 나감
• ENQUEUE, DEQUEUE를 사용해 자료를 넣고 꺼냄

@ 데크

• 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 구조
• 두 개의 포인터를 사용
• 스택과 큐의 구현이 가능
• PUSH, POP을 사용해 자료를 넣고 꺼냄

■ 비선형구조 (비연속적 연결)

트리, 그래프

@ 트리

• 트리: 데이터들을 계층화시킨 자료 구조
• 그래프의 특수한 형태
• 노드와 선분으로 되어 있고, 정점 사이에 사이클이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조
• 노드와 노드를 연결하는 링크로 구성

- 트리 용어

구분	설명
루트 노드	트리에서 부모가 없는 최상위 노드
단말 노드	트리에서 자식이 없는 최하위 노드
조상 노드	특정 노트에서 루트 노드까지의 경로상 노드
부모 노드	특정 노드에 연결된 이전 레벨의 노드
자식 노드	특정 노드에 연결된 다음 레벨의 노드
형제 노드	같은 부모를 가진 노드
깊이	루트 노드에서 특정 노드에 도달하기 위한 간선의 수
차수	특정 노드에 연결된 자식 노드의 수
레벨	루트 노드를 기준으로 특정 노드까지의 경로의 길이

- 트리 순회방법

1. 전위 순회

• 루트 → Left → Right

2. 중위 순회

• Left → 루트 → Right

3. 하위 순회

• Left → Right → 루트

※트리 순회 순서 구하는 TIP, 루트 노드를 기준으로 트리를 계속 나누기

- 트리 종류

◆ 이진 탐색 트리

• 차수가 2이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리
• 부모 노드보다 작은 값은 왼쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성됨
• 검색 효율이 나쁨 (균형을 맞춰주지 않음)

◆ AVL 트리

• 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리

◆ 2-3 트리

• 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리
• AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 줄인 트리

◆ 레드-블랙 트리

• 각 노드는 빨강 또는 검정의 색상을 가지고 잇으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리

@ 그래프

노드와 노드를 연결하는 간선을 하나로 모아 높은 자료 구조

@방향 그래프

• 정점을 연결하는 선에 방향이 있는 그래프
• 최대 간선 수 n(n - 1)

@무방향 그래프

• 정점을 연결하는 선에 방향이 없는 그래프
• 최대 간선 수 n(n - 1) / 2

수식 infix Prefix, Postfix로 변환하기

@Prefix

1. 계산 순서에 맞게 괄호를 친다.
2. 기호들을 괄호 안에서 가장 앞쪽으로 옮긴다
3. 괄호를 제거한다

<!-- 문제 -->
a * (b + c) * d

<!-- 1. 계산 순서에 맞게 괄호를 친다 -->
((a * (b + c)) * d)

2. 기호들을 괄호 안에서 가장 앞쪽으로 옮긴다
(* (* a (+ b c)) d)

<!-- 3. 괄호를 제거한다 -->
** a + b c d

@Postfix로

1. 계산 순서에 맞게 괄호를 친다.
2. 기호들을 괄호 안에서 가장 뒤쪽으로 옮긴다
3. 괄호를 제거한다

<!-- 문제 -->
a * (b + c) * d

<!-- 1. 계산 순서에 맞게 괄호를 친다 -->
((a * (b + c)) * d)

2. 기호들을 괄호 안에서 가장 뒤쪽으로 옮긴다
( ( a (b c + ) * ) d *)

<!-- 3. 괄호를 제거한다 -->
 a b c + * d *