코딩 알고리즘

Union-Find 자료구조는 \*\*서로소 집합(Disjoint Set)\*\*을 표현하고 관리하는 데 유용한 알고리즘이다. 보통 동일한 그룹에 속하는 요소들 간의 연결 여부를 효율적으로 확인할 때 사용된다.대표적인 활용 사례는 다음과 같다:그래프에서 사이클 검출:

BST는 왼쪽 자식 노드 < 현재 노드 < 오른쪽 자식 노드의 조건을 만족하는 이진 트리이다.모든 서브트리도 BST이어야 한다.BST를 중위 순회(in-order) 하면 오름차순으로 정렬된 노드 값을 얻을 수 있다.오른쪽 → 루트 → 왼쪽 순으로 탐색내림차순

해당 글은 SortedList 가 아닌 방식으로 최소값과 최댓값을 트래킹하는 자료구조를 다릅니다.해당 알고리즘의 기본적인 원리는 두개의 모노토닉 큐를 이용해 가능한 최대, 최소값의 인덱스를 저장해 O(1) 의 속도로 주어진 배열에서 최소값과 최대값을 찾고 그 사이즈또한

DFS로 방향 그래프를 탐색하면서 노드를 세 가지 상태로 색칠한다고 하자.하얀색: 아직 DFS 탐색을 시작하지 않은 노드회색: DFS 탐색을 시작했지만, 아직 그 노드에서 출발하는 모든 경로 탐색이 끝나지 않은 노드즉, 현재 DFS 호출 스택에 있는 노드검은색: 그 노

범용 세그트리 코드

사이클이 없고 루트가 존재하는 트리에 대해 두 정점의 가장 가까운 조상을 의미한다.예를 들어 해당 트리에서 11과 2의 LCA는 7이다.일단 그래프에 DFS를 돌려 모든 정점의 깊이를 구한다.두 정점의 깊이를 비교해 깊이가 깊은쪽을 parent로 올려 동일하게 맞춘다.

보통 두 문자열의 동일성 유무 비교는 O(N) 시간복잡도가 들기 마련이다.만약 문자열을 적절히 해싱할수 있다면 정수와 정수간의 비교로 변환해 O(1)이 될 것이다.롤링해시의 값의 표현은 다음과 같다.Ex. 문자열 "ABCD"에 대해 각 A, B, C, D 는 ascii

z-algorithm이란 특정 문자열 s에 대해까지의 모든 부분 문자열에 대해 s와 비교시 가장 긴 prefix를 각각 다 찾는 알고리즘이다.단순하게 생각하면 각각의 suffix에 대해 직접 문자열을 비교하면 된다.예를 들어 s = "ababa" 라고 해보자.따라서 z

만약 우리가 2, 5, 7의 배수로 이루어지고 제일 큰 값이 n을 넘지 않는 집합의 크기를 구해야 한다고 가정한다.n을 넘지 않는 선에서2의 배수의 갯수를 더한다.5의 배수의 갯수를 더한다.7의 배수의 갯수를 더한다.다만 여기서 겹치는 부분은 중복해서 세어졌기 때문에