TIL_210415

멜로디·2021년 4월 15일
0

Today I Learned

목록 보기
23/30

오늘 배운 것

  • Graph
  • Tree
  • Binary Search Tree
  • Search Algorithm

Graph

정의

컴퓨터 공학에서 사용하는 자료 구조 그래프는 수학적 그래프와 전혀 다른 형태를 갖는다.
거미줄처럼 여러개의 점들이 이어진 복잡한 네트워크와 같은 형태이다.

따라서, 컴퓨터 공학에서의 그래프를 한 문장으로 정의하면
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
라고 말할 수 있다.

용어

정점(vertex)
그래프의 각 포인트를 말한다.

간선(edge)
정점들을 잇는 선을 말한다.

서로 다른 정점들이 직접적인 관계를 갖고 있다면, 그 정점들은 직접 간선으로 이어져 있고
서로 다른 정점들이 간접적인 관계를 갖고 있다면 다른 여러 정점을 거쳐 이어져 있을 것이다.

가중치/비가중치 그래프
비가중치 그래프는 각 정점간의 연결 유무만을 판단하는 반면,
가중치 그래프는 더 자세한 정보를 담을 수 있다.
가중치 그래프가 확장되어 수백만개의 정점과 간선이 추가되면 내비게이션에서 사용하는 자료구조와 유사해진다.

무향그래프(undirected graph)
방향이 지정되지 않은 그래프.
반대로 단방향 그래프(directed graph)로 구현할 경우 그 방향에 맞는다면 조회나 제어가 가능한데, 그 반대 방향이라면 불가능하다.

진입차수/진출차수
한 정점에 진입하고 진출하는 간선이 몇개인 지 나타낸다

인접
두 정점 간에 간선이 직접 이어져 있는 상태

자기 루프
정점에서 진출한 간선이 다른 정점을 거치지 않고 곧바로 자기 자신에게 다시 진입하는 경우

사이클
한 정점에서 출발하여 다른 정점을 경유한 뒤 해당 정점으로 돌아갈 수 있는 상태

인접 행렬

정점들간의 인접함을 표시해 주는 행렬. 2차원 배열의 모습을 갖고 있다.
정점 간 인접하였을 경우 1, 인접하지 않았을 경우 0으로 표시하는 형태이며, 만약 가중치 그래프라면 0이나 1 대신 관계에서 의미 있는 값을 저장한다.

사용처

  • 두 정점 사이에 관계 유무를 확인하기에 용이
    (A에서 B로 진출하는 간선이 있는 지 파악하기 위해서는 [0][2]와 같은 방식으로 바로 확인할 수 있음)
  • 가장 빠른 경로를 찾고자 할 때 주로 사용됨

인접 리스트

각 정점이 어떤 정점과 인접한 지 리스트의 형태로 볼 수 있는 표현 방식.
각 정점마다 1개의 리스트를 갖으며, 이 리스트에는 자신과 인접한 다른 정점들이 적혀있다.

사용처

인접 행렬은 연결 가능한 모든 경우의 수와 정보를 저장하기 때문에 메모리를 많이 차지한다.
이 때문에 메모리를 효율적으로 사용하여야 할 때 인접 행렬 대신 인접 리스트를 사용한다.

Tree

그래프의 여러 구조 중 일방향 그래프의 한 구조로, 조직도와 비슷한 형태이다.

상위 데이터가 하위 데이터에 단방향으로 연결되는, 계층적 자료구조이다.
데이터를 순차적으로 나열시킨 선형 구조가 아닌,
하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이며,
계층적으로 표현되고 아래로만 뻗기 때문에 사이클이 없다.

용어


루트(root)
데이터가 시작되는 부분(최상위)을 말한다.
tree 구조에서는 모든 데이터가 루트에서 시작된다.

노드(node)
각 데이터들을 말한다. 그래프에서의 정점과 지칭하는 것이 같으나, 구조상 의미가 일부 다르다.

부모 노드(parent node)/자식 노드(child node)/리프 노드(leaf node)
상위 노드를 부모 노드라고 하고, 연결된 하위 노드를 자식 노드라고 한다.
자식이 없는 노드는 나뭇잎과 같은 형태라고 하여 리프 노드라고 부른다.

