211216, 17 D+31(32) 자료구조, Stack / Queue, Graph, Tree, BST

1. 자료구조(Data Structure)

‣ 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것.

‣ 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없다.

 

﹡데이터(data): 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값.

→ 우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있다.

→ 데이터는 그 자체만으로 어떤 정보를 가지기 힘들기 때문에

    데이터는 필요에 따라 데이터의 특징을 잘 파악(분석)하고 정리하여 활용해야만 의미를 가질 수 있다.

→ 데이터를 체계적으로 정리하여 저장해두는 것이 데이터를 활용하는 데 있어 훨씬 유리하다.

ex) 나이라는 데이터만 알고 있다면, 사람의 나이인지, 강아지의 나이인지, 나무의 나이인지 알 수 없다.

 

1-1. 자료구조의 특징

→ 특정 상황에 놓인 문제를 해결하는 데에 특화되어 있다.

→ 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다. 

(문제 해결력을 필요로 하는 알고리즘 테스트(코딩 테스트)와 굉장히 밀접한 연관성이 있으므로

특정 문제를 해결하는 데에 적합한 자료구조를 찾아 데이터를 정리하고 활용할 줄 알면

상황에 가장 적합하고 정확한 코드를 작성할 수 있다.)

 

✷ 그래서 왜 데이터 구조와 알고리즘을 공부해야 된다고요?

자료구조를 활용해 알고리즘 문제를 풀 수 있다.

알고리즘 문제를 마주했을 때 문제를 풀기에 적합한 자료구조를 파악하고, 그에 알맞게 자료구조를 사용한다.

자료구조를 학습하기 시작한 지금, 문제를 마주하고 어떤 자료구조를 사용할지 결정할 수 없고,

그리고 알고리즘 문제를 만날 때마다 필요한 자료구조를 클래스로 직접 정의해서 풀기에는 많은 시간이 소요된다.

테스트 시간이 무제한이라면 상관없지만, 대부분의 알고리즘 테스트에는 제한 시간이 존재한다.

 

✷ 여기서는 JavaScript에서 제공하는 배열과 같은 데이터 타입을 이용해 자료구조의 형태와 유사하게 구현하여 문제를 해결함.

 

출처: 코드스테이츠 유어클래스

 

2. 자료구조의 종류

참고영상-Stack / Queue는 3:06부터

참고영상2-Stack / Queue-노마드코더

 

① Stack(스택)

: 데이터(data)를 순서대로 쌓는 자료구조.

ex) 택배 상하차

→ 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.

→ 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.

⇒ 가장 마지막 데이터가 가장 먼저 빠져나간다 / 가장 먼저 들어온 데이터가 가장 마지막에 빠져나간다.

 

✅ Stack의 실사용 예제

: 브라우저의 뒤로가기, 앞으로가기 기능.

‣ 브라우저에서 자료구조 Stack이 사용될 때 거치는 순서

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관.

2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때,

    현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴.

3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때,

    Next Stack의 가장 마지막으로 보관된 페이지를 가져옴.

4. 마지막으로 현재 페이지를 Prev Stack에 보관함.

function browserStack(actions, start) {
  // actions는 배열, start는 string타입
  // 배열 타입으로 리턴
  // 이전 페이지, 현재 페이지, 다음 페이지
  // prevPage, current, nextPage
  // prevStack, current, nextStack
  
  if(typeof start !== "string") return false;

  // 뒤로가기는 -1(prevStack)
  // 앞으로가기는 +1(nextStack)
  let prevStack = [];
  let nextStack = [];
  let current = start;

  // 하나씩 돌아간다
  // 반복문
  for(let i = 0; i < actions.length; i++) {
    // 뒤로가기 버튼을 눌렀을 때(&& 활성화가 된 경우)
    if(actions[i] === -1 && prevStack.length !== 0) {
      // 원래 있던 페이지를 next스택에 넣고
      nextStack.push(current);
      // prev 스택의 top에 있는 페이지로 이동한후
      // prev 스택의 값을 pop합니다
      let prevPage = prevStack.pop();
      current = prevPage;

      // 앞으로 가는 버튼을 눌렀을 때(&& 활성화가 된 경우)
    } else if(actions[i] === 1 && nextStack.length !== 0) {
      // 원래 있던 페이지를 prev스택에 넣고
      prevStack.push(current);
      // next스택의 top에 있는 페이지로 이동한 후
      // next스택의 값을 pop합니다
      let nextPage = nextStack.pop();
      current = nextPage;

      // 새로운 페이지로 접속할 경우
    } else if(typeof actions[i] === "string") {
      // prev스택에 원래 있던 페이지를 넣고
      prevStack.push(current);
      current = actions[i];
      // next스택을 비운다
      nextStack = [];
    } else {
    }
  }
  return [prevStack, current, nextStack];
}

 

