[코드 스테이츠] 42일차, "6주차 복습 (2) - 자료구조"

---

[ 오늘의 TODO ]

1. 코드 스테이츠) 목~금 내용 복습
   // 자료구조 개념
2. 패스트 캠퍼스) 인강 3개 이상 듣기 // optional
3. 스터디 그룹) 프로그래머스 문제 풀기 (~월)
   // 하노이의 탑 
   (구글링해서 풀리긴 하는데... 내가 직접 푼 게 아니라서 찝찝함)
4. 생활) 물 1L 이상 마시기
5. 생활) 수-토-일 운동 
   // 다시 운동하기 위해 노력해보겠습니다. 

---

[ 오늘의 복습 ]

1.  자료구조

  1) 자료구조란?

  여러 데이터들을 묶어 저장하고 사용하는 방법을 정의한 걸 자료구조라고 한다.

 

  여기서 데이터라는 건 실생활의 모든 값을 의미한다. 하지만, 데이터의 값은 그 자체로 의미를 지니진 못한다. 예를 들어 100m 라는 데이터가 있다고 하자. 여기서 100m는 100m 달리기의 100m 인지, 맛집에 가기 위해 걸리는 거리인지 알 수 없다. 그렇기에 데이터는 분석하고, 정리하고 활용해야 의미가 생긴다. "현 위치에서 약속장소까지의 거리: 100m", "달리기로 1위한 거리: 100m" 이런식으로 해야 데이터는 비로소 그 의미가 생기는 것이다.

 

  여기서 필요에 따라 데이터의 특징을 파악하고 분석하고 정리해서 활용해야 한다. 이 때 데이터를 체계적으로 정리하고 관리할 수 있도록 해주는 것이 자료구조다. 

 

  자료 구조 중에서 자주 쓰이는 게 4가지 있다. 1) Stack, 2) Queue, 3) Tree, 4) Graph 

 

2. Stack

  1) Stack 이란?

  Stack은 영어로 "쌓다, 쌓이다"라는 의미다. 책을 쌓아 올린 형태와 비슷한 구조를 지닌다. 만약 바닥에 책을 쌓아 올렸을 때, 가장 먼저 내가 꺼내게 될 책은 가장 나중에 쌓은 책이다. 가장 나중에 쌓은 책일수록 가장 위에 있기에 꺼낼 때는 가장 나중에 쌓았던 것이 된다. 

 

  그래서 Stack의 가장 주된 특징은 가장 먼저 들어간 자료가 가장 나중에 나오고, 가장 나중에 들어간 자료가 가장 먼저 나오는 LIFO(Last In First Out), FILO(First In Last Out) 이다. 

 

  2) Stack의 실제 사례

  예를 들면 브라우저의 뒤로 가기, 앞으로 가기 버튼이 될 것이다. 우리가 뒤로 가기 버튼을 누른다면 가장 나중에 방문한 페이지가 꺼내지기 때문이다. 

 

 

3. Queue

  1) Queue 란?

  Queue는 영어로 "줄을 서서 기다리다", "대기 행렬"이라는 의미를 갖고 있다. Stack과는 정 반대되는 개념으로, 만약 내가 맛집에 들어가기 위해 줄을 서서 기다리고 있다면 먼저 온 사람이 먼저 들어가는 게 당연하다. 가장 나중에 온 사람이 가장 먼저 들어간다면 머리 끄덩이 잡힌다. 

 

  그렇기에 Queue의 주된 특징은 가장 먼저 들어간 자료가 가장 먼저 나오고, 가장 나중에 들어간 자료가 가장 나중에 나오는 FIFO(First In First Out), LILO (Last In Last Out) 이다.

 

  2) Queue의 실제 사례

  예를 들면 프린트기가 있다. 컴퓨터에서 프린트기에 가장 먼저 입력하는 페이지 수가 가장 먼저 나오는 형태로 출력된다. (역순 인쇄라면 달라지겠지만)

 

 

