2. 소프트웨어 개발(자료구조)

자료구조(Data Structure)

자료를 효율적으로 저장하기 위해 만든 구조

분류

선형: 데이터를 연속적으로 연결

• 리스트, 스택, 큐, 데크

비선형: 데이터를 비연속적으로 연결

• 그래프, 트리

리스트

선형리스트: 연속된 물리적 기억장소에 저장(배열)

• 가장 간편한 자료구조, 접근 구조가 빠름
• 삽입 삭제 시, 기존 자료의 이동이 필요

연결리스트: 노드의 포인터 부분으로 서로 연결시켜 저장(원형, 단순, 이중 연결리스트등)

• 삽입 삭제가 자유로움
• 연결을 위한 포인터 저장공간이 추가적으로 필요함

선형 자료구조

스택

한 방향으로만 자료를 넣고 꺼내는 LIFO(Last in First out)구조

• 위처럼 한 방향으로만 push(삽입), pop(삭제)을 통해 자료를 넣고 꺼낸다.
• 맨 위 포인터를 스택 포인터라 한다.

삽입

• 스택에 데이터가 가득차면 넣지않고 오버플로우
• 공간이 있으면 top크기를 1증가 시키고, 가리키는 곳에 데이터 삽입

삭제

• 스택에 데이터가 없으면 언더플로우
• 데이터가 있으면 데이터 삭제 후 top크기 1감소

사용처: 인터럽트, 함수 호출(재귀), 후위 표현 연산, 깊이 우선 탐색

큐

한방향에서 삽입, 다른 방향에서 삭제하는 FIFO(First in First out)구조

• Enqueue(삽입): Tail(Rear)에 데이터를 넣어줌
• Dequeue(삭제): Head(Front)에 처음 저장된 데이터부터 꺼냄.

데크(Deque; Double Ended Queue)

큐인데 양쪽에서 삽입, 삭제가 가능

• Push: 데이터를 데크에 넣음
• Pop: 데이터를 꺼냄

비선형구조

트리(Tree)

데이터를 계증화시킨 자료구조

• 사이클이 없음(특정 노드에서 출발해 노드 중복 없이 다시 시작했던 노드로 돌아오는 경로)
• 관계성이 계층 구조로 나타남

용어

• 루트노드(Root): 부모가 없는 최상위노드
• 단말노드(Leaf): 자식이 없는 노드
• 레벨(Level): 특정 노드까지 경로 길이
• 조상 노드(Ancestor): 특정 노드에서 루트에 이르는 경로상의 모든 노드
• 자식 노드(Child): 특정 노드에 연결된 다음 레벨의 노드
• 부모 노드(Parent): 특정 노드에 연결된 바로 이전 레벨의 노드
• 형제 노드(Sibiling): 같은 부모를 가진 노드
• 깊이(Depth): 루트노드에서 특정 노드에 도달하기 위한 간선의 수
• 노드의 차수(Degree): 특정 노드에 연결된 자식 노드의 수
• 트리의 차수: 노드의 차수 중 가장 큰 차수

트리의 순회

전위: Root → Left → Right 순으로 노드를 방문

중위: Left → Root → Right순으로 노드를 방문

후위: Left → Right → Root순으로 노드를 방문

이건 직접 해보면서 파악하면 좋다.

수식 Infix → Prefix, Postfix변환

기호가 가운데에 있는 infix를 앞쪽에 있는 Prefix로 바꾼다.

1. 계산 순서에 맞게 괄호를 부여한다.
2. $((a*(b+c))*d)$
3. 기호들을 괄호 내에서 가장 앞쪽으로 옮긴다.
4. $(*(*a(+bc))d)$
5. 괄호를 제거한다
6. $**a+bcd$

기호가 가운데에 있는 infix를 뒤쪽에 있는 Prefix로 바꾼다.

1. 계산 순서에 맞는 괄호 부여
2. $((a*(b+c))*d)$
3. 기호들을 괄호내에서 가장 뒤쪽으로 옮긴다.
4. $((a(bc+))d)$
5. 괄호를 제거한다
6. $abc+d$

트리 종류

이진 탐색 트리

• 차수가 2이하인 노드로만 구성된 트리
• 부모보다 작은 값은 왼쪽 부모보다 큰 값은 오른쪽으로 둔다.

AVL 트리(Adelson-Velsky and Landis Tree)

• 두 자식 서브트리의 높이가 최대 1만큼만 차이가 나도록 균형을 잡음
• 이진 트리의 한쪽으로만 치우칠 수 있는 문제를 제거

2-3트리

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

레드-블랙 트리

• 빨강 혹은 검정의 색상을 가져 색깔 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리

그래프

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

• 정점: 그래프의 노드, 간선: 노드를 연결하는 선

유형

방향그래프: 정점을 연결하는 선에 방향이 있는 그래프

• n개의 정점으로 구성된 방향그래프의 최대 간선 수는 n(n-1)

무방향 그래프: 정점을 연결하는 선에 방향이 없는 그래프

• n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)/2

용어

• 경로: 임의 정점에서 다른 정점으로 이르는 길
• 길이: 경로 상에 있는 간선수
• 단순 경로: 한 경로의 모든 간선이 다를 때의 경로
• 사이클: 동일 정점에서 시작과 끝이 이어지는 경로

탐색

깊이우선탐색(DFS): 최대한 깊이 내려간 후 더이상 깊이 갈 곳이 없으면 옆 노드로 이동

너비우선탐색(BFS): 최대한 넓게 이동한 후 더 갈 수 없으면 아래로 이동

• 한 노드에 직접 연결된 노드를 모두 방문 후 다음 노드로 방문