해나의 컴공생존기

1. Cut Vertex Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 O(n (m+n))의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 O(m+n)만에 절단점을 찾을 수 있다. 1.2. root Cut Vertex root 노드는 child가 2개 이상이라면 무조건 cut vertex이다. 증명해보자! 1) child가 0개인 경우 루트 노드밖에 없으므로 성립 2) child가 1개인 경우 사진과 같이 root노드가 없어도 자식노드들 끼리 다 연결되어있다. 3) child가 2개 이상일 경우 루트노드에 1번 서브트리와 2번 서브트리가 있다고 가정해보자. 1번 서브트리에는 어딘가에 ..

1. Recursive DFS RDFS 는 시작노드로부터 인접한 노드로 방문하는데, 앞 노드가 방문되지 않았으면 그 노드에서 또 재귀적으로 호출한다. 각 노드들이 RDFS의 인자가 되는 것은 한번 뿐이므로 시간 복잡도는 O(m+n)이 걸린다. 1.1 DFS tree DFS에서 전진한 edges로만 생성한 결과를 DFS Tree라 한다. 시작 노드가 루트이고, 전진하면서 방문한 노드들을 자식으로 하나씩 갖게 된다. 1.2 edge 종류 Tree Edges: DFS Tree에 들어간 모든 엣지들 Forward Edges: 조상에서 자손으로 연결되는 엣지 중 트리에 포함되지 않는 엣지들 Back edges: 자손에서 자기보다 조상들 중 하나로 연결되는 엣지 (DFS 과정에서 이미 방문한 노드로 향하는 엣지) ..

1. Traversal Traversal : 그래프의 노드를 방문하는 방법 어디서 시작하는지 정하지 않는다. 어디에서 시작하느냐에 따라서 다른 알고리즘이 된다. 같은 노드를 여러번 지나갈 수 있다. 어떤 문제를 푸느냐에 따라서 계산할 것들이 달라진다. Traversal을 통해 그래프 안에 뭔가 구조가 만들어질 것이다. => 보통 Tree가 만들어 진다. 2. Any-Order Traversal 어떤 노드 s에서 시작하고 s를 BOX에 넣는다. BOX가 비어있지 않으면 아래의 과정을 반복한다. 하나의 노드를 꺼내고 방문하지 않은 노드라면 방문한 뒤 어떤 계산을 수행한다. 그리고 노드와 인접한 모든 엣지들을 BOX에 넣는다. 이후 이 과정을 계속 반복한다. 박스에 여러개 들어있다면 어느 것을 꺼내겠는가? 어..

1. 돌 가져가기 n개의 돌이 있고, 각 돌에는 숫자가 있다. 게임 참가자는 두명이다. A는 하나의 타일 X를 고른다 B는 X를 기준으로 왼쪽 혹은 오른쪽 에서만 돌을 가져갈 수 있다. 이가 반복된다. 돌에 적힌 숫자가 점수가 된다. 이 때 어떻게 하면 최고점이 보장 될 수 있을까? 1,1 idea (모름) 2. longest Increasing Subsequence (LIS) 숫자의 나열이 있을때, 증가하는 가장 긴 Subsequence를 찾는 것이 이 문제의 정의이다. 2.1 idea 각 숫자의 나열에 나로 끝나는 LIS의 개수를 적는다 내가 앞 숫자가 나보다 작으면 내 앞 배열 + 1을 해주면 된다. 8 2 7 6 3 4 1 2 1 1 2 2 2 3 1 2 2.2 Proof 여러가지 경우에도 이 규..

1. 동전 거스름 돈 N원의 거스름 돈을 돌려줄 때, 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구해보자. 1.1 idea 8월을 거슬러준다고 가정해보면 아래 경우중 하나가 일어날 것이다. 동전은 1원, 4원, 6원짜리가 있다고 가정해보자. 1원 동전 한개 + 7원 최적해 4월 동전 한개 + 4원 최적해 6원 동전 한개 + 2원 최적해 위처럼 작은 사건으로 나눌 수 있다. 식으로 나타내면 아래와 같다. C(i, j)를 크기 Di 동전으로 j원을 거슬러 줄 때의 동전 개수라고 가정하자. C(i, j-Di) + 1 : Di 원을 거슬러 준 경우 동전 하나 추가 C(i-1, j) :거슬러 주지 않고 다음 돈으로 스킵(i원짜리 동전이 없을 때,1원 내기) 2. 바둑 돌 가져가기 완전 정보 게임 :..

