자료구조/알고리즘 - 자료구조 기초(Stack, Queue, Graph, Tree, BST)

자료구조

학습 목표

* 자료구조란?

* Stack, Queue, Tree, Graph 자료 구조
- 알고리즘 문제에서 Stack, Queue 자료 구조를 배열로 흉내내기
- 각 자료구조의 개념과 구조 파악
- 알고리즘 문제에 맞는 자료구조 적용

* 트리 및 그래프의 탐색 기법 이해
- Binary Search Tree
- BFS 와 DFS의 개념과 알고리즘 적용

* 자료 구조를 활용한 알고리즘 문제 접근

 

자료 구조 소개

자료 구조란?

여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것
→ 필요에 따라 데이터의 특징을 잘 파악하여 체계적으로 정리하여 저장해 둬야 한다
→ 데이터를 효율적으로 다룰 수 있는 여러 방법들을 모아 “자료 구조” 라 한다

 

가장 많이 쓰이는 자료 구조
→ Stack, Queue, Tree, Graph

 

자료 구조는 특정한 상황에 놓인 문제를 해결하는데 특화
→ 많은 자료구조를 알아두면 알고리즘(코딩) 테스트와 같은 상황에서 적합한 자료구조를 이용해서
빠르게 문제 해결 가능

자료 구조 이해하기 로드맵

1. 각 자료구조가 가진 특징을 학습
2. 각 자료구조를 사용하기 적합한 상황을 이해
3. 다른 자료 구조와의 차이점을 이해하기 위해 자료구조의 내부를 직접 구현
4. 자료 구조를 구현하면서 해당 자료구조의 동작 원리 이해

이를 좀 더 구체화해서 생각해 보면

 

1) class 키워드를 이용해 자료 구조의 데이터 타입을 직접 정의. 이 과정에서 필요한 속성 ,메서드를 학습
→ 자료구조를 직접 구현해 보면서 알고리즘을 학습하는 과정

 

2) 자료 구조를 활용해 알고리즘 문제 풀기

문제에 적합한 자료구조를 파악하여 알맞은 자료구조를 사용
→ 필요한 자료구조를 클래스로 직접 정의해서 사용하기에는 비효율적
→ JavaScript 에서 제공하는 “배열”과 같은 데이터 타입을 이용하여 자료구조의 형태와 “유사”하게 구현하여(자료 구조를) 문제 해결 가능!

 

Stack & Queue

Stack

데이터를 순서대로 쌓는 구조(“스택이 쌓였다”를 생각!)

아래는 실생활의 예

다섯 대의 자동차가 순서대로 좁은 골목을 지나고 있습니다. 좁은 골목에 진입한 차량은 곧 맞이할 미래를 모르고 있지만, 이 골목의 끝은 막혀 있습니다. 첫 번째 자동차는 이 골목을 통과하기 위해 직진했고, 나머지 자동차도 앞 자동차의 꽁무니를 따라 직진했습니다. 그러나 첫 번째 차량이 막다른 길을 맞이했습니다. 마지막으로 들어온 다섯번 째 자동차가 먼저 후진하여 나와야 하는 상황이 되어버린 겁니다.

→ 자료 구조 스택의 특징을 보여줌

LIFO(Last In First Out) 또는 FILO(First In Last Out)의 특징

 

Stack의 실사용 예제

컴퓨터에서 “브라우저 뒤로 가기, 앞으로 가기” 기능

ex) 브라우저에서 자료구조 stack의 구현 원리

Prev Stack, Next Stack 이라는 2개의 Stack이 존재한다고 보자

1. 새로운 페이지에 접속 시, 현재 페이지를 Prev Stack에 보관(저장;쌓)
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관(저장)하고
Prev Stack에서 가장 나중에 쌓인 페이지를 꺼내 옴(현재 페이지로)
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동 시,
Next Stack에서 가장 마지막으로 쌓인 페이지를 꺼냄
4. 마지막으로 Prev Stack에 현재(였던) 페이지를 보관한다

 

Queue

“Queue를 기다린다”를 생각!
→ 줄을 서서 기다리다, 대기 행렬

 

FIFO(First In First Out) 또는 LILO(Last In Last Out)의 특징을 가짐

 

실 생활의 예로 살펴보면,

명절에는 고향으로 가기 위해 많은 자동차들이 고속도로를 지납니다. 고속도로에는 톨게이트가 있고, 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과합니다.

→ 그러므로, Queue의 경우 데이터가 입력된 순서대로 처리되어야 할 때 주로 사용!

 

Queue의 실사용 예제

컴퓨터에서 프린터로 여러 문서를 순서대로 출력하는 경우

