완전 정보 게임 (NIM 게임) 게임의 정보가 참가자 모두에게 공개. 양쪽다 최선을 다한다면 게임 시작과 동시에 승패가 결정됨. 최선이 뭔데?? NIM 게임 : 플레이할 때마다 문제 사이즈가 줄어드는 게임. 바둑돌 가져가기1 K개의 바둑돌을 두사람이 번갈아가며 1개 혹은 2개씩 가져감. 못가져가는 사람이 짐. 나부터 시작. DP값은 지거나(X) 이기거나(O)를 의미 k를 순서대로 진행하면서 규칙을 찾아보자. ⇒ k가 3의 배수일때 나는 무조건 진다. = 내가 시도를 하고나서 다음 타자를 X로 보내면 이긴다. = DP : XOO 반복 예를 들어 i=2의 경우 내가 2개를 뽑는 다면 다음타자를 i=0인 상황으로 보낼 수 있다. 그런데 i=0의 DP 는 X이므로 다음타자는 더이상 할 수 있는게 없으므로 진다...

Longest Increasing Subsequence (LIS) 같은 숫자는 허용 X ⇒ 허용하는 경우 : 예를 들어 3이 여러개 있을 때 각각의 3을 3.1, 3.2, 3.3 … 으로 바꾸면 여전히 알고리즘 적용 가능. 불연속이어도 됨. O(n²) 알고리즘 입력 값이 Arr(i) 에 주어진다고 하였을 때 LIS(i) 는 Arr(i)를 포함하여 (i) 까지 오면서 가장 큰 LIS 이다. ⇒ 즉, Arr(0) ~ Arr(i-1) 들중 Arr(i)보다 작은 값들(Increasing 해야하므로) 중에서 LIS가 가장 큰값 + 1(Arr(i)를 포함) = LIS(i) DP Optimization - O(nlogn) DP 결과의 데이터를 분석하여 최적화 하기. 불필요한 계산이나 중복되는 계산을 지우자. 1. 같..

금화 모으기 - O(n²) 왼쪽 아래에서 오른쪽 위로 가면서 금화 모으기 Ceil(i, j) 는 (i, j) 일 때까지 오면서 모을 수 있는 최대 금화 개수 ⇒ (i, j)의 바로 왼쪽과 바로 아래쪽 중 더 큰값이 정답. (집합 나누기) Cell(i, j) = Max(Cell(i-1, j), Cell(i, j-1)) + Coin(i, j) 동전 거스름 돈 N원을 1원, 4원, 6원을 사용하여 남김없이 거스름 돈 주는 방법. 만약 동전의 종류가 2배 이상 차이가 나면, 큰 것부터 주는 그리디 방법을 사용하면 되지만 지금은 4원, 6원이 서로 2배이상 차이가 나지 않으므로 정답에 6원이 안들어갈 수도 있다. 즉, 가장 큰 것부터 주는 것이 답이 아닐 수도 있음. 따라서 DP로 해결. C[j] = j원을 거슬..

최대 공백 정사각형 - O(n²) n x n 크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형 찾기. 오른쪽 아래 구석인 x, y 위치에서 만들 수 있는(x,y 를 포함하는) 가장 큰 정사각형의 크기가 LES(x, y) 에 저장됨. 1. (x, y) == 1 이라면 (그 자리에 검은점이 존재하면) LES(x, y) = 0 2. 1행 or 1열의 경우 검은점 자리를 제외한 나머지의 LES(x, y) = 1 3. (x,y) == 0 이라면 LES(x, y) = Min(LES(x-1, y-1), LES(x, y-1), LES(x-1, y)) + 1 최대 공백 직사각형 - O(n²) 넓이가 제일 큰 빈 직사각형 찾기. 스택 문제로부터 아이디어 1. 입력을 높이 입력으로 변환 ⇒ 높이로의 변환..

Sequence Alignment Global, Local, Semi-local Alignment Problems. 편집거리에서 insert 와 delete로 인한 길이 차이 발생을 방지. 빈자리에 gap symbol(‘-’) 을 넣어서 매치시키기. 즉, 두 문자열은 최종적으로 같은 길이의 문자열이 된다. 모든 문자들 쌍에 대한 score가 존재. score가 최대가 되도록 하는 답 구하기. 문자열 A, B 가 주어졌을 때 이에 대한 optimal global alignment V를 구해보자. 이때 각 문자 쌍에 대한 σ (Scoring Matrix)가 주어진다면 다음과 같이 계산하면 된다. (편집 거리 코드에서 +1 되던 부분을 score 값으로 변경하면 된다.) V(0, 0) = 0 V(i, 0) =..