② Queue(큐)

: 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)이 특징.

ex) 은행 창구

→ 데이터(data)가 입력된 순서대로 처리할 때 주로 사용함.

⇒ 가장 먼저 들어온 데이터가 가장 먼저 빠져나간다 / 가장 마지막에 들어온 데이터는 다 빠질때까지 나갈 수 없다.

 

✅ Queue의 실사용 예제

: 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 때.

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

 

‣ 컴퓨터와 프린터 사이의 데이터(data) 통신

→ 일반적인 프린터는 속도가 느리다.

→ CPU는 프린터와 비교하면 데이터를 처리하는 속도가 빠르다.

→ CPU는 빠른 속도로 인쇄에 필요한 데이터를 만들고,

    인쇄 작업 Queue에 저장한 후 다른 작업을 수행함.

→ 프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄.

function queuePrinter(bufferSize, capacities, documents) {
  // 작업 목록 크기, 최대 용량, 문서들(배열)

  // 모두 인쇄되는데 걸리는 최소 시간 리턴
  // return count;
  // 1초마다 추가를 시도해야한다 --> count++

  // 1초가 지나는 것을 세주기 위한 변수
  // 걸리는 시간을 세는 변수
  let count = 0;

  // 이 문서가 들어가는 공간
  // 가상의 대기열
  let queue = [];

  // 작업물의 총 크기(용량)
  let totalBuffersize = 0;

  // 1 <= bufferSize <= 100
  // 들어갈 수 있는 작업 목록의 크기는 정해져있다
  for(i = 0; i < bufferSize; i++) {
    // 총 용량을 넘는 것을 방지하기 위해서 0으로 시작한다.
    // 처음부터 시작할 queue는 0으로 고정되어서 시작한다.
    // 그렇게 반복해서 계속 돌린다(반복문)
    queue.push(0);
  }

  // 프린터가 제일 처음으로 실행하고 있을 때
  // queue의 제일 앞에 현재 문서를 넣어주고
  // 대기열에서 그 문서를 지운다
  let currentDocument = documents.shift();
  queue.unshift(currentDocument);
  queue.pop();

  // 총 용량에 현재 문서의 크기를 더한다.
  totalBuffersize = totalBuffersize + currentDocument;

  // 1초 지났음
  count++;

  // 인쇄가 끝났다 === 총 용량이 0이 되었다
  // --> 총 용량이 0이 될 때까지 반복한다
  // --> 0이 될 때까지 빼준다
  while(totalBuffersize) {
    totalBuffersize = totalBuffersize - queue.pop();
    currentDocument = documents.shift();

    // 총 용량과 현재 문서 용량을 더한 것이 
    // 최대 용량보다 작거나 같다면?(용량을 넘지 않는다면)
    if(totalBuffersize + currentDocument <= capacities) {
      queue.unshift(currentDocument);
      totalBuffersize = totalBuffersize + currentDocument;

      // 최대 용량을 넘으면
    } else {
      documents.unshift(currentDocument);
      queue.unshift(0);
    }
    count++;
  }
  return count;
}

 

✷ !!(느낌표 2개를 앞에 붙이는 것)은 무슨 의미일까?

⇒ 정의되지 않은 변수/정의된 변수들을 강제로 논리 값으로 변환해주는 기능을 한다(Boolean Type Conversion).

⇒ 0, null, undefined의 값을 가지는 변수들의 정확한 논리 결과의 값이 필요할 때 사용할 수 있다.

let a = 0;
console.log(a);
// 0
console.log(!a);
// true
console.log(!!a);
// false

let a = null;
console.log(a);
// null
console.log(!a);
// true
console.log(!!a);
// false

let a = undefined;
console.log(a);
// undefined
console.log(!a);
// true
console.log(!!a);
// false

‣ 동영상 스트리밍 앱을 통한 동영상 시청(유튜브 등)

→ 다운로드 된 데이터가 영상을 재생하기에 충분하지 않은 경우가 있기 때문에 동영상을 정상적으로 재생하기 위해 Queue에 모아두었다가 동영상 재생에 충분한 양의 데이터가 모였을 때 재생한다.

 

