2024-02-14 기준 Greedy HTML 삽입 미리보기할 수 없는 소스 Divide and Conquer HTML 삽입 미리보기할 수 없는 소스 Dynamic Programming HTML 삽입 미리보기할 수 없는 소스 Graph HTML 삽입 미리보기할 수 없는 소스 Back Tracking HTML 삽입 미리보기할 수 없는 소스 Pseudo Polynomial HTML 삽입 미리보기할 수 없는 소스 State Space HTML 삽입 미리보기할 수 없는 소스 Randomized Algorithm HTML 삽입 미리보기할 수 없는 소스

Boruvka’s MST Algorithm 프림, 크루스칼보다는 느리다. O(mlogm) 모든 노드는 가장 작은 인접엣지를 고른다. 가장 작은 인접엣지는 항상 MST에 들어간다. a→b가 들어가지 않는다면 a→c→b와 같이 다른 엣지를 경유해서 들어온 것이 된다. 그러나 a→b 가 가장 작은 웨이트라면 그냥 a→c→b 대신에 a→c, a→b를 하면된다. 따라서 가장 작은 인접엣지는 항상 MST에 들어간다. 그러면 컴포넌트가 생긴다. 만약 두 노드가 고른 엣지가 겹치면, 전체 그래프는 분리되서 여러개의 컴포넌트가 생길 수도 있다. 최악의 경우 n/2 개 생긴다. (노드 2개씩은 무조건 연결되서 컴포넌트가 생기므로) 따라서 알고리즘을 그 상태로 다시 시도한다. (이부분 때문에 프림과 크루스칼보다 느리다.) ..

Lowest Common Ancestor LCA 노드 a와 b의 공통 조상중 제일 최소 찾기. logn 모든 노드가 자신의 부모, 조상, … 을 전부다 가지게 하자. A[i][j] 를 계산하면 된다. A[i][j] : 노드 i에서 위로 2^j 만큼 올라간 노드의 번호. 즉, A[i][0] 은 노드 i의 부모이다. 만약 A[i][j] = k가 있다고 가정하면 A[i][j+1] = A[k][j] 이다. (직접 그려서 확인해보면 맞다는 걸 알 수 있다.) A 배열의 크기가 i는 1~n 이고, j는 0~logn 이므로 전체 배열의 값을 작성하는데 nlogn이 걸린다. ⇒ 모든 조상노드를 자유롭게 순회할 수 있다. 이후 LCA를 구한다. 만약 a가 b보다 위에 존재한다면 a의 링크를 따라서 b와 같은 레벨의 a’..

Primality Test (Monte Carlo) n이 소수인가? 페르마 정리 1. 8377이 소수라면, 모든 a에 대하여 a^8376 = 1 mod 8377 이다. 2. 8377이 소수가 아니라면, 어떤 a에 대하여 a^8376 ≠1mod8377 이다. 이때 1

Linked List in an Array (Las Vegas) 링크드 리스트에서 x 찾기 기존 링크드 리스트는 O(n) 1. 배열에서 루트n개를 랜덤하게 고른다. 2. 골라진 애들중 X보다 작은애들을 고른다. 3. 작은 애들중 가장 큰 애 Y를 고른다. 4. Y의 링크를 타면서 간다. 기댓값 계산 및 검증 배열에서 k개를 골랐다고 가정했을 때 O(k + f(n, k))가 걸린다. f(n, k) 는 Y와 x 사이의 거리가 d일 확률의 기댓값이다. P[D=d] = P[D≤d] - P[D≤d-1] 이므로 =((n-d)/n)^k - ((n-d-1)/n)^k 따라서 기댓값 f(n, k) = sigma_{d=1}^{n} d * P[D=d] 이다. 즉, k + f(n, k) = k + n/(k+1) 이므로 대략 k..

