TIL 62일차 - [자료구조/알고리즘] Tree & Graph

• 트리의 개념과 특징, 용어에 대해 이해합니다.

  o

  

  자료구조 Tree는 나무를 거꾸로 뒤집어 놓은 형태를 가지고 있다.

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

  또한 그래프의 여러 구조 중 단방향 그래프의 한 구조로 데이터가 아래에 있는
  하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조다.

  이러한 트리 구조는 아래로만 뻗어나가기 때문에 시작 노드로 다시 돌아오는 cycle(사이클)이 없다.

  따라서 트리는 cycle이 없는 하나의 연결 그래프(connected graph)라고 할 수 있다.

  트리에서 사용되는 용어로는 아래와 같다.

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

• 트리의 실사용 예제를 보고, 트리가 어떻게 이용이 되는지 이해합니다.

  o
  트리의 대표적인 예제로는 컴퓨터의 디렉토리 구조가 있다.
  모든 폴더는 하나의 폴더 (루트 폴더, /)에서 시작되어 가지를 뻗어나간다.
  하나의 폴더 안에 여러 개의 폴더가 있고,
  또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있다.
  제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일하다.

  그 외 트리의 예시로는 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등이 있다.

• 직접 구현한 트리가 어떤 식으로 동작하는지 이해하고, 해당 클래스 내의 로직을 이해합니다.

  o

• 이진 탐색 트리의 개념과 종류 특징에 대해 이해합니다.

  o

  

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

• 직접 구현한 이진 탐색 트리가 어떤 식으로 동작하는지 이해하고, 해당 클래스 내의 로직을 이해합니다.

  o

• 전위 순회, 중위 순회, 후위 순회의 개념과 각 순회가 어떤 식으로 탐색하는지 이해합니다.

  o

  • 전위 순회 (preorder traverse)
    : 텍스트가장 먼저 루트 노드(A)를 탐색한다.
    루트에서 시작하여 왼쪽의 노드들을 순차적으로 탐색한 뒤,
    왼쪽 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
    이는 부모 노드가 제일 먼저 탐색되는 순회 방식이다.
    주로 트리를 복사할 때 사용된다.
    

  • 중위 순회 (inorder traverse)
    : 제일 먼저 왼쪽 끝에 있는 노드(H)부터 탐색하기 시작하여,
    루트를 기준으로 왼쪽에 있는 노드의 탐색이 끝나면,
    루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
    즉, 루트를 가운데에 두고 탐색한다.
    이는 부모 노드가 서브 트리의 탐색 중간에 탐색되는 순회 방식이다.
    주로 이진 탐색 트리의 오름차순으로 값을 가져올 때 사용된다.
    
    
    

  • 후위 순회 (postorder traverse)
    : 가장 먼저 제일 왼쪽 끝에 있는 노드(H)부터 탐색하기 시작하여,
    루트를 거치지 않고 오른쪽으로 이동하여 탐색한 뒤,
    루트를 가장 마지막에 탐색한다.
    이는 자식 노드가 먼저 삭제 되어야 상위 노드를 삭제할 수 있기 때문에
    주로 트리를 삭제할 때 사용된다.
    
    

• 전위 순회, 중위 순회, 후위 순회가 어느 상황에서 사용되는지 이해합니다.

  o

• 그래프의 개념과 구조, 표현 방식에 대해 이해합니다.

  o
  그래프는 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조다.
  직접적인 관계가 있는 경우, 두 점 사이를 이어주는 선이 있다.
  간접적인 관계라면, 몇 개의 점과 선에 걸쳐 이어진다.
  여기서 하나의 점을 그래프에서는 정점(vertex)라고 하고,
  하나의 선은 간선(edge)라고 한다.

  그래프에서 자주 사용되는 용어는 아래와 같다.

  • 정점 (vertex)
    : 노드(node)라고도 하며, 데이터가 저장되는 그래프의 기본 원소다.
  • 간선 (edge)
    : 정점을 이어주는 선으로 정점 간의 관계를 나타낸다.
  • 인접 정점 (adjacent vertex)
    : 하나의 정점에서 간선에 의해 직접 연결된 정점을 의미한다.
  • 가중치 그래프 (weighted graph)
    : 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀 있는 그래프
  • 비 가중치 그래프 (unweighted graph)
    : 열결의 강도가 적혀 있지 않는 그래프
  • 무향(무방향) 그래프 (undirected graph)
    : 왕복이 가능한 양방향 간선으로 표현할 수 있는 그래프로
    내비게이션이 대표적인 무향 그래프다.
  • 진입차수 (in-degree), 진출차수 (out-degree)
    : 한 정점에 진입(들어오는 간선)하고,
    진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
  • 인접 (adjacent)
    : 두 정점 간에 간선이 직접 이어져 있다면, 이 두 정점은 인접한 정점이다.
  • 자기 루프 (self loop)
    : 정점에서 진출하는 간선이 다른 정점을 거치지 않고
    바로 자기 자신에게 진입하는 경우, '자기 루프를 가졌다'라고 표현한다.
  • 사이클 (cycle)
    : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면,
    '사이클이 있다'라고 표현한다.