‣ 버퍼(buffer)

: 컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용하는 것을 통틀어 말함.

→ 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용.

→ 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생하는데, 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다.

CPU는 규칙적, 대부분의 컴퓨터 장치들은 불규칙적임.

✅ JavaScript로 사용자 정의 데이터 타입을 만들어 내는 여러 방법 중 ES6 문법 중 하나인 class 키워드로 사용자 정의 데이터 타입을 만들고, Stack과 Queue의 데이터 타입을 정의한다.

이렇게 생성한 사용자 정의 데이터 타입은 Stack과 Queue를 Array와 object처럼 사용할 수 있다.

사용자 정의 데이터 타입으로 Stack과 Queue를 정의하면 new 키워드를 통해 새로운 객체(인스턴스)를 만들 수 있고 생성한 인스턴스를 통해 다양한 메소드를 사용할 수 있다.

// class 키워드를 사용하여 자료구조의 데이터 타입을 직접 정의한다. 
// 이 과정에서 필요한 속성과 메서드를 학습한다.

// class 키워드의 예
class Human {
  constructor(name, gender, job) {
    this.name = name
    this.gender = gender;
    this.job = job;
  }
  speak() {
    return `저는 ${this.name} 입니다.`
  }
}

const harvey = new Human('Harvey', male, doctor);
console.log(harvey.speak()); // '저는 Harvey 입니다.'

③ Graph(그래프)

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

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.

 

정점 A, B, C와 2개의 단방향 간선, 그리고 하나의 양방향 간선이 있는 그래프

정점(vertex)은 하나의 점, 간선(edge)는 하나의 선.

 

✅ 그래프의 실사용 예제

‣ 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 (길찾기) 등에서 사용하는 자료구조.

‣ 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있음.

ex) 길찾기의 예시

펠리칸 타운에 사는 에밀리는 칼리코 사막에 사는 샌디와 친구이다.
2년째 봄, 23일에 열리는 샌디의 결혼식을 위해 에밀리가 참석한다고 한다.
릿지사이드 빌리지에 사는 알리사가 샌디의 결혼식에 참석한다고 하여 에밀리는 펠리칸 타운에서 출발해서 릿지사이드 빌리지에 사는 알리사를 태워 함께 칼리코 사막으로 이동한다.

위의 예제에서는 3개의 정점이 존재하는데, 에밀리, 샌디, 알리사가 사는 각각의 마을이 정점이다.

그리고 이 3개의 정점은 서로 이어지는 간선(관계)을 가지고 있다.

 

‣ 정점: 펠리칸 타운, 릿지사이드 빌리지, 칼리코 사막

‣ 간선: 펠리칸 타운—릿지사이드 빌리지, 릿지사이드 빌리지—칼리코 사막, 칼리코 사막—펠리칸 타운

이 마을들 사이에는 이러한 간선이 존재하는데, 이 간선은 길찾기에서 이동할 수 있음을 나타낸다.

 

정점에 비행기를 타고가야만 갈 수 있는 주주시티를 추가한다면? 자동차로는 이동할 수 없기 때문에 어떠한 간선도 추가할 수 없는데, 그래프에선 이런 경우를 관계가 없다고 표현한다.

 

간선을 살펴보면 각 마을들이 서로 관계가 있다는 것은 알 수 있지만, 그 마을들이 얼마나 떨어져 있는지는 알 수 없다.

간선은 특정 도시 두 개가 이어져 있다는 사실만 알려줄 뿐, 그 외의 정보는 포함하지 않는다.

 

‣ 비가중치 그래프

→ 추가적인 정보를 파악할 수 없는 그래프.

→ 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 그래프.

// 비가중치 그래프로 나타낸 각 마을들의 그래프

let isConnected = {
  pelican: {
    ridgeside: true,
    calico: true
  },
  ridgeside: {
    pelican: true,
    calico: true
  },
  calico: {
    pelican: true,
    ridgeside: true
  }
}

console.log(isConnected.pelican.ridgeside) // true
console.log(isConnected.ridgeside.calico) // true

위 정보만으로는 펠리칸 타운에서 칼리코 사막까지 갈 수 있다는 사실 외에 파악할 수 있는 정보가 없다.

⇒ 현재의 비가중치 그래프를 가중치 그래프로 바꾸고, 각 도시 간의 거리를 표시할 수 있다.

비가중치 그래프는 각 정점 간의 연결 유무만을 판단, 가중치 그래프는 더 자세한 정보를 담을 수 있다.

 