Las Vegas 답은 항상 나오지만, 시간이 랜덤 Monte carlo 답이 랜덤이지만, 시간이 항상 일정 Las vegas → Monte carlo 그냥 시간되면 짜르면된다. 그때까지 답 나왔으면 나온거고, 안나왔으면 안나온거고. Monte Carlo → Las vegas 답 안나왔으면 다시 돌린다. 답 나올때까지.. Randomized QuickSort Pivot을 매번 랜덤하게 결정하기. 기존에는 특정입력에 대하여 항상 최악의 경우 O(n^2) 이지만 랜덤 quicksort는 모든 입력에 대하여 낮은 확률의 최악의 경우가 발생 가능. 따라서 특정 입력을 계속 사용해야만 하는 경우에 효과적인 알고리즘.

Traveling Salesman Problem S노드 부터 시작해서 S노드로 되돌아오는 최소 경로 각 노드는 한번만 방문 가능 엣지 웨이트 존재. (최소합) NP-Complete HTML 삽입 미리보기할 수 없는 소스 state tree를 이렇게 구성하자 루트는 시작 노드 s 차일드는 연결된 노드들 (일단 s까지 계속 연결되는 모든 노드들을 구성하자.) 어떻게 cut off 할 수 있을까? 1. 노드는 한번만 방문해야 하므로 만약 a노드의 자손들에서 다시 a노드가 나온다면 cut off 한다. 2. DFS를 한다치면 왼쪽 자손들 부터 값을 계산해나간다. 일단 a 자손들에서의 답 A를 찾았다고 치자. 그러면 나머지 b 자손들 부터의 답 B는 A보다 작아야지만 의미가 있다. 따라서 자손들을 순회하면서 계산..

15 Puzzle 빈칸대로 순서대로 옮기면서 오름차순으로 나열하기 영원히 못맞추는 모양이 있다!! 아무거나 두개 빼고 둘의 위치 교체해서 다시 넣으면 영원히 못맞춘다. 칸을 움직이면서 나올 수 있는 상태를 노드 하나로 치면 노드의 총 개수는 16! 이때 다음 상태로 한번에 갈 수 있는경우 엣지로 연결된다. ⇒ 16!은 너무 많으므로 다익스트라 불가능 2개의 connected component 가 생긴다. 그리고 두개 빼고 둘의 위치 교체해서 넣으면 그 전이랑 다른 컴포넌트에 무조건 들어가게 된다. ⇒ 답이 이전 컴포넌트에 있었다면 서로 연결 안되서 영원히 못맞춘다. 모든 노드에서 Parity of Permutation plus Parity of Distance of 16 from Corner 를 계산한다..

Pseudo Polynomial DP로 전부 다 해보기? 동전 문제 N개의 동전 단위 C[i] 가 있고, 각 동전의 개수는 무한할 때, W원을 동전으로 바꿔주기 위해 필요한 최소 동전의 개수 0원부터 N원까지의 모든 DP 값을 계산하자. 예를 들어 2원, 5원 9원이 있는 상황에 10원을 구하기위한 최소 개수는 아래와 같다. i 0 1 2 3 4 5 6 7 8 D 1 X 1 X 2 1 3 2 4 아래의 Min은 각각 2원, 5원, 9원을 하나씩 사용했을 때 이다. 점화식 : D[10] = Min(D[8] + 1, D[5] + 1, D[1] + 1) 막대기 자르기 길이 i인 막대기의 가치 V[i]가 입력으로 주어졌을 때, 길이 N인 막대기를 잘 나누어서 최대 가치로 나누는 문제 동전 문제랑 비슷하게 풀면 ..

Back Tracking = 전부 다 찾아보기 systematic 순서 cut off : 도저히 답 안나올거 같으면 그만두기 N-Queen N * N 크기 체스판에 N개의 퀸을 서로 공격할 수 없도록 올려놓는 경우의 수 퀸 : 8방향 공격 가능 N=8 기준 체스판 자리가 총 64개 이므로 64C8 의 놓을 수 있는 경우의 수가 존재하는데, 서로 공격하면 안되므로 제외되는 게 있다. 1. 한 row에 퀸이 2개 들어갈 수는 없다. 같은 row에 있으면 그 방향으로 공격 가능하므로 2. 아래로 내려갈 수록 위 퀸의 대각선 아래랑, 바로 밑은 제외되므로, 점점 놓을 수 있는 자리가 적어진다. 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 ..