컴퓨터하는 kimmessi

LCA(최소 공통 조상)이란? 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다. 동작 과정 1. 최소 공통 조상을 찾을 두 노드를 확인한다. 2. 먼저 두 노드의 깊이를 같게 만들기 위해 깊이가 더 큰 쪽이 작은 쪽의 깊이에 맞게 거슬러 올라간다. 3. 부모가 같아질 때까지 계속 거슬러 올라간다. 4. 이 과정을 계속 반복해준다. 알고리즘 사례 예를 들어, 이러한 트리가 있다고 가정하자, 이 때, 트리의 노드들의 깊이는 각각 다음과 같다. 6번 노드와 10번 노드의 LCA를 구해보자. 두 노드의 깊이가 각각 2와 3으로 같지 않으므로 두 노드의 깊이를 맞춰주는 작업을 진행해준다. 두 노드의 깊이가 같아졌다면 이제 두 노드가 같아질 때까지 거슬러 올라가준다. 6번 노드와 10번 노드의 ..

Union-find란? 합집합을 찾는 알고리즘이다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해 두 노드를 같은 집합으로 합치거나, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별해주는 알고리즘 크루스칼 알고리즘에도 쓰이는 중요한 그래프 알고리즘 알고리즘 사례 위와 같이 모두 떨어져있는 집합 각각 6개씩 있다고 가정하자. 각각의 부모노드는 자기자신이다. 여기서 2와 3를 연결했다고 해보자. (이 때 i값이 작은쪽이 부모노드가 된다고 가정한다 보통 작은 쪽이 부모노드가 되는 게 일반적) 이제 1과 2를 연결해보자. 위의 표를 보면 알 수 있듯이 합집합으로 되어있는 노드들의 부모노드 값들이 전부 조상노드로 향하는 게 아니라는 걸 알 수 있다. 그렇기 때문에 합집합으로 다 연결을 했다고..

다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..

최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다. 이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다. 다이나믹 프로그래밍을 이용한 최장 증가 부분 수열 for(int i=1;i dp[i]) dp[i] = dp[j] + 1; } result = max(result, dp[i]); } 각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다. 처음 원소부터 해당 원소까지 for문을 돌리는데 이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 ..

마스터 정리 (Master Theorem) 재현식으로 표현된 알고리즘의 동작시간을 점근적으로 계산해 간단하게 계산하는 방법 $T(n) = a T( \frac{n}{b} ) + f(n) $이고 $ a>b>1, n$이 음수가 아닌 정수일 때, $$\begin{cases}T(n) \in \Theta (n^{\log _b a}) & \mathrm{if}\,\, f(n) \in O(n^{\log_b a- \epsilon }) \\ T(n) \in \Theta(n^{\log_b a} \log n) & \mathrm{if} \,\, f(n) \in O(n^{\lg _b a}) \\ T(n) \in \Theta(f(n)) & \mathrm{if} \;f(n) \in \Omega(n^{\log_b {a+\epsilon}..

에라토스테네스의 체란? 고대 그리스 수학자 에라토스테네스가 만든 소수 판정법. 임의의 자연수 $N$에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법. 우선 에라토스테네스의 체를 쓰지 않고 그냥 소수를 구해보자 bool isPrime = true; int N; for(int i=2;i

분기한정법이란? 분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다. https://kimmessi.tistory.com/74?category=871925..

되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답이 유망했는지 아닌지를 판별하면서 불필요한 노력을 절감할 수 있다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. 깊이 우선 탐색 (depth - first search) 부모 마디 우선(preorder) 트리 검색은 트리의 깊이 우선 검색이다. 이는 뿌리마디(root)를 먼저 방문한 후, 그 뿌리마디(node)의 후손들을 모두 방문한다. 예시로는 왼쪽에서 오른쪽의 순서로 마디의 자식을 방문한다. 다음은 깊이우선검색을 하는 간단한 재귀 알고리즘을 쓰는 프로시저이다. void depth_first_tree_se..

탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택한다. 적절성검사(feasibility check) : 새로운 집합이 해답이 되기 적절한지 검사한다. 해답점검(solution check) : 새로운 집합이 문제의 해답인지 결정한다. 이 과정이 동시다발적으로 진행된다. 거스름돈을 고르는 탐욕 알고리즘 예를 들어 돈이 50원, 25원, 10원, 5원, 1원이 있고 31원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.) 1. 50원을 집었다가 내려놓는다. 2. 25원을 집는다. 3. 25원을 ..

동적계획 알고리즘이란? 동적계획은 분할한 입력사례를 재귀 호출해 답을 얻고, 그 보다 작은 입력사례의 답을 먼저 구해 저장해놓고, 필요하면 꺼내 쓰는 알고리즘이다. 분할정복과는 달리 상향식(bottom-up) 접근 방법이다. 동적계획 알고리즘의 개발단계는 다음과 같다. 1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식을 세운다. 2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다. 이항계수 구하기 이항계수 (binomial coefficient)는 다음과 같다. $$\left(\begin{array}{c}n\\ k\end{array}\right) = \frac{n!}{k!(n-k)!} \;\; \mathrm{for} \;\;0 \leq k \leq n$$ 위..