‣ 정점: 펠리칸 타운, 릿지사이드 빌리지, 칼리코 사막

‣ 간선

: 펠리칸 타운—1.5km—릿지사이드 빌리지,

  릿지사이드 빌리지—2.0km—칼리코 사막,

  칼리코 사막—1.2km—펠리칸 타운

 

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

내비게이션은 간선에 거리를 표기한 가중치 그래프가 확장되어

수백만 개의 정점(주소)과 간선이 추가되어야 내비게이션에서 쓰는 자료구조와 유사해진다.

 

✅ 그래프 용어들

‣ 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소.

‣ 간선 (edge): 정점 간의 관계(정점을 이어주는 선).

‣ 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점.

 

‣ 가중치 그래프 (weighted Graph)

: 연결의 강도가 얼마나 되는지 적혀져 있는 그래프.

(연결의 강도: 추가적인 정보, 위의 예시에서는 펠리칸 타운에서 칼리코 사막으로 가는 거리 등)

‣ 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프.

‣ 무(방)향 그래프 (undirected graph)

: 앞서 보았던 길찾기 예제는 무(방)향 그래프이다.

펠리칸 타운에서 칼리코 사막으로 갈 수 있듯, 반대로도 가능하다.

하지만 단방향(directed) 그래프로 구현된다면

펠리칸 타운에서 칼리코 사막으로 갈 수 있지만, 반대는 불가능하다(그 반대의 경우도 마찬가지).

만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.

 

‣ 진입차수 (in-degree) / 진출차수 (out-degree)

: 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.

‣ 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점.

‣ 자기 루프 (self loop)

: 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 한다.

  다른 정점을 거치지 않는다는 것이 특징.

‣ 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현 한다.

길찾기 그래프는 펠리칸 타운 → 릿지사이드 빌리지 → 칼리코 사막 → 펠리칸 타운으로 이동이 가능하므로,

사이클이 존재하는 그래프이다.

 

③-1. 그래프의 표현 방식

▾ 인접 행렬

 → 한 개의 큰 표와 같은 모습을 한 인접 행렬

→ 그래프의 연결 관계를 이차원 배열로 나타내는 방식

⇒ 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.

ex) adj[i][j] ⇒ 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

그래프의 예시와 네비게이션 그래프를 인접 행렬로 표현한 그림

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기한다.

만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표.

가중치 그래프라면 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

 

✅ 간선이 유향(directed)이 아닌 무향(undirected)그래프일 때

 

✷ 인접 행렬을 사용하는 경우

‣ 두 정점 사이에 관계 여부를 확인하기에 용이하다.

예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해서

0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다.

‣ 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용한다.

‣ 인접 행렬은 연결 가능한 모든 경우의 수를 저장 → 상대적으로 메모리를 많이 차지함.

 

▾ 인접 리스트

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

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

내비게이션 그래프의 인접 리스트 예시

(B는 A와 C로 이어지는 간선이 2개인데, A가 C보다 먼저인)순서는 보통은 중요하지 않다(하지만 예외는 있을 수 있음).

모든 자료구조(그래프, 트리, 스택, 큐 등)는 구현하는 사람의 편의와 목적에 따라 기능을 추가 / 삭제할 수 있다.

그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다.

이 때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다.

우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다. 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적이다.

 

✷ 인접 리스트를 사용하는 경우

‣ 메모리를 효율 적으로 사용하고 싶을 때

 

✷ 힙(heap)이 뭔가요?

✷ 그래서 힙(heap)이 뭔데요??

✷ ???heap!!!

‣ 힙(heap): 사전적 의미는 더미, dummy, 쌓아 올린 것.

메모리에서 힙 영역이란건 사전적 의미처럼 들어오는대로 차곡차곡 배정한다는 의미이다.

예를 들어 10개의 원소로 된 배열이 있으면 0, 1, 2... 같이 배열 순서대로 데이터를 할당한다(무작위 할당X).

 

‣ 힙 영역: 데이터를 차곡 차곡 배정할 수 있는 공간.

(정의한 힙 영역보다 더 큰 데이터가 들어오면 힙 오버플로우가 발생)

 

‣ 힙 알고리즘(=힙 정렬): 차곡 차곡 저장된 배열을 이진트리처럼 생각해 정렬하는 알고리즘.

따라서 둘간의 관계는 힙영역에 차곡 차곡 들어온데로 저장된 구조(배열)을 그대로 이용