최장 공통 부분 서열 (LCS) 두 문자열의 유사도 측정. 이때 연속이 아니더라도 허용한다. 구하고자 하는 것은 LCS의 길이 X = (x1, … xm) Y = (y1, … yn) 일반적인 방법 - O(2^m) LCS 구하기 X의 모든 부분 서열을 구하여 Y의 부분 서열인지를 비교한다. X의 부분 서열(집합)의 수는 2^m 이므로 최소 O(2^m)의 시간이 걸린다. DP - O(n²) DP를 이용하여 LCS(i, j)를 계산한다. 이때 LCS(i, j)는 xi와 yj의 LCS이다. 그리고 최종 답은 LCS(m, n) 이다. i=0 혹은 j=0 일때 비교할 게 없으므로 ⇒ LCS(i, j) = 0 LCS 를 계산하기 위해 집합을 나눠보자 1. 만약 xi = yj 이라면 ⇒ LCS(i, j) = LCS(i-..

근사 문자열 매칭과 거리함수 근사 문자열 매칭 (Approximate string matching) 주어진 문자열과 비슷한 문자열 비교, 검색 거리함수 비슷함의 정도, 기준 해밍거리(Hamming distance) 문자열 두개의 같은 자리를 sync를 맞추며 비교. 길이가 서로 다르면 파악이 힘들다. 편집거리(Edit distance) 편집(insert, delete, change)이 얼마나 일어났는지? 모든 편집의 가중치는 1로 고정. 가중편집거리(Weighted edit distance) 모든 글자와 편집에 서로 같거나 다른 가중치를 부과. 기타 등등… 휴리스틱 : 아직 증명이 안된 알고리즘 편집거리 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산의 최소 수. 편집 연산의 종류 insert..

All-Pairs Shortest Path 무방향 그래프, 웨이트 있음. 가능한 모든 최단 거리 쌍 찾기. 다익스트라 n번 돌리기? ⇒ O(n*(m+n)logn) Floyd Warshall - O(n³) D[k][i]][j] 를 구하자. ⇒ 반복문 세번 O(n³) D[k][i]][j]는 1, 2, 3, …, k 노드를 거치는 i → j 의 가장 짧은(최단) 거리. 1, 2, 3, …, k 노드를 전부 거칠 필요는 없고, 단지 i, …, j 사이에 거칠 수 있는 노드로 1, 2, 3, …, k 가 존재한다는 의미. 또한 D[k][i][j] 에서 k+1, k+2, … ,n 노드는 사용하지 않음. k = n 일 때가 i → j 최단 거리의 최종 답. k = 0 일 때는 i → j 의 기본 웨이트와 같다.(다른..

Maximum Subarray 배열에서 연속된 부분 배열중 그 합이 가장 큰 부분 배열을 찾는 문제. 값으로는 양수, 음수 존재. 배열의 값이 모두 음수 값이라면, 그 중 절댓값이 가장 작은 값이 정답. (공집합(아무런 부분 배열도 고르지 않음)은 정답에서 제외한다.) O(n³) 알고리즘 브루트포스 가능한 모든 배열을 찾는다. O(n²) 알고리즘 구하는데 겹치는 부분은 이전 것을 재활용한다. O(n) 알고리즘 방법 1 : i를 포함한 최대합과 포함하지 않은 최대합을 비교한다. DP1[k] = Max(DP1[k-1] + arr[k], arr[k]) // DP1은 i를 포함하지 않은 최대합이다. DP2[k] = Max(DP1[k], DP2[k-1]) // DP2는 i를 포함한 최대합이다. i=1 부터 시작해..

Matrix Multiplication 행렬사이즈가 서로 다른 행렬들의 곱셈 (A x B) * (B x C) 왼쪽 행렬의 한칸에 B번 곱하는데 총 A x C 칸이 생기므로 총 ABC 의 시간이 걸린다. ex) 2x3 * 3x5 * 5x2 가 있을 때 순서대로 곱하면 2x3x5 + 2x5x2 = 50 의 시간이 걸린다. 반대로 1. 3x5 * 5x2 를 먼저 곱하면 3x5x2 의 시간이 걸린다. 2. 이후 2x3 * 3x2 를 곱하면 2x3x2 의 시간이 걸린다. ⇒ 총 3x5x2 + 2x3x2 = 48 의 시간이 걸린다. 즉, 곱하는 순서에 따라 시간이 다르게 발생한다. 행렬 M1, … Mn을 곱한다고 했을 때 Cij 는 Mi 부터 Mj 까지 곱했을 때의 최소 곱셈 횟수이다. 따라서 C1n이 최종 답이다..