알고리즘 썸네일형 리스트형 [D-9] 이진 트리 📍 이진 트리(binary tree)✅ 정의각 노드의 자식 노드(차수)의 개수가 2이하로 구성돼 있는 트리를 말한다.트리 영역에서 가장 많이 사용되는 형태이다. ✅ 종류편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 이진 트리를 말한다.포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리를 말한다.완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리를 말한다. 완전 이진 트리 : 일반적으로 코딩 테스트에서 데이터를 트리에 담을 때 사용한다.편향 이진 트리 : 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다. ✅ 순차 표현이진 트리의 가장 직관적이면서 편리한 트리 자료구조 형태는 바로 '배열'이다.코딩 테스트에서 .. 더보기 [D-10] 트리 알아보기 & 트라이 📍 트리(tree)트리(tree)는 노드와 에지로 연결된 그래프의 특수한 형태이다. ✅ 특징순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다. ✅ 구성 요소구성 요소설명노드데이터의 index와 value를 표현하는 요소에지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드 (자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 트리✅ 트리의 부모 찾기_백준117251. 인접 리스트.. 더보기 [D-11] 최소 신장 트리 📍 최소 신장 트리✅ 정의최소 신장 트리(minimum spanning tree)란그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리를 말한다.✅ 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.(내부에 유니온 파인드 알고리즘 구현 필수)N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. ✅ 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기2. 그래프 데이터를 가중치 기준으로 정렬하기3. 가중치가 낮은 에지부터 연결 시도하기4. 과정 3 반복하기5. 총 에지 비용 출력하기 1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기- 에지 중심으로 저장하는 최소 신장 트리는 .. 더보기 [D-12] 🤔벨만-포드 & 플로이드-워셜 📍벨만-포드✅ 정의벨만-포드(bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.음수 사이클을 판별하는 문제가 더 빈번하게 출제된다. ✅ 특징특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다.음수 가중치 에지가 있어도 수행할 수 있다.전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.시간복잡도는 O(VE)이다. ✅ 핵심 이론1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기2. 모든 에지를 확인해 정답 배열 업데이트하기3. 음수 사이클 유무 확인하기 1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기- 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다.- 최단 경로 배열은 출발 노드는 0,.. 더보기 [D-13] 다익스트라 📍 다익스트라✅ 정의다익스트라(dijjkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하다. (출발-도착 노드 간의 최단거리가 아니다.)✅ 특징- 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.- 에지는 모두 양수이다.- 시간 복잡도는 O(ElogV)이다.(노드 수 : V, 에지 수 : E) ✅ 핵심 이론1. 인접 리스트로 그래프 구현하기2. 최단 거리 배열 초기화하기3. 값이 가장 작은 노드 구하기4. 최단 거리 배열 업데이트하기5. 과정 3~4를 반복해 최단 거리 배열 완성하기1. 인접 리스트로 그래프 구현하기- 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현한다.- 그래프의 연결을 표현하기 위해 .. 더보기 [D-14] 위상 정렬 📍 위상 정렬✅ 정의위상 정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. ✅ 핵심 이론항상 유일한 값으로 정렬되지 않는다.사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다. ✅ 정렬 원리1. 진입차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다.ArrayList로 표현한 그래프이다.다음의 그래프는 사이클이 없는 상태이다. 진입 차수 배열 D를 업데이트한다.다음은 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가시킨 배열의 결과이다.2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.인접 리스트에서 선택된 노드가 가리키는 노드들의 진.. 더보기 [D-15] 유니온 파인드 📍 유니온 파인드✅ 정의유니온 파인드(union-find)는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘을 말한다. ✅ 핵심 이론union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b가 b ∈ B일 때 union(a, b)는 A∪B를 말한다. find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 더보기 [D-16] 그래프의 표현 - 에지 리스트 & 인접 행렬 & 인접 리스트 📍 그래프노드와 에지로 구성된 집합을 말한다.노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다.여러 알고리즘에서 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다. ✅ 에지 리스트에지 리스트(edge list)는 에지를 중심으로 그래프를 표현한다.에지 리스트는 배열에 출발 노드와 도착 노드를 저장하여 에지를 표현하다.출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.벨만 포드나 크루스칼(MST) 알고리즘에 사용하며, 노드 중심 알고리즘에서는 잘 사용하지 않는다. ✅ 에지 리스트로 가중치 없는 그래프 표현하기가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer형.. 더보기 이전 1 2 3 4 다음