1. 최장 공통 부분 서열 (LCS) subsequence는 떨어져 있을 수 있고 substring는 연속되어야 한다. 정확히 말하자면 subsequence은 주어진 서열에서 일부 문자를 삭제한 후에 남은 문자들로 만들 서열을 의미한다. LCS은 X와 Y가 주어질 때 X와 Y의 공통 부분 서열 중 가장 긴 것을 의미한다. 1.2. idea LCS(i, j)를 Xi와 Yj의 LCS길이라고 하자. 우리가 구해야할 길이는 LCS(m,n)이다. i=0 or j=0 → LCS(i,j) =0 Xi = Yj → LCS(i,j) = LCS(i-1,j-1)+1 Xi ≠ Yj → LCS(i,j) = max{LCS(i,j-1),LCS(i-1,j)} 2. 최대 공백 정사각형 주어진 크기의 흑백 이미지에서 검은 점을 포함하지 ..

1.근사 문자열 매칭과 거리함수 근사 문자열 매칭 : 비슷한 문자열 비교 (엄청 빠른 방법은 없음) 거리함수 해밍거리 : 두 문자열을 같은 자리를 비교해서 다른 것의 개수를 센다. 밀리는 경우는 체크 못함 편집거리 : 해밍거리와 비슷하지만 insert, delete 와 change 존재 가중편집거리 : 편집거리와 비슷하지만 문자별로 가중치 존재 2. 편집거리 편집거리란 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수이다. 편집연산은 삽입, 삭제, 교체가 존재한다. 이를 구하는 방법은 문자열 두개로 표를 만든뒤 각 칸에 편집거리를 계산해주는 것이다 . 편집거리는 아래와 같이 계산한다. D(i,j)는 S1의 i번째 인덱스와 S2의 j번째 인덱스를 비교한다는 의미이다. D(i, j-1) ..

1. 문제정의 모든 노드 쌍들마다의 최단경로 구하기 (path까지는 어렵기 때문에 길이만 구할 것이다) undirect 그래프라고 가정. 가장 쉬운방법은 다익스트라 알고리즘을 n번 돌리는 것이다. 2. Floyd Warshall Alg 각 노드별로 번호를 부여했다고 가정하자. i → j로 가는 최단경로를 구할 건데, {1, 2, ..., k}번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k가 0부터 N까지 반복한다. (k가 n일 때가 최종 답이된다,) 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 k번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다. k=0이라면 {공집합}이고 i와 j를 연결하는 것은 direct edge밖에 없다. direct edge가 없다면 답은 ..

1. 문제 정의 각 칸에 숫자가 적혀있을 때, 합이 최대가 되게 하는 Subarray의 합을 구하는 것이다. 0칸의 합도 허용하는 버전과, 허용하지 않는 버전 모두 소개될 것이다. 2. idea : O(N^3) 1.모든 경우의 수를 다 해본다. 크기가 1인거 n개, 2인거 n-1개,...,n인거 1개 → n(n-1)/2 => (N^2) 한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문. 2. 칸을 나누는 선은 n+1개 이다. 이 중 시작선과 끝선을 두개 뽑는다 n+1C2 => (N^2) 한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문. 3. idea : O(N^2) 아이디어는 앞에와 같다. 이 방법은 계산에 쓰이는 시간 N을 절약하는 것이다. n개가 계산이 되어어있고 n+1개를 계산해야한..

1. 문제정의 행렬의 곱에서 어떤 행렬을 먼저 곱하냐에 따라 걸리는 시간이 달라진다. 행렬들은 M1, M2, ... Mn으로 표현되며, 행렬의 크기는 di-1 * bi로 표현된다. Cij는 Mi부터 Mj까지 곱했을 때 최소 비용을 의미하며 C1n이 최종 답이 된다. 2. solution 전체 답을 제일 좋은 답으로 만들기 위해서는 어떤 곱을 나중에 해야할까? 우리는 이 문제에 대한 해답을 알지 못한다. 따라서 하나씩 다 해볼 것이다. Cij에서 i-j가 작은 값부터 해볼 것이다. 1) i-j =0 C11,C22,C33, ... Cnn 위와 같은 경우는 비용이 모두 0이라고 할 수 있다. 2) i-j =1 C12,C23,C34, ... Cn-1n 비용은 di-1 * di * di+1 3) i-j =2 C1..