• 매트릭스(행렬)와 리스트의 장단점에 대해 이해합니다.

  o

  인접 행렬
  : 두 정점을 바로 이어주는 간선이 있다면, 이 두 정점은 '인접하다'고 한다.
  인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로
  2차원 배열의 형태로 나타낸다.
  만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true),
  이어져 있지 않다면 0(false)으로 표시한 일종의 표다.
  만약 가중치 그래프라면, 1 대신 관계에서 의미 있는 값을 저장한다.
  
  위의 그래프는 다음과 같이 행렬로 표현할 수 있다.
  

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

• 그래프의 실제 사용 예제를 보고, 어떤 식으로 그래프가 사용되는지 이해합니다.

  o
  포털 사이트의 검색엔진, SNS에서 사람들과의 관계, 내비게이션 등에 사용된다.
  세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져있다.

• 직접 구현한 그래프를 구현하는 데 필요한 것이 무엇이었는지 이해하고, 로직을 파악합니다.

  o

• 너비 우선 탐색과 깊이 우선 탐색의 개념과 특징에 대해 이해합니다.

  o
  너비 우선 탐색(BFS, Breadth-First Search)
  : 루트 노드를 기준으로 찾고자 하는 노드(정점)까지 가는 방법을
  가까운 정점부터 탐색하는 방법.
  더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 탐색한다.
  즉, 너비(→)를 먼저 탐색하는 방법으로 두 정점 사이의 최단 경로를 찾을 때 사용한다.

  깊이 우선 탐색(DFS, Depth-First Search)
  : 하나의 경로를 끝까지 탐색한 수, 찾는 값이 아니라면, 다음 경로로 넘어가 탐색한다.
  하나의 경로를 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에 운이 좋다면
  금방 경로를 찾을 수 있지만, 그렇지 않은 경우 시간이 오래 걸릴 수도 있다.
  즉 깊이(↓)를 먼저 탐색하는 방법으로 한 정점에서 시작하여
  다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.

  따라서 BFS는 시작 노드에서부터 인접한 모든 노드를 탐색하면서,
  한 단계씩 깊이를 늘려가는 방식이다.
  즉 노드를 적게 방문하고 빠르게 탐색할 수 있다.
  BFS는 목표 노드가 근처에 있는 경우에 유용하다.

  BFS의 동작 방식은 큐(Queue)를 사용하여 구현할 수 있다.
  시작 노드를 큐에 넣고, 큐에서 하나씩 노드를 꺼내면서
  해당 노드의 인접한 노드들을 큐에 추가하는 방식으로 진행된다.

  DFS는 한 경로를 끝까지 탐색한 후, 다른 경로로 탐색하는 방식이다.
  DFS는 스택(Stack)이나 재귀 함수를 통해 구현될 수 있다.

1. 시작 노드를 선택한다.
2. 선택한 노드를 방문했다고 표시하고, 해당 노드와 연결된 아직 방문하지 않은
   인접한 노드 중 하나를 선택한다.
3. 선택한 노드로 이동하여 2단계를 반복한다.
   선택한 노드를 방문했다고 표시하고, 해당 노드와 연결된 아직 방문하지 않은
   인접한 노드 중 하나를 선택한다.
4. 만약 더 이상 방문하지 않은 인접한 노드가 없다면,
   이전 단계로 돌아가서 방문하지 않은 다른 노드를 선택한다.
   이전 단계로 돌아가기 위해 스택을 활용하거나 재귀 함수를 호출한다.