1. 사용자가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업(임시 기억장치의) Queue에 들어감
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄

컴퓨터(출력버튼 누름) → (임시 기억 장치의) Queue에 하나씩 들어 옴 → Queue에 들어온 문서를 순서대로 인쇄 

위의 예시처럼 컴퓨터는 장치들 사이에서 데이터를 주고 받을 때, 장치 간 존재하는 속도나 시간 차이를 극복하기 위해 임시 기억 장치의 자료 구조로 Queue를 사용한다→ 이 것이 컴퓨터의 버퍼(buffer)!!
→ 버퍼링을 생각하면 수월할 듯?

 

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생합니다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용합니다.

다시 한번 컴퓨터와 프린터 사이의 데이터(data) 통신을 정리해 보면,

1. 프린터는 처리 속도가 느리다
2. CPU는 프린터와 비교해 데이터 처리 속도가 빠르다
3. 이 간극을 맞추기 위해 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만들어서
이를 인쇄 작업 Queue에 저장하고, 자기는 또 다른 작업하러 감
4. 프린터는 인쇄 작업 Queue에서 해당 데이터를 받아서 일정한 속도로 인쇄 프로세스 시작

 

우리가 일반적으로 말하는 버퍼링(유튜브, 트위치 등에서 발생하는)을 생각 해보면,

1. 동영상 시청 시, 다운로드 된 데이터가 영상을 재생하기에 충분하지 않은 경우가 발생
2. 컴퓨터는 동영상을 정상적으로 재생하기 위해 이 데이터를 Queue에 모아 두었다가
3. 동영상을 재생하기에 충분한 양의 데이터가 모였으면 동영상을 재생

→ 버퍼링의 과정!

Graph & Tree & BST

Graph

컴퓨터 공학에서의 그래프는 일반적인 의미와 다름!
→ 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 “복잡한 네트워크 망”의 모습
→ 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

단방향 그래프

* 정점(vertex): 그래프에서 하나의 점
* 간선(edge): 그래프에서 하나의 선

그래프의 실사용 예제

포털 사이트의 검색 엔진, SNS에서 사람들 간의 관계, 네비게이션(길찾기) 등이 있다

→ 네이게이션 시스템을 통해 구조를 살펴보자

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다. 대전에 살고 있는 친구 C도 B의 결혼식에 참석을 한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동을 하려고 합니다.

 

이를 정점과 간선으로 나타내면

* 정점: 서울, 대전, 부산
* 간선: 서울ㅡ대전, 대전ㅡ부산, 부산ㅡ서울

→ 이 간선은 “이동할 수 있음”을 나타냄

 

Cf.) 정점에 “LA”를 추가하더라도 이동할 수 없으므로 간선은 추가 안된다
→ “관계가 없다”라고 표현(그래프에서)

 

간선을 살펴 보면 정점 간 관계가 있다는 것은 알 수 있지만 그 외의 정보는 알 수 없다(각 도시간 거리라든지)

 

이렇게 추가적인 정보를 파악할 수 없는 그래프, 즉 가중치(연결의 강도의 정도)가 적혀 있지 않은 그래프
→ “비가중치 그래프”

ex) JavaScript로 나타낸 네비게이션 그래프의 상황

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

 

위의 비가중치 그래프를 가중치 그래프로 바꾸고, 각 도시간의 거리를 표시한다면?

* 정점: 서울, 대전, 부산
* 간선: 서울 ㅡ140kmㅡ 대전, 대전  ㅡ200kmㅡ 부산, 부산 ㅡ325kmㅡ 서울

이와 같이 간선에 “연결정도”(거리 등)를 표현한 그래프
→ “가중치 그래프”

관련 그래프 용어들

* 무(방)향그래프(undirected graph): 위에서 본 네비게이션 예제 같은 케이스. 
서울에서 부산으로 갈 수 있고, 반대로 부산에서 서울로도 갈 수 있다. 
만약 단방향(directed) 그래프로 구현된다면 어느 한쪽으로만 갈 수 있다.

* 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 
진출(나가는 간선)하는 간선이 몇 개인가를 나타냄

* 인접(adjacency): 두 정점 간에 간선이 “직접적”으로 이어진 경우, 이 두 정점은 “인접”한 정점

* 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
“자기 루프를 가졌다” 라고 표현. 이 자기 루프는 다른 정점을 거치지 않는다는 것이 특징

