알고리즘 공부방

트리에서의 지름이란, 트리에서 가장 멀리 떨어진 두 점 사이의 거리를 구하는 문제이다. 2가지 솔루션이 있고, 2개 모두 알아두도록 하자. SOL 1) 전체적인 알고리즘은, 1. 임의의 한 점으로부터 제일 멀리 떨어진 점을 잡고, (A) 2. 그 점으로부터 제일 멀리 떨어진 점을 잡는다. (B) 이때 A, B는 지름을 구성하는 요소이다. => dfs 2번으로 답을 구한다. 더보기 만약 A가 지름을 구성하는 두 점중 하나가 맞다면 2는 자명하다. 따라서 A가 지름을 구성하는 점임을 보여 보자. (귀류법) 임의의 정점에서 제일 멀리 떨어진 점 X를 잡았는데, 그 점이 지름 A, B 모두 아니라 하자. 위 그림에서 루트 R과 제일 멀리 떨어진 점 X를 골랐다 하자. (X!=A, X!=B) 1. 지름이 루트를 ..

엄청나게 중요한 자료구조인 세그먼트 트리에 대하여 알아보고 가자. 세그먼트 트리의 목적은 구간에 대한 질의와 수정을 빠르게 하는 것이다. 아이디어는 다음과 같다. 구간 트리의 루트는 배열의 전체 구간인 [1, n]을 표현하며, 그 왼쪽 노드는 [1, mid], 오른쪽 노드는 [mid+1, n]을 포함하게 함으로서 재귀적으로 구간에 대한 정보를 이진 트리에 저장한다. 만약 구간에 대한 쿼리가 떨어진다면 그 쿼리의 구간에 해당하는 노드들을 몇개 잡아 그 그 부분에 대해서만 계산하면 된다. 세그먼트 트리 자체의 원리에 대한 자세한 내용은 다른 블로그나 종만북을 복습하도록 하고, 구현과 시간복잡도에 초점을 맞춰 보자. *세그먼트 트리의 이론 및 구현 : https://www.acmicpc.net/blog/vie..

우선, $O(N^2)$ DP 풀이부터 살펴 보자. $dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이 $dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다. 여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1000; const int INF = numeric_limits::max(); const int NEGINF = ..

카라츠바 알고리즘의 간략한 설명이다. 원래 $a \times b$를 할 때 시간복잡도는 $O(N^2)$이다. (a, b의 길이는 모두 $N$) 이를 Divide & Conquer 로 줄일 수 있는데, 편의를 위하여 $N=20$이라 하자. 구현이 젤 중요하다. 1. LIM : 어느정도 이상은 카라츠바의 상수가 매우 크기 때문에 $O(N^2)$의 곱셈이 유리하다. 나는 이를 1000정도로 설정했다. 2. CUT : 이게 젤 중요하다. 그냥 각 자리 수를 벡터에 넣고 카라츠바를 돌리면 $O(N^{log3})$ 에 300,000을 넣은 값으로 10초 정도 걸려야 답이 나온다. 하지만 8자리씩 묶어서 넣으면 그만큼 N이 줄어듬으로 훨씬 낫다. 나는 이를 1e8정도로 설정해서 1억 진법을 따랐다. 3. 포인터 주고..