5. 스택이 비어있을 때까지 반복한다.

   DFS는 깊은 경로를 먼저 탐색하기 때문에,
   규모가 크고 깊이가 깊은 그래프에서는 탐색 시간이 길어질 수 있다.
   또한, 최단 경로를 보장하지 않는다.
   따라서 BFS와는 달리 DFS는 더 깊은 경로로 들어가기 때문에
   규모가 크고 깊이가 깊은 그래프에서는 비효율적일 수 있다.
   그러나 DFS는 메모리 사용량이 비교적 작고,
   목표 노드가 깊은 곳에 위치해 있는 경우에 유용할 수 있다.
   또한, 그래프의 탐색 순서가 중요한 경우에도 DFS를 활용할 수 있다.

   DFS는 백트래킹, 그래프 순회, 연결 요소 찾기, 사이클 검사 등
   다양한 그래프 문제에서 사용된다.

• 너비 우선 탐색과 깊이 우선 탐색의 장단점에 대해 파악합니다.

  o
  Q) 왜 최단 경로를 찾을 때 BFS 방식을 사용할까?
  한 경로를 끝까지 모두 다 탐색하는 처음 발견한 답이 최단 거리가 아닐 수 있지만,
  BFS는 현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중
  가장 먼저 발견한 해답이 최단거리라는 보장이 되기 때문이다.

  반면, 정확도를 높이고 싶을 때는 DFS 방식을 사용한다.
  BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있기 때문이다.

• 그래프가 매우 크다면 어떤 탐색 기법을 고려해야 하는지 이해합니다.

  o

• 그래프의 규모가 작고 depth가 얕다면 어떤 탐색 기법을 고려해야 하는지 이해합니다.

  o
  규모가 작고 깊이가 얕은 그래프의 경우,
  보통 너비 우선 탐색(BFS, Breadth-First Search)이 가장 효율적인 탐색 기법이다. 그 이유로는 다음과 같다.

1. BFS는 최단 경로를 보장한다.
   BFS는 너비 우선으로 탐색하면서 노드를 방문하기 때문에,
   시작 노드와 가장 가까운 노드부터 순차적으로 탐색한다.
   만약 목표 노드가 시작 노드와 근처에 있는 경우,
   BFS는 빠르게 목표에 도달할 수 있다.

2. BFS는 탐색에 필요한 메모리 사용량이 적다.
   BFS는 큐를 사용하여 탐색하므로, 탐색하는 노드를 메모리에 보관해야 한다.
   그러나 규모가 작은 그래프의 경우, BFS는 인접한 노드들을 빠르게 탐색하므로
   메모리 사용량이 크게 증가하지 않는다.

3. BFS는 탐색 시간이 예측 가능하다.
   BFS는 모든 인접 노드를 순차적으로 탐색하므로,
   그래프의 크기에 따라 탐색 시간이 선형적으로 증가한다.
   따라서 규모가 작고 깊이가 얕은 그래프에서는 탐색 시간을 예측하기 쉽다.

   따라서 규모가 작고 깊이가 얕은 그래프에서는 BFS를 선택하는 것이 더 효율적이다.
   그러나 상황에 따라 DFS가 더 적합한 경우도 있을 수 있으므로,
   탐색의 목적과 그래프의 구조에 따라 적합한 탐색 기법을 선택하는 것이 중요하다.

• 추가학습
  대표적인 자료구조 외에도 다양한 자료구조들이 존재하고 있다. (환형 큐, 리스트 등)
  해당 자료구조들을 직접 찾아서 정리하고, 자료구조들이 어디에 사용되는지 스스로 학습을 해본다.

• 추가학습
  다음의 질문에 대한 답을 고민해 본다.
  Q. DFS와 BFS의 장단점은 또 무엇이 있을까?
  Q. 그래프가 매우 크다면 어떤 탐색 기법을 고려해야 할까?
  Q. 반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까?

소감

🔡➡️💻➡️🤓👍
개념 이해는 어렵지 않았지만, 이를 토대로 코드로 구현하는 것은 정말 어려웠다.
솔로 프로젝트가 내일부터 시작인데 오늘 안에 다 코플릿을 풀 수 없을 것 같아서
이번주 내내 하루에 하나씩이라도 풀어봐야겠다.