트리(Tree) | 세그먼트 트리 Segment Tree (알고리즘) 정리
세그먼트 트리 (Segment Tree) | 인덱스 트리 (Index Tree) 세그먼트 트리 주어진 데이터들의 (구간 합) (데이터 업데이트) 가 함께 일어나거나, (최대, 최소) 를 구할 때 빠르게 수행하도록 고안해낸 자료구조이다. → 더 큰 범위를 ‘인덱스 트리’ 라고 말하기도 한다. [1] 세그먼트 핵심 1) 데이터 초기화하기 a) tree 배열 크기 선언 b) 단말 노드에 arr 원본 배열 초기화 c) setTree로 단말노드 위의 부모노드들을 자식 노드 활용해 세팅 2) 질의값 계산하기 | 구간합, 구간 곱, (구간 안의 최소값, 최대값), 데이터 갱신 등의 질의 질의는 보통 여러 가지가 있는데, 구간 합부터 들어보겠다. 질의값 계산 시에는 원본 idx를 트리의 idx로 맞춰주는 게 중요하다...
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 14.
트리(Tree) | 트리, 트라이, 이진트리 비교
코딩테스트에서의 Tree 문제 분류 1) 그래프로 푸는 Tree 트리도 특수한 그래프 형태의 하나이기 때문에 노드, 간선 정보가 주어질 수 있다. 이 경우, 인접리스트 형태로 트리를 표현하고, 그에 맞는 그래프 처리 (ex. DFS/BFS) 풀이 2) Tree 만을 위한 문제 보통 1차원 배열로 트리를 표현한다. 이진트리, 세그먼트 트리, LCA(최소 공통 조상) 1. 트리 (Tree) (1) 트리 Tree : 노드-에지로 연결된 그래프의 특수한 형태 (2) 특징 사이클 X, 루트 노드 1개 루트노드 제외한 모든 노드들은 단 1개의 부모 노드만 갖는다. 트리의 부분 트리(=서브트리) 역시 같은 특징을 따른다. (3) 트리의 구성 요소 2. 트라이 (Trie) (1) 트라이 (Trie) ; 문자열 검색 빠..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 9.
MST | 최소 비용 신장 트리 (MST) 개념 간략한 정리
신장 트리 : n개 정점 무방향 그래프에서 간선 n-1개 부분 그래프 최소 비용 신장 트리 그래프에서 모든 노드 연결 시 사용하는 엣지 가중치 합 최소로 하는 트리 n개 정점 갖는 무방향 그래프에서 모든 노드를 연결한 신장 트리 구성할 때 간선 가중치 합 최소인 트리 MST는 엣지 가중치 최소를 사이클 없고, 단절점 없이 만드는 게 목표다. 에지를 기준으로 하는 알고리즘 [최소 비용 신장 트리 조건] 정점 n개 간선 n-1개 사이클 X : 사이클 포함 시 가중치 합이 최소가 될 수 없으므로 뺀다. 단절점 없는 (연결 그래프) → 최소비용 신장트리를 구현할 알고리즘의 종류 1) 크루스칼 (Kruskal) 알고리즘 모든 간선 가중치 오름차순 정렬 후, 모든 정점이 연결될 때까지 계속해서 작은 가중치를 사이클..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 24.
최단 경로| 다익스트라, 벨만포드, 플로이드 비교
최단 경로 알고리즘 1) 다익스트라 : one-to-all (가중치는 양수만) 2) 벨만-포드 : ont-to-all (가중치 음수도 가능, 음수 사이클 여부 판단 시 多 사용) 3) 플로이드 : all-to-all 1) 다익스트라 (dijkstra) 알고리즘 | One-to-One 출발 노드→ 다른 모든 노드로의 최단 거리 구하는 알고리즘 특징은 엣지 (가중치)가 모두 양수 시간 복잡도 : O(E logV) → 특정 노드 (1개)에서 다른 노드들(all)에 대한 최단 거리 구하라는 문제가 주어졌을 때 ‘다익스트라’를 떠올려라 ⬛ 다익스트라 알고리즘 수행 과정 1) 인접 리스트로 그래프 표현 2) 최단 거리 distance[] 1차원 배열 선언 → 최초 초기화 시 Integer.MAX_VALUE로 초기화..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 13.
DP 알고리즘 | LCS (최장 길이 공통 부분 수열)
LCS (Longest Common Subsequence) 두 개의 문자열 X, Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자열을 찾고자 한다. 부분 문자열 길이가 최대가 되도록 부분 문자열 찾는 방법은 ? LCS 는 두 개의 문자열 X, Y가 주어졌을 때 공통의 부분 문자열 길이 최대값을 찾는 문제다. X = ABDCDC Y = ACADC => 두 문자열 최장 길이 공통 부분 수열은 길이 4의 "ACDC " 가 된다. DP[i][j] 의 정의 : 각 위치 인덱스를 각각 마지막 문자로 포함하는 두 문자열의 LCS 길이값 즉, A[i]와 B[j] 를 기준으로 경우를 나눠 D[i][j]에 최장 길이를 갱신해줘야 한다. => D[i][j]에 올 수 있는 값의 경우는 크게 4가지로 나눌 수 있다...
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 11.
이분 탐색 | Parametric Search 에 대한 이론 비교
Binary Search | 이분 탐색 = 이진 탐색 = 이분 검색 정렬된 데이터에서 특정 값을 찾기 위해 (특정 범위)를 절반으로 줄여나가면서 중앙값과 비교해가며 빠르게 탐색하는 기법이다. Parametric Search | 파라메트릭 서치 이러한 이분 탐색의 응용을 Parametric Search 라고 부르다. 최적화 문제를 결정 문제로 환원하면 더 쉽게 풀 수 있다면 고려해봐라 (1) 예, 아니오 판단할 함수 만들고 (2) 판단 함수를 활용하여, 이분 탐색 범위를 좁혀가면서 타겟값을 구하는 거다. 1) 최적화 문제 : 여러 해답 중 기준에 따라 최소, 최대값 등을 구하는 문제 : f(i) = 1 이 되는 i의 최솟값을 구하라 2) 결정 문제 : 예 아니오로 답할 수 있는 문제 : 어떤 i에서 f(i..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 7.