[자료구조] Stack, Queue, Graph, Tree

자료구조

여러 데이터들의 묶음을 저장하고 효율적으로 사용하는 방법을 정의한 것
*특정한 상황에 놓인 문제를 해결하는 데에 특화

• 데이터 : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
  *데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있으며, 사용 목적에 따라 형태를 구분하고 분류하여 사용

 

 

Stack

데이터를 순서대로 "쌓는" 구조

• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근 (일방통행)
  *이러한 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 함

• 재귀 함수와 활용도가 높음

const stack = []

stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]
stack.push(4) // [1, 2, 3, 4]
stack.push(5) // [1, 2, 3, 4, 5]
//LIFO(Last In First Out) => 마지막에 추가된 맨 위의 항목은 처음 끄집어 낼 수 있다.

stack.pop() // [1, 2, 3, 4]
stack.pop() // [1, 2, 3]
stack.pop() // [1, 2]
stack.pop() // [1]
//FILO(First In Last Out)

 

 

browserStack 예제

1. 새로운 페이지로 접속할 때
   : 현재 페이지를 Prev Stack에 보관
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때
   : 현재 페이지를 Next Stack에 보관하고, Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동할 때
   :Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
4. 마지막
   :현재 페이지를 Prev Stack에 보관

function browserStack(actions, start) {
  // 출력 예시 : [[prev],current,[next]]
  // -1 : 뒤로 가기
  // 1 : 앞으로 가기

  let prev = []
  let current = start
  let next = []
  // 출력에 필요한 변수들 생성
  // current : 시작값 할당

  // 각 변수에 저장해 기억해 두기위한 재귀함수 생성
  let memo = (actions) => {
    let [head, ...tail] = actions

    for (let i = 0; i < actions.length; i++) {
      if(typeof head === 'string') { 
        //새로운 페이지 접속
        prev.push(current) 
        current = head
        next = []
      } else if(head === -1) {
        // 뒤로가기
        next.push(current)
        if(prev.length !== 0) {
          current = prev.pop()
        }
      } else if(head === 1) {
        // 앞으로 가기
        prev.push(current)
        current = next.pop()
      }
      return memo(actions.slice(1)) 
    }
  }

  // 재귀함수 실행
  memo(actions)

  return [prev, current, next]
}

 

 

Queue

줄을 서서 기다리는 대기행렬 구조

CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장 후 다른작업 수행
프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄

• Stack과 반대되는 개념으로 먼저 들어간 데이터가 먼저 나옴
  *FIFO(First In First Out) 혹은 LILO(Last In Last Out)
• 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용
  *이 과정을 버퍼(buffer)라고 함
• while 반복문과 활용도 좋음

const queue = []

queue.push(1) // [1]
queue.push(2) // [1, 2]
queue.push(3) // [1, 2, 3]
queue.push(4) // [1, 2, 3, 4]
queue.push(5) // [1, 2, 3, 4, 5]

// FIFO(First In First Out)
queue.shift() // [2, 3, 4, 5]
queue.shift() // [3, 4, 5]
queue.shift() // [4, 5]
queue.shift() // [5]
// LILO(Last In Last Out)

 

 

paveBox 예제

function paveBox(boxes) {

  let result = []
  // 몇명의 사람이 박스 포장을 끝내고 한번에 나갈 수 있는지 기록

  // head보다 많은 박스를 포장해야 하는 사람을 만나면 배열 분리
  let splitArr = (boxes) => {
    let [head, ...tail] = boxes
    
    // head보다 작거나 같은 박스를 포장해 head와 함께 나갈 수 있는 사람들 기록
    let newArr = []

    for(let i = 0; i < tail.length; i++) { 

      if(head < tail[i]) {
        // head보다 많은 박스를 포장해야 할 사람을 만났을 경우
        result.push(newArr.length + 1)
        return splitArr(tail.slice(i)) 
      } else if(head >= tail[i]) {
        // head보다 작거나 같은 박스를 포장할 사람을 만났을 경우
        newArr.push(tail[i])
        if(newArr.length === tail.length) {
          // head보다 많은 박스를 포장해야 할 사람 없이 끝나는 경우
          return result.push(newArr.length + 1)
        }
      }
    }
  }

  // 재귀함수 실행
  splitArr(boxes)

  return Math.max(...result)
  // 최대 몇명이 함께 나갈 수 있는지 리턴
}

