TIL 211007 - [자료구조/알고리즘] 자료구조 기초

Achievement Goals

• 자료구조가 무엇인지 설명할 수 있다.
• Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
  • 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
  • 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
  • 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
  • Binary Search Tree를 이해할 수 있다.
  • BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
• 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

자료구조 : 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

 

자료 구조의 종류와 구분

각 자료구조의 특징

각 자료구조를 사용하기에 적합한 상황

다른 자료구조와의 차이점 이해, 자료구조 내부 직접 구현

자료구조의 동작원리 이해

 

Chapter 1 - Stack / Queue

Stack

데이터를 순서대로 쌓는 자료 구조. LIFO(Last In First Out). 브라우저의 뒤로 가기와 앞으로 가기 기능에 사용

 

Queue

Stack과 반대되는 개념. FIFO(First In First Out). 먼저 들어간 데이터가 먼저 나온다.

컴퓨터 장치들 사이에 데이터를 주고 받을 때 각 장치 사이에 존재하는 속도의 차이나 시간 차이 극복위해

임시 기억 장치의 자료 구조로 Queue를 사용한다. 이것을 버퍼라고 한다.

 

Chapter 2- Graph / Tree / BST

(1) Graph

CS에서 언급하는 그래프는 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습

그래프에서 하나의 점을 정점(vertex)이라고 하고 선은 간선(edge)

검색엔진, SNS에서 사람들과의 관계, 네비게이션에서 사용하는 자료 구조

정점 사이에 간선을 추가 할 수 없는 경우 '관계가 없다'라고 표현

비가중치 그래프: 간선은 두 정점이 단순히 이어져 있다는 것만 알려줄 뿐 그외 정보는 포함하고 있지 않는 그래프

 

알아둬야 할 그래프 용어들

• 무(방)향그래프(undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프 입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 하지만 단방향(directed) 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프 입니다.

질문

• 위 네비게이션 예제에서 서울은 몇개의 진입차수와 몇개의 진출차수를 가지고 있나요?
• 네비게이션 대신 SNS에서 자료구조로 그래프를 이용한다면, 정점과 간선은 무엇이 될까요?
• SNS에서 어떤 관계일 경우 단방향 그래프가 생성될까요?
• 자기 루프와 사이클은 어떻게 다를까요?

인접행렬: 서로 다른 정점들이 인접한 상태인지를 표시한 행렬, 2차원 배열 형태 

인접 행렬은 언제 사용할까?

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
  • 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.

 

인접 리스트: 각 정점이 어떤 정점과 인접한지를 리스트 형태로 표현

리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있음

 

인접 리스트는 언제 사용할까?

• 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.

 

(2) Tree

하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 구조. 데이터가 바로 아래에 있는 하나 이상의 데이터 단방향으로 연결된 계층적 자료 구조.비선형 구조. 루트와 노드(부모 노드, 자식 노드)

 

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드

깊이: 루트로부터 하위 계층의 특정 노드까지의 층

레벨: 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현. 같은 레베에 나란히 있는 노드를 형제 노드라고 함

높이: 리프 노드를 기준으로 루트가지의 높이. 각 리프 노드의 높이는 0. 한 레벨씩 올라갈때마다 높이가 1씩 증가

 

(3) Binary Search Tree

자식 노드가 최대 2개인 노드들로 구성된 트리. 자식노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 구분

자료의 삽입, 삭제 방법에 따라 1) 정 이진 트리  2)포화 이진 트리  3)완전 이진 트리

 

종류	영어표기	설명
정 이진 트리	Full binary tree	각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특성

 

 

Chapter 3 - Graph, Tree Search Algorith

1. Tree traversal

 

2. BFS / DFS

그래프 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 탐색하는 것이 목적이다.

 

BFS(Breadth-First-Search; 너비 우선 탐색)

맹목적인 탐색방법의 하나로 시작 정점에서 가장 인접한 모든 정점들을 방문한다. 더는 탐색할 정점이 없을 때, 그 다음에 떨어져 있는 정점을 순서대로 방문한다.

 

DFS(Depth-First-Search; 깊이 우선 탐색)

하나의 경로를 끝까지 탐색 후 더 이상 탐색할 경로가 없다면 다음 경로로 넘어가 탐색한다.