특징

이 자료 구조는 높이와 깊이를 측정할 수 있다.
노드와 노드의 거리를 레벨이라고 부르며, 첫 번째 노드인 루트를 Level 1로 설정한다.

  • 높이 : 루트부터 가장 안쪽의 노드까지의 레벨
  • 깊이 : 특정 노드부터 루트까지의 레벨
  • 형제 노드 : 같은 레벨에 나란히 있는 노드
  • 서브 트리 : 큰 트리의 내부에 트리의 모양새를 갖춘 작은 트리

Binary Search Tree

트리는 효율적 탐색을 위해 사용하기도 한다.
지금까지 각각의 특징을 추가한 새로운 트리가 다양하게 만들어졌고, 이 때문에 하나의 모습만 가지고 있는 것이 아닌, 특징에 따라 여러가지 이름으로 불리고 있다.
그 중 가장 간단하고 많이 사용하는 것은 이진 트리(binary tree)이진 탐색 트리(binary search tree)이다.

정의


이진 트리
자식 노드가 최대 2개인 노드들로 구성된 트리를 뜻한다

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

정 이진 트리
각 노드가 0개 혹은 2개의 자식 노드를 갖음

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

모든 왼쪽 자식들은 루트나 부모보다 작은 값
모든 오른쪽 자식들은 루트나 부모보다 큰 값

주의

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

이러한 문제를 해결하기 위해 삽입과 삭제시마다 트리의 구조를 재조정하는 알고리즘을 도입할 수 있음

Search Algorithm

Tree Traversal

어떠한 목적을 위해 트리의 모든 노드를 한번씩 방문하는 것을 트리 순회라고 한다.
계층적 구조 때문에 순회 방법으로 여러가지가 존재한다.

트리 순회 방법의 차이는 루트를 두는 기준에 따라 달라진다

주의 : 순회할 때의 순서는 항상 왼쪽부터 오른쪽으로 진행한다

전위 순회
루트를 가장 먼저 방문하고, 하향식으로 조회한다.
일반 사용자가 파일 시스템을 모두 방문하려고 할 때 사용하는 방식과 유사하다.

중위 순회
루트를 가운데에 두고 순회한다.
루트 기준 왼쪽 최하위 노드부터 방문하며,
왼쪽 노드들의 방문이 끝나면 루트를 거쳐 오른쪽의 노드들을 마저 방문한다.

후위 순회
루트를 마지막으로 방문한다.
루트 기준 왼쪽 최하위 노드부터 방문하며,
왼쪽 노드들의 방문이 끝나면 바로 오른쪽의 노드들을 방문하고,
오른쪽 노드들의 순회가 끝나면 제일 마지막으로 루트를 방문한다.

BFS/DFS

그래프의 탐색은 하나의 정점을 시작으로, 그래프의 모든 정점들을 한번씩 방문하는 것을 목적으로 한다.

그래프의 데이터는 배열처럼 정렬되어있지 않기 때문에, 원하는 자료를 찾을 때까지 하나씩 모두 방문한다.

BFS(Breadth First Search / 너비 우선 탐색)
가까운 정점들부터 우선 일괄적으로 탐색하고,
더는 탐색할 가까운 정점이 없을 때(원하는 결과가 나오지 않음)
그 다음 거리의 정점들을 일괄적으로 탐색한다
결과가 나올 때 까지 위 절차를 반복한다.

장점 두 정점 사이의 최단 경로를 찾기 용이하다
단점 최악의 경우 모든 경로를 다 살펴보게 될 수 있다

DFS(Depth First Search / 깊이 우선 탐색)
하나의 경로를 끝까지 탐색한 후,
해당 경로의 끝에서도 원하는 결과가 나오지 않았을 경우 다음 경로로 넘어간다.
결과가 나올 때 까지 위 절차를 반복한다.

장점 한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 수 있다
단점 BFS에 비해 시간이 오래 걸린다

profile
하루하루 배울때마다 기록하는 일기장

0개의 댓글