본문 바로가기

알고리즘 코딩테스트

[D-8] 🤔세그먼트 트리 📍 세그먼트 트리✅ 정의주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태를 말한다.더 큰 범위는 인덱스 트리라고 부른다. ✅ 핵심 이론세그먼트 트리의 종류 : 구간 합, 최대 및 최소 구하기구현 단계 : 트리 초기화 하기, 질의값 구하기(구간 합 또는 최대 및 최소 구하기), 데이터 업데이트하기 ✅ 수행 과정1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.트리 배열의 크기를 구하는 방법은 2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의한다.리프 노드를 제외한 나머지 노드의 값을 채운다(2^k -1부터 1번쪽으로 채운다.). 샘플 데이터{5, 8, 4, 3, 7, 2, 1, .. 더보기
[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 집합의 대표 노드를 반환한다. 더보기

티스토리툴바