🍀TIL🍀[프로그래머스] Coding Test 스터디8

그래프

• 직접적인 관계 가 있는 경우 두 점 사이를 이어주는 선이 있다.

• 간접적인 관계 라면 몇 개의 점과 선에 걸쳐 이어진다.

• 그래프에서 하나의 점은 정점(vertex) 이라고 표현하며, 하나의 선은 간선(edge) 이라고 한다.

// 예시 코드 
/*
    1 == 서울, 2 == 부산, 3 == 대전
    0은 연결되지 않은 상태, 1은 연결된 상태 (간선을 정수로 표현)
*/

[1] = [0, 1, 1]// 서울 - 부산 , 서울 - 대전
[2] = [1, 0, 1]// 부산 - 서울 , 부산 - 대전
[3] = [1, 1, 0]// 대전 - 서울 , 대전 - 부산

💟그래프 관련 용어

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

• 간선 (edge)
  두 정점을 연결하며, 이들의 관계를 나타내는 선.

• 인접 정점 (adjacent vertex)
  간선에 의해 직접 연결된 정점을 의미

• 가중치 그래프 (weighted Graph)
  연결의 강도(추가적인 정보, 예시로 서울-부산으로 가는 거리)를 나타내는 그래프

• 비가중치 그래프 (unweighted Graph)
  연결의 강도를 표현하지 않는 그래프

• 무향(무방향) 그래프 (undirected graph)
  간선이 양방향을 가리키는 그래프.
  이 경우, 한 정점에서 다른 정점으로 이동하는 것과 반대로 이동하는 것 모두 가능하다.

  • 예시로 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능! 이게 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능할것이다. 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다는 것!

• 진입차수 (in-degree) / 진출차수 (out-degree)
  한 정점으로 들어오는 간선과 나가는 간선의 수

• 인접 (adjacency)
  두 정점이 직접 연결되어 있는 경우, 이들을 인접하다고 표현한다

• 자기 루프 (self loop)
  한 정점에서 시작해서 바로 그 정점으로 돌아오는 경로

• 사이클 (cycle)
  한 정점에서 시작해서 다시 그 정점으로 돌아오는 경로가 존재한다면, 이를 사이클이 있다고 말한다.
  내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프라고 할 수 있다.

🌳트리(Tree)🌳

그래프의 여러 구조 중 단방향 형태 중 하나로 하나의 뿌리에서 다양한 방향으로 가지가 뻗어 나가는 형태를 가지고 있다.

• 마치 가계도와 유사한 형태를 가지고 있는 계층적 자료 구조로서, 데이터가 바로 아래에 있는 하나 이상의 데이터와 무방향으로 연결된다.

• 데이터를 순차적으로 배열한 선형 구조와 달리, 하나의 데이터 아래 여러 데이터가 존재하는 비선형 구조이다.

• 계층적으로 하향식 구조로 표현이 되기 때문에 사이클이 존재하지 않는다.

• 트리 구조는 ‘루트(Root)‘ 라는 하나의 꼭짓점 데이터로 시작해 여러 개의 데이터를 ‘간선(Edge)‘ 으로 연결한다. 각 데이터는 ‘노드(Node)’ 라고 하며, 두 노드가 상하 계층으로 연결된 부모/자식 관계를 형성한다.

• 참고로, 자식 노드가 없는 노드는 나무의 잎과 같다해서 ‘리프 노드(Leaf Node)’이다.

💟트리의 특징

• 트리 자료 구조는 깊이, 레벨, 그리고 높이 를 측정할 수 있다.

• 깊이 (Depth)
  트리 구조에서 깊이 는 루트부터 특정 노드까지의 거리
  이때, 루트 자신의 깊이는 '0'이다.

• 레벨(Level)
  레벨 은 같은 깊이를 가진 노드의 집합 을 의미
  깊이가 0인 루트 자신의 레벨은 1이다.
  같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.

• 높이(Height)
  높이 는 리프 노드로부터 루트 노드까지의 거리
  부모 노드는 자식 노드의 가장 높은 높이 값에 1을 더한 값을 높이로 가진다.

  • 위의 예시에서, H, I, E, F, J의 높이와 D,G의 높이는 각각 0과 1. B와 C의 높이는 2이다. 이때 B는 D의 높이에서 1을 더한 값을 높이로 가지며, 같은 계산에 따라 루트 A의 높이는 3이된다.