* Stack과 Queue는 어떻게 구현할 수 있을까?

  다른 언어들과 같이 클래스로 만들어서 사용할 수 있을 것이다. ES6 문법 중 하나인 class 를 사용해 사용자 정의 데이터 타입을 만들어서 Stack, Queue 데이터 타입을 정의해서 사용할 수 있을 것이다.

 

  하지만, 자바 스크립트에는 배열이라는 자료형이 매우 잘돼있다. prototype을 통해 메소드들도 굉장히 잘 구현돼 있어서 Stack이라면 .pop을 통해서 FILO 를 구현할 수 있고, Queue 라면 .shift를 통해 FIFO를 구현할 수 있다.

 

  코플릿을 통해서 Stack과 Queue, 그 외에 Tree 와 Graph를 class 를 통해 구현해봤지만, 아직 완벽하게 숙지하진 못한 것 같다. 다음에 기회 되면 다시 돌아와서 내용을 정리해보고 공부해봐야할 것 같다. 

 

 

4. Graph 

  1) Graph 란?

  그래프라 하기에 우리가 흔히 생각하는 함수를 표현하는 그래프가 아니다. 거미줄처럼 여러 점들이 선으로 이뤄져 있는 복잡한 네트워크 망의 모양이 그래프다. 그래프는 여러 점들이 서로 복잡하게 연결돼 있다. 만약, 그 점들이 직접적인 관계가 있다면 두 점을 이어주는 선이 있고, 간접적인 관계가 있는 경우, 몇개의 점과 선을 걸쳐서 이어진다.

 

  용어를 한 번 정의하면 점들(데이터들)은 정점(Vertax)라고 부르고 점들을 잇는 선 하나 하나를 간선(Edge)라고 부른다.

 

  우리 주변에서 가장 흔하게 볼 수 있는 예시로는 지하철 노선도가 있다. 각 역은 정점에 해당하고, 그 점들을 잇는 선이 간선임을 의미한다. 지하철을 통해서 어느 역이든 다 갈 수 있으므로 모든 점들은 다 간접적인 관계에 있지만, 직접적인 관계는 없는 정점들은 존재한다.

 

네이버 지하철 노선도

 

  예를 들어 홍대입구역은 2호선으로 신촌역, 합정역 / 경의 중앙선으로 가좌역, 서강대역 / 공항선으로 디지털미디어시티역, 공덕역과 간선으로 이어져 있고 직접적인 관계에 있다. 하지만 상수역, 이대역, 당산역은 직접적으로 연결돼 있지 않지만 환승을 하든지, 조금 더 가든지 하면 도달할 수 있다. 이렇게 어떻게 건너 건너서 도착할 수 있다면 간접적인 관계에 있는 것이다.

 

  2) 비가중치 그래프

네이버 길찾기

 

  위의 예시처럼 정점과 간선에 대한 정보만 존재한다면 비가중치 그래프라고 한다.

  

  간선을 통해서 서로 관계가 있다는 것은 알 수 있지만, 거기까지 가는데 얼마나 시간이 걸리는지, 요금은 얼마 정도가 드는지에 대해 정보를 를 알 수 없다. 정말 간단하게 정점과 간선에 대한 정보만을 남기고 추가적인 정보를 파악할 수 없는 것을 비가중치 그래프라고 부른다. 위의 내용을 객체로 표현한다면 다음과 같다

 

let isConnected = {
  홍대입구: {
    합정: true,
    상수: false
  },
  합정: {
    홍대입구: true,
    상수: true
  },
  상수: {
    홍대입구: false,
    합정: true
  }
}

 

 

  3) 가중치 그래프

 

