1. Graph
자료구조의 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있다
그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다
직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다
하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다
인접행렬 : 간선정보 가 들어오고 그걸 인접행렬에 기록한다
두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다
만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다
만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다
인접 행렬은 언제 사용할까?
한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기 쉽다
예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있고
가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용한다
1) 무방향 그래프
1번 노드에서 2번 노드로 2번에서 1번노드로 가는 것이 전부 가능하다
그래프는 G(V,E)로 표현한다
정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
간선 (edge): 정점 간의 관계(정점을 이어주는 선)
위의 그래프가 입력으로 들어올때
//정점의 갯수 , 간선의 갯수
5 5
// 간선정보
1 2
1 3
2 4
3 4
2 5
위의 그래프를 인접행렬 2차원 배열로 표현 할 수 있다
처음에는 0으로 초기화 시켜놓은 뒤
1과 2가 연결되어 있다면 1행 2열 , 2행 1열 둘다 1로 체크 해주면 된다
const graph = Array.from(Array(5), ()=> Array(5).fill(0))
1 2 3 4 5 // 노드번호
1 [0, 1, 1, 0, 0 ]
2 [1, 0, 0, 1, 1 ]
3 [1, 0, 0, 1, 0 ]
4 [0, 1, 1, 0, 0 ]
5 [0, 1, 0, 0, 0 ]
graph[a][b] = 1;
graph[b][a] = 1;
이런식으로 표현 할 수 있고
1행을 탐색할때 1로 체크된 부분만 1과 연결 되었다고 알 수 있다2) 방향 그래프
이동하는 방향이 정해져 있을때
2차원 배열을 만들고 이동할 수 있는 방향에 따라서 간선정보가 들어온다
a b
1 2
1 3
3 4
4 2
2 5 1 2 3 4 5 // 노드번호
1 [0, 1, 1, 0, 0 ]
2 [0, 0, 0, 0, 1 ]
3 [0, 0, 0, 1, 0 ]
4 [0, 1, 0, 0, 0 ]
5 [0, 0, 0, 0, 0 ]
graph[a][b] = 1;
이런식으로 표현 할 수 있고
행 -> 열 으로 이동한다
1행을 탐색할때 1로 체크된 노드만 1에서 이동할 수 있다고 알 수 있다3) 가중치 그래프
방향그래프에 간선에 가중치 값이 있는 것이다
1에서 2로 이동할 때 비용이 2 들어간다 이런식으로 표현할 때 사용한다
1에서 2로 이동하는데 가중치는 2
a b c
1 2 2
2 5 5
1 3 4
4 2 2 1 2 3 4 5 // 노드번호
1 [0, 2, 4, 0, 0 ]
2 [0, 0, 0, 0, 5 ]
3 [0, 0, 0, 0, 0 ]
4 [0, 2, 0, 0, 0 ]
5 [0, 0, 0, 0, 0 ]
graph[a][b] = c
이런식으로 표현 할 수 있고
행 -> 열 으로 이동한다
1행을 탐색할때 2열에 2가 적혀있으므로
1에서 2로 이동할 때 2의 가중치 값이 들어간다 라고 이해할 수 있다2. Tree
몇가지 제약이 있는 방향그래프의 일종이다
정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다
하나의 루트에서 하위로 뻗어 나가는 구조이다
트리 용어
가장 위에 존재하는 정점을 루트
각 정점은 노드, 자식이 없는 정점을 리프노드라고 부른다
트리에는 레벨이 존재하는데 레벨은 루트로부터 몇번째 깊이인지 표현할때 쓰인다
한 정점에서 뻗어 나가는 간선의 수를 degree 혹은 차수라고 부른다
트리의 사용
가지를 뻗어나가는 모양새를 가지는 조직도, 파일구조 , 대진표 등등에서 사용된다
조직도
파일 구조
트리의 특징
루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다
정점이 n개인 트리는 반드시 n-1개의 간선을 가진다
루트에서 특정 정점으로 가는 경로는 하나만 존재한다
3. 이진트리
각 정점이 최대 2개의 자식을 가지는 트리
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다
이진트리
각 노드가 0 개 혹은 2 개의 자식 노드를 갖는다
완전 이진 트리
마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져있어야 한다
포화 이진 트리
정 이진 트리이면서 완전 이진 트리이다 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리
편항트리
한 방향으로만 정점이 이어진다
이진트리 특징
이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고,
모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있는데 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 도 있다
이진트리 js 구현
이진트리 배열로 구현
// 정점 찾기
// 0 번 인덱스는 편의를 위해 비워둠
// left = index * 2
// right = index * 2 +1
// parent = floor(index / 2)
const tree = [
undefined;
// 1
9,
// 1*2, 1*2+1
3, 8
// 2*2, 2*2+1, 3*2, 3*2+1
2, 5, undefined, 7,
// 4*2, 4*2+1, 5*2, 5*2+1
undefined, undefined, undefined, 4
]