힙 정렬 알고리즘으로 우선순위 원소를 뽑아내거나 데이터 정렬을 하는 관계이다.

 

④ Tree(트리)

‣ 이름 그대로 나무의 형태, 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습.

‣ 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있어 트리 구조라 부름.

‣ 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조.

‣ 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조.

‣ 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없다.

출처: 코드스테이츠 유어클래스

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

위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node).

 

✅ 용어 정리

루트(Root): 트리 구조의 시작점이 되는 노드

노드(Node): 트리 구조를 이루는 모든 개별 데이터. 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계.

부모 노드(Parent Node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드.

자식 노드(Child Node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드.

리프 노드(Leaf Node): 트리 구조의 끝 지점, 자식이 없는 노드. 나무의 잎과 같다고 하여 그렇게 부름.

 

출처: 코드스테이츠 유어클래스

↑ 트리 구조의 레벨과 서브 트리

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

 

‣ 깊이 (depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.

루트 노드는 지면에 있는 것처럼 깊이가 0이다.

위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1, D, E, F, G의 깊이는 2.

 

‣ 레벨(Level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다.

depth가 0인 루트 A의 level은 1. depth가 1인 B와 C의 level은 2. D, E, F, G의 level은 3.

형제 노드(Sibling Node): 같은 레벨에 나란히 있는 노드

 

‣ 높이(Height)

리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.

리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1 한 값을 높이로 가진다.

트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.

위 그림에서 H, I, E, F, J의 높이는 0. D와 G의 높이는 1. B와 C의 높이는 2. 이 때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가지기 때문에 루트 A의 높이는 3.

 

‣ 서브 트리(Sub tree)

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

(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리.

 

✷ 트리의 실사용 예제

: 컴퓨터의 디렉토리 구조.

어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고,

또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.

모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.

(이 내용은 여기에서 이미 한 번 나왔던 내용이다.)

 

하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있다.

제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다.

사용자들이 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있다.

(또 다른 예시: 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.)

 

④-1. 이진 트리(Binary Tree)

‣ 자식 노드가 최대 두 개인 노드들로 구성된 트리.

‣ 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.

‣ 자료의 삽입, 삭제 방법에 따라

정 이진 트리(Full binary tree), 포화 이진 트리(Perfect binary tree), 완전 이진 트리(Complete binary tree)로 나뉨.

출처: 코드스테이츠

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

 

✷ binary heap

 

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

‣ 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.

‣ 이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다.

‣ 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제이다.

이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

 

✷ binary search - 관련 영상: 노마드코더 - 2:58 부터

 

④-3. 트리 순회(Tree traversal)

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

 

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

‣ 전위 순회 (preorder traverse): 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.

출처: 코드스테이츠

 

‣ 중위 순회 (inorder traverse): 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.

출처: 코드스테이츠

 

‣ 후위 순회 (postorder traverse): 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

출처: 코드스테이츠

 

⑤ BFS / DFS ⇒ 둘 다 모든 정점을 한 번만 방문한다는 공통점이 있다.

한국에서 미국으로 가는 비행기를 예약하려고 한다. 비행편에 따라 직항과 경유가 있다.
경유할 경우, 해당 항공사가 필요로 하는 공항에 잠시 머물렀다가 가기도 한다.
경유하는 시간은 비행편마다 다르고, 경유지도 다르다.
최단 경로를 알아내려면 어떻게 해야 할까?

‣ BFS(Breadth-First Search)

: 너비를 우선적으로 탐색하는 방법.

 

→ 한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다.

더 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문한다.

직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다.

경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다.

 

→ 주로 두 정점 사이의 최단 경로를 찾을 때 사용하는데,

만약, 경로를 하나씩 전부 방문한다면, 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴봐야 한다.

 

출처: 코드스테이츠

 

‣ DFS(Depth-First Search)

: 깊이를 우선적으로 탐색하는 방법.

 

→ 비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 수 없다.

이 때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야 하는데,

DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다.

하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있다.

또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있다.

 

→ 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.

BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

출처: 코드스테이츠

 

‣ BFS와 DFS의 차이 한 번에 보기

DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현 검색 대상의 그래프가 클 때나 미로찾기 등의 최단거리를 구해야할 때 유용함	큐를 이용해서 구현 검색 규모가 크지 않고 검색 대상이 시작 지점으로부터 멀지 않으며 경로의 특징을 저장해야 할 때 유용함

 

✷ Linked List