네이버 길찾기

  반면, 위의 사진은 얼마나 걸리는지, 요금은 얼마 정도 드는지, 출구 정보에 대한 내용이나 그 역마다 걸리는 시간 등 다양한 정보가 추가돼 있다. 이렇게 단순히 간선이 연결됐는 지의 유무만이 아니라 더 자세한 정보를 담아내 주는 것이 가중치 그래프다 (엄밀하게 얘기하면 위 사진은 정점과 간선으로만 이뤄진 것이 아니기에 그래프는 아니지만, 정보를 더 담아냈다에 중점을 두고 얘기하면 그렇다는 것)

  

  4) Graph와 관련된 용어들

    4-1) 무방향 그래프, 단방향 그래프

  방금 전 지하철 노선도가 무방향 그래프다. 방향성이 있다는 것은 한쪽에서 한쪽으로만 간다는 의미다. 흔히 말하는 "일방 통행"이다. 하지만 지하철 노선의 경우 홍대입구에서 합정에 갈 수 있고, 합정에서 홍대입구로 갈 수 있다. 이렇게 방향성 없이 갈 수 있는 것을 무방향 그래프라고 한다. 반면에 일방통행인 것을 단방향 그래프라고 부른다.

 

    4-2) 진입차수, 진출차수

  한 정점에 진입하는 간선이 몇 개인지를 나타내는 게 진입차수, 한 정접에서 진출하는 간선이 몇개인지 나타내는 게 진출 차수다. 무방향 그래프라면 진입차수와 진출차수는 동일하다.

 

  홍대입구역을 예로 들면 2호선으로 두 개(합정, 신촌), 경의 중앙선으로 두 개(가좌, 서강대), 공항선(디지털 미디어 시티, 공덕)으로 두 개 총 6개의 진입차수와 진출차수가 존재한다. 합정역의 경우 2호선으로 두 개(홍대입구, 당산), 6호선으로 두 개(상수, 망원) 총 4개의 진입차수와 진출차수가 존재하게 된다.

 

    4-3) 인접

  두 정점간에 간선이 직접적으로 이어져 있다면 두 정점은 인접한 정점이다.

 

  홍대입구와 합정은 인접하고, 합정과 상수는 인접하다. 하지만 홍대입구와 상수는 인접하지 않다.

 

    4-4) 자기 루프

  만약, 정점에서 진출한 간선이 곧바로 자기 자신에게 진입할 수 있는 경우 자기 루프를 가졌다고 표현한다. 자기에서 진출한 간선을 통해 다른 정점을 거치지 않고 그 간선으로 바로 진입하는 것이 특징이다. 예를 들면 롤러코스터가 있다. 롤러코스터는 출발한 후 어딘가에 정차하지 않고 다시 출발 지점으로 복귀한다. 이렇게 어디 거치지 않고 자기 자신으로 되돌아 오는 게 자기 루프다. 

 

    4-5) 사이클

  한 정점에서 출발해 출발한 정점으로 되돌아갈 수 있다면 사이클이 있다고 표현한다

 

  대부분의 지하철 역은 사이클이 존재한다. 홍대입구로 예를 들면

 홍대 입구 => 합정(환승) => 상수 => => 광흥창 => 대흥 => 공덕(환승) => 홍대입구

  이런식으로 다시 되돌아올 수 있다. 물론 위의 경우 외에도 다양한 방법으로 홍대 입구역으로 되돌아올 수 있는데 그렇게 한 번 출발해서 자기 루프가 아닌 방식으로 다시 자신에게 돌아온다면 사이클이 존재한다고 표현한다

 

 

  5) 그래프의 표현 방식

    5-1) 인접 행렬

  인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시하는 행렬로, 2차원 배열의 형태를 띈다. A와 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한다.

 

  만약, 가중치 그래프일 경우 1 대신에 걸리는 시간이나 요금 등의 값을 넣어줄 수 있다. 위의 홍대입구, 합정, 상수를 인접행렬로 만든다면 다음곽 같을 것이다.

 

	홍대입구	합정	상수
홍대입구	0	1	0
합정	1	0	1
상수	0	1	0

 

  이걸 이차원 배열로 만들면 다음과 같을 것이다

 

let subwayLine = [
 [0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]
]

 

  인접 행렬은 연결 가능한 모든 경우의 수를 저장하기에 상대적으로 메모리를 많이 차지하지만, 몇가지 경우를 제외하고 이 인접 행렬(matrix)를 사용한다.

 

    5-2) 인접 리스트

  인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 나타낸 것이다. 각 정점마다 리스트가 존재하고, 이 리스트는 자신과 인접한 다른 정점을 담는다. 

 

  인접 리스트는 메모리를 효율적으로 사용하고 싶을 때, 혹은 버텍스를 지우거나 살릴 때 사용한다

 

 

  6) Grapth 탐색

 