* 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아올 수 있는 경우 “사이클이 있다” 라고 표현
위의 네비게이션 그래프의 경우 `서울-> 대전-> 부산 -> 서울”로 되므로 사이클이 존재하는 그래프

 

그래프의 표현 방식: 인접 행렬 & 인접 리스트

인접 행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 “2차원 배열”의 형태
만약 A라는 정점과 B라는 정점이 이어져 있으면 1(true), 그렇지 않다면 0(false)로 표시한 일종의 표
→ 가중치 그래프라면 1대신 관계에서 의미 있는 값을 저장(ex 거리)

ex) 간략하게 그래프 모양을 표로 나타내자면 이럴 것이다.
    To
From===============
     A    B    C
A    0    0    1
B    1    0    1
C    1    0    1
==================
* A의 진출차수: 1개(A->C)
[0][2]===1
* B의 진출차수: 2개(B->A, B->C)
    [1][0]===1
    [1][2]===1
* C의 진출차수: 1개(C->A)
    [2][0]===1

 

인접 행렬은 언제 사용?

* 두 정점 사이에 관계 유무 확인에 용이
→ A에서 B로 진출하는 간선의 유무 파악할 때 바로 0번째 행의 1번째 열에 값을 보면 된다
* 가장 빠른 경로(shortest path)를 찾을 때도 주로 사용

 

인접 리스트

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

정수로 이루어진 리스트의 예시

 

ex) 간략하게 리스트의 형태를 표현하자면

A→ C→ Null
B→ A→ C→ Null
C→ A→ Null

B는 A와 C로 이어지는 간선이 두개가 있는데, 왜 A가 C보다 먼저인가? 이 순서가 중요?
→ “보통은 중요하지 않음”

그래프를 인접 리스트로 구현할 때 정점별로 살펴봐야할 우선 순위를 고려해 구현할 수도 있다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다.

→ 그런데 우선 순위를 다룰 때는 더 적합한 다른 자료구조(queue, heap)를 이용하는 것이 합리적이므로, 따라서 “보통”은 중요치 않다(예외는 존재)

 

인접 리스트는 언제 사용?

메모리를 효율적으로 사용하고 싶을 때 사용
→ 인접 행렬은 연결 가능한 모든 경우의 수를 저장하므로 상대적으로 메모리를 많이 차지

 

Tree

하나의 뿌리로부터 가지가 사방으로 뻗은 형태; 나무와 닮아서 트리 구조라 부름
→ 데이터가 바로 아래에 있는 하나 이상의 데이터에 “단방향”으로 연결된 “계층적” 자료구조
→ 또한, 하나의 데이터 뒤에 여러 개의 데이터가 존재 가능한 “비선형 구조”
→ 아래로만 뻗어가므로 사이클이 존재x

트리 구조 중 이진 트리의 예

루트(Root)라는 하나의 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결한다

용어 정리

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

자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

깊이(depth)

루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트는 깊이가 0

레벨(Level)

같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 가능. Depth가 0인 루트의 level은 0
같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 함

높이(Height)

리프 노드를 기준으로 루트까지의 높이를 표현 가능. 각 리프 노드의 높이를 0으로 놓고 계산
즉, 부모 노드의 height =자식 노드의 가장 높은 높이값(height)+1

서브 트리(Sub Tree)

큰 트리의 내부에, “트리 구조를 갖춘 작은 트리”를 “서브 트리”라고 함

트리의 실사용 예제

가장 대표적인 예는 “컴퓨터의 디렉토리 구조”
→ 어떤 프로그램이나 파일을 찾을 때 특정 폴더에서 다른 폴더에 진입하고 또 그 안에서 다른 폴더에 진입하면서 찾으니깐…
→ 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작하여 가지를 뻗어 나가는 모양새

“파일 시스템” 등이 트리 구조로 만들어져 있다
그 외에도 경기 토너먼트 대진표, 가계도(족보), 조직도 등의 예가 있다

 

Binary Search Tree(이진 탐색 트리)

트리 구조는 편리한 구조를 전시하는 것 외에 “효율적인 탐색”을 위해 사용하기도 한다
→ 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 대표적

이진 트리(Binary Tree)

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

 

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

* 정 이진 트리(Full binary tree): 각 노드가 0개 또는 2개의 자식 노드를 가짐

* 포화 이진 트리(Perfect binary tree): 정 이진 트리이면서(and) 완전 이진 트리인 케이스
모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리

* 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고
마지막 레벨의 노드는 전부 차 있지 않아도 되지만, 왼쪽은 채워져 있어야 한다.

<정 이진 트리>

<포화 이진 트리>

<완전 이진 트리>

 

 

이진 탐색 트리(Binary Search Tree)

모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징을 가진다
→ 이진 탐색 트리가 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리는 문제 발생(탐색 시간이 길어짐)

 

→ 이 경우, 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘 추가 필요