• 서브 트리(Sub tree)
  트리 구조의 루트에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리

💟트리의 장점

1. 효과적인 계층 구조 표현
예를 들어, 회사에서 조직도를 작성할 때!

2. 정렬과 탐색에 활용 가능
이진 탐색 트리, 힙(Heap) 등과 같은 다양한 형태로 사용될 수 있으며, 정렬과 탐색을 위한 알고리즘을 구현하는 데에도 사용된다.

3. 삽입과 삭제가 용이함
노드의 삽입과 삭제가 쉽다. 이는 삽입 및 삭제 시에 해당 노드의 부모와 자식 노드만 수정하면 되기 때문!

4. 구조 파악의 용이함
시각화가 쉬우므로, 트리를 시각적으로 표현하여 이해하기 쉽다.

5. 다양한 분야에 활용 가능
다양한 문제를 해결하기 위한 다양한 알고리즘의 기초가 되기때문에 데이터베이스, 알고리즘 등 다양한 분야에서 활용된다.

💟트리와 그래프의 차이

이진 탐색 트리(Binary Search Tree)

이진 탐색의 속성이 이진 트리에 적용된 특별한 형태의 이진 트리

💟이진 탐색이란?

정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나

좀 더 자세히 설명하면,
오름차순으로 정렬된 데이터를
같은 크기의 두 부분으로 나눈 후,
두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘이다.

💟이진 탐색 방법

1. 전체 데이터에서 중간값을 찾아 내가 찾고자 하는 값이 있는지 확인한다.

2. 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 데이터에서 중간값보다 큰 값인지 작은 값인지 판단 (Up? Down?)

3. 찾고자 하는 값이 중간값보다 작은 값일 경우, 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 설정하고 탐색을 반복 수행
   찾고자 하는 값이 중간값보다 큰 값일 경우, 데이터의 중간값의 다음 값부터 맨 마지막까지를 탐색 범위로 잡고 탐색을 반복 수행

이진 탐색 트리는 이러한 이진 탐색의 원리를 이진 트리에 적용한 것.

💟이진 탐색 트리의 특징

트리의 루트 노드는 전체 데이터의 중간값에 해당하며, 루트 노드의 왼쪽 서브 트리는 모두 루트 노드 값보다 작은 값들로, 오른쪽 서브 트리는 루트 노드 값보다 큰 값들로 이루어져 있다.

• 각 노드는 중복되지 않는 키(Key)를 가진다. 이 키(Key)는 각 노드에 저장된 값이다.

• 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 가진 노드들로 이루어져 있으며, 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 가진 노드들로 이루어져 있다.

• 각각의 서브 트리도 모두 이진 탐색 트리의 속성을 가진다.

인접행렬

인접 행렬은 서로 다른 노드들이 어떻게 인접해 있는지를 보여주는 2차원 배열

즉, A 노드와 B 노드가 연결되어 있다면 1(true)로 표시하고, 연결되어 있지 않다면 0(false)로 표시하는 표!
(가중치가 존재하는 그래프라면 1 대신 관계의 의미를 나타내는 값이 저장된다)

• 인접 행렬은 본질적으로 큰 표와 같은 형태로, 이는 두 개의 정점 간의 연결 여부를 확인하는데 매우 유용하게 사용된다.

  • ex. A에서 B로 이동하는 경로가 있는지를 알고자 한다면, 단순히 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

인접리스트

그래프의 정점 간 연결을 리스트 형식으로 표현하는 방식

• 각 정점이 어떤 다른 정점들과 연결되어 있는지를 알기 쉽게 해준다.

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

• 인접 행렬은 모든 가능한 연결을 저장하므로, 메모리 사용량이 높게 나타날 수 있는 반면, 인접 리스트는 실제 연결만을 저장하기 때문에 메모리 사용이 더 효율적 이다.

위에서 본 그래프를 인접 리스트로 표현하면 아래 그림과 같다.

graph = [
    [2, None],
    [0, 2, None],
    [0, None]
]