그래프 탐색 방법의 절대 원칙은 한 번 간 곳은 다시 가지 않는 것이다.

    6-1) BFS

  최단 경로를 찾는데 용이하다. 탐색을 시작하는 정점에서 원하는 정점을 찾기 위해 가장 가까운 정점부터 탐색한다. 그리고 더 탐색할 정점이 없을 때, 그 다음으로 떨어진 정점을 순서대로 방문한다. 이렇게 너비를 우선적으로 탐색하는 방법을 너비 우선 탐색, Breadth - First Search, BFS 라고 한다.

 

  이걸 구현하기 위해 대부분 Queue의 구조로 탐색하고 While 문이 사용된다.   

 

    6-2) DFS

  하나의 경로를 끝까지 탐색하고 없다면 다음 경로로 넘어간다. 한 정점에서 시작해 다른 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색한다. 깊이를 우선적으로 탐색하는 이런 방법을 깊이 우선 탐색, Depth - First Search, DFS 라고 한다. 한

 

  이걸 구현하기 위해 대부분 Stack의 구조로 탐색하고 재귀 함수의 방법이 사용된다

 

 

5. Tree

이진 트리

  1) Tree 란?  

  Tree 란 그 이름에서도 유추할 수 있듯이 나무의 형태를 취한다. 하지만, 그 나무는 지상의 나무 모습이 아니라 뿌리를 내린, 지하의 나무 모습이다. Graph의 여러 구조 중에서 단방향 그래프의 한 종류다. 각 데이터를 노드라고 부르며, 두 개의 노드가 상하 계층으로 연결될 대 부모-자식의 관계가 된다.

 

  2) 용어 정리

1. 노드(Node): 트리 구조를 이루는 모든 개별 데이터(2, 7, 5 등)
2. 루트(Root): 트리 구조의 시작점이 되는 노드 (맨 꼭대기에 있는 2)
3. 부모 노드(Parent Node): 두 노드가 상하 관계에 연결돼 있을 때 루트에 더 가까운 노드 (6이 5, 11의 부모 노드)
4. 자식 노드(Child Node): 두 노드가 상하 관계에 연결돼 있을 때 루트에 더 먼 노드 (11, 5 가 6의 자식 노드)
5. 리프(Leaf): 트리 구조의 끝 지점. 자식 노드가 없는 노드 (4)
6. 깊이(Depth): 트리 구조에서 루트로부터 특정 노드까지의 깊이를 의미한다. 
   (6까지의 깊이는 2, 4까지의 깊이는 3이 된다)
7. 레벨(Level): 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어 레벨이라 부른다
   (루트 노드가 레벨 1, 7과 5가 레벨 2다)
8. 높이(Height): 트리 구조에서 리프 노드를 기준으로 루트까지 올라가는 높이를 의미한다. 
   (맨 왼쪽의 2, 리프 노드로 있는5, 11, 4 의 높이는 0이다. 6은 높이가 1, 7은 높이가 2다)

 

  3) Binary Search Tree

  수많은 트리 구조 중 간단하고 많이 사용하는 구조 중에 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 있다. 지금 예시로 가져온 게 이진 트리다. 

 

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

 

이진 탐색 트리

  반면 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다. 즉 이진 트리에서 추가적으로 중복된 값을 허용하지 않고 크기에 따라 작으면 왼쪽, 크면 오른쪽으로 정렬 시켜 놓은 트리다. 이렇게 만들어준 이유는정리가 잘 돼있으므로 나중에 데이터를 탐색할 때 더 빠르게 데이터를 가져올 수 있기 때문이다.

 

 

  4) 트리 순회

  특정 목적으로 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 트리 순회의 방법에는 밑의 세 가지 방법이 있다.

1. 전위 순회
   최상위 노드 부터 시작
   PARENT(PARENT ⇒ LEFT ⇒ RIGHT) ⇒ LEFT ⇒ RIGHT
   
   
2. 중위 순회
   최하위 왼쪽 노드 부터 시작
   LEFT(LEFT ⇒ PARENT ⇒ RIGHT) ⇒ PARENT ⇒ RIGHT
   
   
3. 후위 순회
   최하위 왼쪽 노드 부터 시작
   LEFT(LERFT ⇒ RIGHT ⇒> PARENT) ⇒ RIGHT ⇒ PARENT