Section 4

벌써 섹션4를 들어갔다....

코드스테이츠 과정을 밟은지 벌써 반이나 지나갔다.

앞으로 3개월 더 열심히 해보자..

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

이번 유닛에서는 자료구조에 대해서 공부하였다.

정처기 자격증을 취득할 때 한번 개념을 본것 말고는 생소한 개념이 많았던 유닛이었다.

게다가 생각했던것 보다 나에게 너무 어려웠다.

하지만 코딩테스트를 할 때 필수불가결한 유닛이기 때문에 꼭 알고 가자.

자료구조

자료구조란?

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

자료구조의 분류

너무 많은 자료구조...

이번 시간에는 자주 등장하는 Stack, Queue, Tree, Grap 를 다룰 것이다.

자료구조의 특징

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
따라서 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

stack

stack이란?

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.
마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조이다.

Stack의 구조

그림과 같이 스택은 가장 먼저 들어간 자동차는 가장 나중에 나올 수 있고, 가장 나중에 들어간 자동차가 가장 먼저 나올 수 있다는 것이다.

Stack의 특징

1. LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고 있다.

2. 데이터는 하나씩 넣고 뺄 수 있다.

Stack 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.

3. 하나의 입출력 방향을 가지고 있다.

Stack 자료구조는 데이터의 입출력 방향이 같다.

4. 저장되는 데이터는 유한하고 정적이어야 한다.

5. 스택의 크기는 제한되어 있다.

힙(heap)에 비해 스택의 크기가 제한되어 있으므로, 스택 오버플로(Stack Overflow) 같은 에러가 자주 발생한다.

Queue

큐(Queue)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.

Queue의 구조

그림과 같이 큐는 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.

Queue의 특징

1. FIFO (First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조를 가지고 있다.

2. 데이터는 하나씩 넣고 뺄 수 있다.

Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.

3. 두 개의 입출력 방향을 가지고 있다.

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다.

Tree

Tree란?

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다.
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.

Tree의 구조

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.

용어정리

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

이진 트리(Binary tree)

이진 트리(Binary tree)란?

이진 트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.

이진 트리는 그림과 같이 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

이진 트리 특징

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

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란?

이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리를 말한다.

이진탐색트리 특징

• 각 노드에 중복되지 않는 키(Key)가 있다.
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
• 좌우 서브트리도 모두 이진 탐색 트리여야 한다.

즉, 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

트리 순회(Tree Traversal)

트리 순회란?

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.

트리를 순회할 수 있는 세 가지 방법

• 전위 순회 (preorder traverse)

가장 먼저 방문할 노드는 루트이다.

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 다음, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.

• 중위 순회 (inorder traverse)

루트를 가운데에 두고 순회한다.

제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 나머지를 탐색한다.

• 후위 순회 (postorder traverse)

루트를 가장 마지막에 순회한다.

제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트에 간다.

그래프(Graph)

그래프란?

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

Graph의 표현 방식

• 인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기한다.
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.

• 인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

알아둬야 할 Graph 용어들

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge): 정점 간의 관계를 나타냄 (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻함
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻함
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현 가능하다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프이다.

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

너비 우선 탐색(Breadth-First Search)이란 너비를 우선적으로 탐색하는 방법이다.

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

깊이 우선 탐색(Depth-First Search)이란 깊이를 우선적으로 탐색하는 방법이다.