트리 (Tree)트리는 노드들이 계층적으로 연결된 비선형적 자료구조로, 루트 노드와 부모-자식 관계의 서브트리들로 구성됨트리 구성 요소구성 요소설명노드데이터의 Index, value를 표현하는 요소에지노드와 노드 간의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드자식 노드두 노드 사이의 관계에서 하위 노드리프 노드트리에서 가장 하위에 존재하는 노드서브 트리전체 트리에 속한 작은 트리관련 개념차수 (degree): 각 노드가 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 함높이 (height): 루트 노드에서 가장 멀리 있는 리프 노드 까지의 거리레벨 (level): 트리에서 특정 노드의 깊이, 루트 노드는 레벨 0에..

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 간선들의 가중치 합을 최소로 하는 트리임📌 최소 신장 트리 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음`N개`의 노드가 있으면 MST를 구성하는 간선의 개수는 항상 `N-1개`핵심 이론1. 간선 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화MST는 데이터를 노드가 아닌 간선 중심(≒ 벨만 포드)으로 저장하므로 인접리스트가 아닌 간선 리스트의 형태로 저장edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성사이클 처리를 위한 유니온 파인드 배열도 선언 및 인덱스를 해당 자리의 값으로 초기화2. 그래프 데이터를 가중치 기준으로 정렬간선 리스트에 담긴 그래프를 데이터를 가중치 기준으로 오름..

벨만 포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같음기능특징시간 복잡도(노드: V, 에지: E)특정 출발 노드에서 다른 모든 노드까지의 최단 경로- 음수 가중치 간선이 있어도 수행- 음수 사이클의 존재 여부 판단 가능O(VE)핵심 이론벨만 포드 알고리즘은 다음 3단계의 원리로 동작1. 에지 리스트로 그래프 표현 및 최단 경로 배열 초기화벨만 포드 알고리즘은 간선을 중심으로 동작하므로 그래프를 간선 리스트로 구현또한 최단 경로 배열은 출발 노드는 0, 나머지는 무한대로 초기화2. 모든 에지를 확인해 정답 배열 갱신최단 거리 배열에서 갱신 반복 횟수는 노드 개수 -1∵ 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 간선의 최대개..

플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘임기능특징시간복잡도 (노드 수:V)모든 노드 간에 최단 경로 탐색음수 가중치가 있어도 수행 가능DP의 원리를 이용해 알고리즘에 접근O(V³)핵심 이론플로이드 워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정. 최단 경로 위에 k노드가 존재한다면, 그것을 이루는 부분 경로 역시 최단 경로라는 것.색칠된 경로가 `1→5`의 최단 경로라면, `1→4` 최단 경로와 `4→5` 최단 경로 역시 색칠된 경로로 이루어질 수 밖에 없음즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이루어진다는 의미이므로다음과 같은 점화식을 도출 가능 함.📌 도출한 플로이드 워셜 점화식D[S][E] = Math.m..

가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘단, 모든 간선의 가중치는 0 이상핵심 이론인접 리스트로 그래프 구현최단 거리 배열 초기화값이 가장 작은 노드 선택최단 거리 배열 업데이트3, 4 반복하여 최단 거리 배열 완성1. 인접리스트로 그래프 구현인접 행렬로 구현해도 좋으나 시간 복잡도 측면에서 N크기가 클 것을 대비해 인접 리스트로 구현하는 게 나음그래프의 연결을 표현하기 위해 배열의 자료형은 `(노드, 가중치)` 형태로 선언하여 연결2. 최단 거리 배열 초기화출발 노드는 0, 나머지 노드는 무한으로 초기화이때 무한은 적당히 큰 값을 사용3. 값이 가장 작은 노드 구하기최단 거리 배열에서 현재 값이 가장 작은 노드 선택, 처음에는 출발 노드를 선택하면 됨4. ..

위상 정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드 순서를 나열하는 알고리즘즉, 어떤 일을 하기 위해 선행되어야 할 작업들이 있을 때, 그 작업 수행 순서를 결정📌 사이클이 없는 방향 그래프여야만 위상 정렬 가능!핵심 이론위상 정렬은 다음가 같은 단계로 설명할 수 있음 각 노드의 진입 차수(in-degree)를 센다.진입 차수가 0인 노드들을 큐에 넣는다.큐에서 노드를 하나씩 꺼내어 결과에 넣고, 연결된 노드들의 진입 차수에서 1을 뺀다.새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.모든 노드를 처리하면 끝.진입 차수 저장 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 만큼 증가 (나머지 노드 동일)진입 차수 0인 노드 처리진입 차수가 ..

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘`union 연산`: 각 노드가 속한 집합을 1개로 합치는 연산a, b가 a ∈ A, b ∈ B일 때, union (A, B)는 A∪B 의미`find 연산`: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산a ∈ A일 때, find(a)는 A집합의 대표 노드 반환유니온 파인드 원리 이해유니온 파인드를 표현하는 일반적인 방법은 1차원 배열 이용처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨각 노드가 모두 대표 노드이므로 배열은 자신 인덱스 값으로 초기화2개의 노드를 선택해 각각의 대표 노드를 찾아 연결..

인접 행렬이나 인접 리스트를 사용하여 그래프를 저장하는 방식이 일반적이다.`암시적 그래프 (Implicit Graph)`는 명시적인 저장 방식 없이, 문제의 조건을 통해 그래프의 구조를 유추하며 탐색하는 방식이다.미로 탐색, 퍼즐 문제, 최단 거리 문제 등에서 자주 출제되며, 이를 효과적으로 해결하기 위해 반드시 이해해야 한다.암시적 그래프 개념암시적 그래프는 명시적으로 노드와 간선을 저장하지 않고, 탐색하면서 그래프 구조를 동적으로 유추즉, 탐색 과정에서 이동 가능한 정점과 간선을 문제의 조건을 기반으로 판별함예시)아래와 같은 미로가 있다고 가정`1`: 이동 가능`0`: 이동 불가능상하좌우로 이동겉보기에는 그래프로 보이지 않지만, 값이 1인 곳이 이동 가능(노드) 하다는 점과 상하좌우로 이동(간선)할 ..