//다른풀이
function paveBox(boxes) {
    let answer = []
    
    // boxes 배열이 0보다 클 때까지 반복합니다.
    while(boxes.length > 0){
      // 첫번째 사람보다 많은 상자를 포장해야 하는 사람의 인덱스를 찾음
      // 없으면 -1 반환
      let findIdx = boxes.findIndex(el => boxes[0] < el);
      
      if(finishIndex === -1){
          // 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후 while문을 끝냄
          answer.push(boxes.length)
          break

      } else {
          // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외
          answer.push(findIdx);
          boxes.splice(0, findIdx);
      }
    }

 

 

queuePrinter 예제

1. 프린터에 비해 속도가 빠른 CPU :
   빠른 속도로 인쇄에 필요한 데이터(data)를 만들어 인쇄 작업 (임시 기억 장치의) Queue에 저장하고 다른 작업을 수행
2. 프린터 :
   인쇄 작업 Queue에서 데이터(data)를 받아 Queue에 들어온 문서를 순서대로 인쇄

function queuePrinter(bufferSize, capacities, documents) {
  // bufferSize : 작업 공간의 크기
  // capacities : 작업 공간의 용량
  // documents : 인쇄할 문서

  let workSpace = []

  let currentDocument = documents.shift()
  workSpace.push(currentDocument)
  // workSpace에 처음 인쇄할 문서를 넣어줌

  let timer = 1
  // 타이머 : 1초에서 시작

  let workSpaceVolume = currentDocument

  // 남은 작업 공간에 0을 채워줌
  for(let i = 0; i < bufferSize - 1; i++) {
    workSpace.push(0)
  }

  while(workSpaceVolume > 0) {
    workSpaceVolume = workSpaceVolume - workSpace.pop() 
    currentDocument = documents.shift()
    
    if(workSpaceVolume + currentDocument <= capacities) {
      // 작업 공간에 문서 추가로 넣어줌
      workSpace.unshift(currentDocument)
      workSpaceVolume = workSpaceVolume + currentDocument
    } else {
      // 용량이 넘쳐 문서를 추가할 수 없을 때
      workSpace.unshift(0)
      documents.unshift(currentDocument)
    }

    timer++
  }
  
  return timer
}

 

 

Graph

• 컴퓨터 공학에서의 그래프 : 네트워크 망 형태
• 여러개의 점들이 서로 복잡하게 연결되어 있는 구조
• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 존재
• 인접 매트릭스 또는 인접 리스트로 표현 가능

 

 

그래프 용어

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

 

 

그래프의 표현 방식

• 인접 행렬 : A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
  *가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용
• 인접 리스트 : 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현
  *정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있음

 

1. 인접 매트릭스(adjacency matrix)

• 세로 : from & 가로 : to의 2차원 배열
• 각 vertex가 연결되어 있으면 [from][to] = 1
  *edge가 있음을 의미
• edge 삭제 : [from][to] = 0

 

1-1. matrix 만들기

let matrix = []
let max = 3
// 가장 큰 정점
for(let i = 0; i < max + 1; i++) { 
  matrix.push(new Array(max + 1).fill(0)) 
}
//[[0, 0, 0, 0], [0. 0, 0, 0], [0. 0, 0, 0], [0. 0, 0, 0]]

let matrix = new Array(max + 1).fill(0).map(e => new Array(max + 1).fill(0))
//[[0, 0, 0, 0], [0. 0, 0, 0], [0. 0, 0, 0], [0. 0, 0, 0]]

 

1-2. edges 만들기

matrix[0][1] = 1
matrix[1][0] = 1

matrix[0][2] = 1
matrix[2][0] = 1

matrix[0][3] = 1 
//단방향

matrix[1][2] = 1 
matrix[2][1] = 1

 

2. 인접 리스트(adjacency list)

• 그래프의 각 정점에 인접한 정점을 연결 리스트로 표현하는 방법
• 연결 리스트의 노드는 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 갖는 배열로 갖음
  *정점의 번호만 알고 있으면 각 정점의 연결 리스트에 쉽게 접근 가능

 

2-1. adjList 만들기

let max = 3
// 가장 큰 정점

let adjList = {}

for(let i = 0; i < max + 1; i++) {
  adjList[i] = []
}
//{0 : [], 1 : [], 2 : [], 3 : []}

 

2-2. edges 만들기

adjList[0].push(1)
adjList[0].push(2)
adjList[0].push(3)

adjList[1].push(0)
adjList[1].push(2)

adjList[2].push(0)
adjList[2].push(1)

adjList[3].push(0)

 

 

내비게이션 시스템 예제

1. 비가중치 그래프

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

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

• 간선 : 차로 이동할 수 있음을 의미
  *이어져 있음만 알 수 있고, 얼마나 떨어져 있는지는 파악 불가
• 비가중치 그래프 : 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 그래프

 

2. 가중치 그래프

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

• 가중치 그래프 : 간선에 연결정도(거리 등)를 표현한 그래프

 

 

그래프 용어

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

 

 

그래프의 탐색 기법

• 그래프의 탐색 : 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문(탐색)하는 것을 목적으로 함

 

 

BFS (Breadth-First Search) : 한국에서 미국으로 가는 가장 빠른 경로

• 가까운 정점부터 탐색
• 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문
• 너비를 우선적으로 탐색한다고 하여 Breadth-First Search(너비 우선 탐색)이라 함
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용
• 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 함
• Queue(with while 반복문)와 활용도가 좋음

1. 한국 > 중국 > 한국 > 터키 > 한국 > 일본 > 한국 > 괌
2. 한국 > 중국 > 케냐 > 한국 > 중국 > 몽골 > 한국 > 터키 > 인도 > 한국 > 터키 > 미국
3. 최단 경로 : 한국 > 터키 > 미국

 

 

DFS (Depth-First Search) : 한국에서 미국으로 가는 경로

• 하나의 경로를 끝까지 탐색
• 찾는 정점이 아니라면 다음 경로로 넘어가 탐색
• 깊이를 우선적으로 탐색한다고 하여 Depth-First Search(깊이 우선 탐색)이라 함
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
• BFS보다 탐색 시간은 오래 걸리지만 모든 노드를 완전히 탐색 가능
• Stack(with 재귀함수)와 활용도가 좋음

 

1. 한국 > 중국 > 케냐 > 한국 > 중국 > 몽골 > 영국
2. 한국 > 터키 > 인도 > 독일 > 한국 > 터키 > 미국 : 최단 경로
3. 최단 경로 : 한국 > 터키 > 미국

 

 

Tree

• 나무를 거꾸로 뒤집어 놓은 듯한 구조
• 그래프의 여러 구조 중 무방향 그래프의 한 구조로 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 아래로만 뻗어나가기 때문에 사이클이 없음
• 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결
• 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가짐
• 깊이와 높이, 레벨 등을 측정할 수 있음

 

관련 용어

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

 

 

Tree 특징

1. 깊이 (depth)

• 루트로부터 하위 계층의 특정 노드까지의 깊이(depth) 표현 가능
• 루트 노드 : 깊이 0에서 시작

 

2. 레벨(Level)

• 같은 깊이를 가지고 있는 노드의 묶음
• depth가 0인 루트의 level은 1
• 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node)라고 함

 

3. 높이(Height)

• 리프 노드를 기준으로 루트까지의 높이(height)
• 리프 노드와 직간접적으로 연결된 노드의 높이를 표현
• 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이
• 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 함

 

4. 서브 트리(Sub tree)

• 트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

 

 

이진 트리 및 이진 탐색 트리

• 이진 트리(binary tree) : 자식 노드가 최대 2개인 노드들로 구성된 트리
  *왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있음
• 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉨
• Balnced Tree : 모든 leaf node의 level 차이가 최대 1인 트리로 트리의 주 목적인 '탐색'을 위한 AVL tree, red-black tree 와 같은 자료구조들의 기반이 됨

 

1. 이진 트리(binary tree)

1-1. 정 이진 트리(Full binary tree)

• 각 노드가 0 개 혹은 2 개의 자식 노드를 갖음

 

1-2. 포화 이진 트리(Perfect binary tree)

• 정 이진 트리이면서 완전 이진 트리인 경우
• 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리

 

1-3. 완전 이진 트리(Complete binary tree)

• 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함

 

2. 이진 탐색 트리 (Binary Search Tree)

• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
• 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있음
• 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가해야 함

 

 

Tree traversal

• 트리 순회 : 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
• 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 존재

 

1. 전위 순회

25 > 20 > 10> 5 > 12 > 22 > 36 > 30 > 28 > 40 > 38 > 48

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

 

2. 중위 순회

5 > 10 > 12 > 20 > 22 > 25 > 28 > 30 > 36 > 38 > 48 > 40

• 루트를 가운데에 두고 순회
• 제일 왼쪽 끝에 있는 노드부터 순회하기 시작
• 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 탐색

 

3. 후위 순회

5 > 12 > 10 > 22 > 20 > 28 > 30 > 38 > 48 > 40 > 36 > 25

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