알고리즘 노트(생각 정리용)
1. LIS (Longest Increase Subsequence, 최장 증가 수열)
보통 수열 내의 가장 긴 오름차순 부분 수열을 찾는 문제.
- dp[] 배열(부분 수열 저장 - ArrayList)과 value[] 배열(값 저장)을 만든다.
- value[] 배열을 끝까지 돌면서 다음 작업을 수행한다.
- 1) dp[] 배열이 비어있다면 그냥 추가.
- 2) dp[] 배열의 마지막 값 < value[] 현재값 v -> dp[] 마지막에 추가.
- 3) dp[] 배열의 마지막 값 >= value[] 현재값 v ->
dp[] 배열에서 v를 정렬되도록 추가한다.(원래의 값과 바꿈)
선형 탐색 시 (N^2), 이분 탐색 시(NlogN)
- 주의할 점 : 최장 증가 수열의 길이는 dp[] 의 크기지만 안의 내용은 다를 수 있기 때문에 최장 증가 수열을 출력하려면 따로 인덱싱을 해주는 배열이 필요하다.
- 부분 수열 출력 방법 : 이분 탐색을 이용한 nlogn 방법에선 이분 탐색으로 dp[] 내의 값을 수정할 때 수정한 수의 전까지는 LIS 를 만족하기 때문에
trace[수정한 수] = 바로 이전 값(dp[] 에서)
위와 같이 경로를 만들어 준다.(수정하지 않고 마지막에 추가할 경우도 똑같이 이전 값을 넣어준다, 경로의 끝은 -1로 초기화해준다.)
dp[] 배열의 마지막 수부터 trace 배열을 역으로 탐색하면 가장 긴 부분 수열을 출력할 수 있다.
위와 같이 하게 되면 다음과 같은 반례가 나온다
6
1 3 5 7 2 3
답은
4
1 3 5 7
이지만
4
1 2 3 5 7 이 나온다.
trace 배열을 모든 value 값에 대해 만들어 주는데, trace[i] 는 value[i] 가 dp[] 에서 어느 인덱스에 있는지를 저장해준다.
그 뒤 trace 배열을 뒤에서부터 탐색하고, dp 사이즈 -1 부터 시작하여
trace[i]의 인덱스 == dp 인덱스
라면 스택에 value값을 저장한다.
2. LCS (Longest Common Subsequence, 최장 공통 부분 수열)
보통 수열 내의 가장 긴 공통 부분 수열을 찾는 문제.(두 개의 수열이 주어진다.)
- 각각의 수열에 대해 2차원 배열을 만든다.( 크기 + 1 개 why? 0행과 0열을 0으로 초기화)
- 수열1 의 각 원소에 대해 수열 2의 원소를 대응해가면서 다음 작업을 수행한다.
- 문자가 서로 같다면 -> dp[i][j] = dp[i - 1][j - 1] + 1 즉, 왼쪽 위 + 1
- 문자가 서로 다르다면 -> dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1])
+ 가장 긴 부분 문자열을 찾는 문제
(두 개의 문자열 중 공통 부분 문자열을 찾는데, 끊기지 않고 연속인 부분 문자열을 찾아야 한다.)
- LCS 알고리즘에서 간단히 dp 식을 바꿔주면 된다.
- 문자가 서로 같다면 -> dp[i][j] = dp[i - 1][j - 1] + 1 즉, 왼쪽 위 + 1
- 문자가 서로 다르다면 -> dp[i][j] = min( dp[i - 1][j] , dp[i][j - 1] , dp[i - 1][j - 1])
3. 이항 계수의 Nlog(N) 풀이
예제 : 11401번 - 이항 계수 3
기존 N^2 의 풀이는 점화식
nCk = (n - 1)C(k) + (n - 1)C(k - 1)
을 이용하여 동적 계획법으로 풀이하는 방법이다.
Nlog(N) 의 시간 복잡도로 풀기 위해 다음 식을 변형해야 한다.
nCk = (N!) / ((K!)*(N - K)!)
위 식을 사용하면 값이 매우 커지기 때문에 특정한 수로 나눈 나머지를 구하는 작업을 해줘야 하는데, 모듈러 연산 시 / 연산은 사용할 수 없다.
따라서 페르마의 소정리를 이용하여 위 식을 곱셈과 거듭 제곱의 형태로 바꾸어야 한다.
페르마의 소정리(링크)
A^(p - 1) % p == 1,
(A*A^(p - 2)) % p == 1,
A^(p - 2) % p == 1 / A
위 식을 이용하면 분모인 ((K!)*(N - K)!) 을 곱셈의 형태로 나타낼 수 있다.
A / B (mod M) == A / BM - 2
4. 확장 유클리드 알고리즘
예제 : 14565번 - 역원(Inverse) 구하기
기존의 유클리드 알고리즘은 A 와 B 의 최대 공약수를 구하는 알고리즘이었다.
즉, Ax + By = gcd(A, B) 식에서 gcd(A, B) 값을 구한다.
확장 유클리드 알고리즘에선 위 식에서 x와 y의 값을 구할 수 있다.
예를 들어, A = 18 , B = 57 이라고 할 때,
18x + 57y = 3 에서 x = -3, y = 1 이 된다.
x 와 y를 구하는 법은
1. 배열 x = { 1, 0 }
배열 y = { 0, 1 } 로 초기값을 둔다.
2. 기존 유클리드 알고리즘에서 몫을 구하는 코드를 추가한다.
3. x[i] = x[i - 2] + x[i - 1] * (몫)
4. y[i] = y[i - 2] + y[i - 1] * (몫) -> i는 2부터 시작
반복이 끝났을 때 x 와 y 배열의 마지막 원소가 구하고자 하는 값이다.
5. CCW
세 점 P1, P2, P3 가 주어졌을 때, 삼각형의 넓이를 구하는 공식은 다음과 같다.
S = ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2
이 때 세 점을 이은 직선의 방향은
S > 0 -> 반시계 방향
S = 0 -> 일직선
S < 0 -> 시계 방향.
6. KMP 알고리즘
예제 : 1786번 - 찾기
어떤 문자열 S 에서 특정한 부분 문자열 P 를 O(N + M) 의 시간 복잡도로 찾을 수 있는 알고리즘이다.(N, M은 S,P 의 길이)
- 문자열 P의 맨 앞부터 부분 문자열들에 대해 각각 (접두사 == 접미사) 인 최대 길이를 저장하는 pi[] 배열을 만든다.
pi 배열 구하기
( j == 현재 가장 길게 겹치는 접두사의 길이, i == 문자열 P 를 처음부터 쭉 읽음)
1. P[i] != P[j]일 때 -- while문을 통해 j를 가장 최근에 접두사, 접미사가 같았던 곳으로 돌려놓는다.(P[i] == P[j] 가 될때까지, j 가 0이 되면 break)
2. P[i] == P[j]일 때 -- 현재 pi[i] 의 값을 j + 1 로 하고, j를 증가시킨다.
문자열 S를 처음부터 끝까지 읽으면서 부분 문자열 P가 있는지 확인하기
위에서와 마찬가지로, S[i] != P[j] 와 S[i] == P[j] 인 경우로 나누어 전자의 경우엔 j를 가장 왼쪽에서 겹쳤던 곳으로 되돌리고, 후자인 경우엔 j를 증가시키다가(겹치므로) P의 크기만큼 동일하다면 찾은 게 되고, j를 이전 겹쳤던 곳으로 돌려준다.
보통 수열 내의 가장 긴 오름차순 부분 수열을 찾는 문제.
- dp[] 배열(부분 수열 저장 - ArrayList)과 value[] 배열(값 저장)을 만든다.
- value[] 배열을 끝까지 돌면서 다음 작업을 수행한다.
- 1) dp[] 배열이 비어있다면 그냥 추가.
- 2) dp[] 배열의 마지막 값 < value[] 현재값 v -> dp[] 마지막에 추가.
- 3) dp[] 배열의 마지막 값 >= value[] 현재값 v ->
dp[] 배열에서 v를 정렬되도록 추가한다.(원래의 값과 바꿈)
선형 탐색 시 (N^2), 이분 탐색 시(NlogN)
- 주의할 점 : 최장 증가 수열의 길이는 dp[] 의 크기지만 안의 내용은 다를 수 있기 때문에 최장 증가 수열을 출력하려면 따로 인덱싱을 해주는 배열이 필요하다.
- 부분 수열 출력 방법 :
위와 같이 하게 되면 다음과 같은 반례가 나온다
6
1 3 5 7 2 3
답은
4
1 3 5 7
이지만
4
1 2 3 5 7 이 나온다.
trace 배열을 모든 value 값에 대해 만들어 주는데, trace[i] 는 value[i] 가 dp[] 에서 어느 인덱스에 있는지를 저장해준다.
그 뒤 trace 배열을 뒤에서부터 탐색하고, dp 사이즈 -1 부터 시작하여
trace[i]의 인덱스 == dp 인덱스
라면 스택에 value값을 저장한다.
2. LCS (Longest Common Subsequence, 최장 공통 부분 수열)
보통 수열 내의 가장 긴 공통 부분 수열을 찾는 문제.(두 개의 수열이 주어진다.)
- 각각의 수열에 대해 2차원 배열을 만든다.( 크기 + 1 개 why? 0행과 0열을 0으로 초기화)
- 수열1 의 각 원소에 대해 수열 2의 원소를 대응해가면서 다음 작업을 수행한다.
- 문자가 서로 같다면 -> dp[i][j] = dp[i - 1][j - 1] + 1 즉, 왼쪽 위 + 1
- 문자가 서로 다르다면 -> dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1])
+ 가장 긴 부분 문자열을 찾는 문제
(두 개의 문자열 중 공통 부분 문자열을 찾는데, 끊기지 않고 연속인 부분 문자열을 찾아야 한다.)
- LCS 알고리즘에서 간단히 dp 식을 바꿔주면 된다.
- 문자가 서로 같다면 -> dp[i][j] = dp[i - 1][j - 1] + 1 즉, 왼쪽 위 + 1
- 문자가 서로 다르다면 -> dp[i][j] = min( dp[i - 1][j] , dp[i][j - 1] , dp[i - 1][j - 1])
3. 이항 계수의 Nlog(N) 풀이
예제 : 11401번 - 이항 계수 3
기존 N^2 의 풀이는 점화식
nCk = (n - 1)C(k) + (n - 1)C(k - 1)
을 이용하여 동적 계획법으로 풀이하는 방법이다.
Nlog(N) 의 시간 복잡도로 풀기 위해 다음 식을 변형해야 한다.
nCk = (N!) / ((K!)*(N - K)!)
위 식을 사용하면 값이 매우 커지기 때문에 특정한 수로 나눈 나머지를 구하는 작업을 해줘야 하는데, 모듈러 연산 시 / 연산은 사용할 수 없다.
따라서 페르마의 소정리를 이용하여 위 식을 곱셈과 거듭 제곱의 형태로 바꾸어야 한다.
페르마의 소정리(링크)
A^(p - 1) % p == 1,
(A*A^(p - 2)) % p == 1,
A^(p - 2) % p == 1 / A
위 식을 이용하면 분모인 ((K!)*(N - K)!) 을 곱셈의 형태로 나타낼 수 있다.
A / B (mod M) == A / BM - 2
4. 확장 유클리드 알고리즘
예제 : 14565번 - 역원(Inverse) 구하기
기존의 유클리드 알고리즘은 A 와 B 의 최대 공약수를 구하는 알고리즘이었다.
즉, Ax + By = gcd(A, B) 식에서 gcd(A, B) 값을 구한다.
확장 유클리드 알고리즘에선 위 식에서 x와 y의 값을 구할 수 있다.
예를 들어, A = 18 , B = 57 이라고 할 때,
18x + 57y = 3 에서 x = -3, y = 1 이 된다.
x 와 y를 구하는 법은
1. 배열 x = { 1, 0 }
배열 y = { 0, 1 } 로 초기값을 둔다.
2. 기존 유클리드 알고리즘에서 몫을 구하는 코드를 추가한다.
3. x[i] = x[i - 2] + x[i - 1] * (몫)
4. y[i] = y[i - 2] + y[i - 1] * (몫) -> i는 2부터 시작
반복이 끝났을 때 x 와 y 배열의 마지막 원소가 구하고자 하는 값이다.
5. CCW
세 점 P1, P2, P3 가 주어졌을 때, 삼각형의 넓이를 구하는 공식은 다음과 같다.
S = ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2
또는
S = ((x1*y2 + x2*y3 + x3*y1) - (y1*x2 + y2*x3 + y3*x1)) / 2
이 때 세 점을 이은 직선의 방향은
S > 0 -> 반시계 방향
S = 0 -> 일직선
S < 0 -> 시계 방향.
6. KMP 알고리즘
예제 : 1786번 - 찾기
어떤 문자열 S 에서 특정한 부분 문자열 P 를 O(N + M) 의 시간 복잡도로 찾을 수 있는 알고리즘이다.(N, M은 S,P 의 길이)
- 문자열 P의 맨 앞부터 부분 문자열들에 대해 각각 (접두사 == 접미사) 인 최대 길이를 저장하는 pi[] 배열을 만든다.
pi 배열 구하기
( j == 현재 가장 길게 겹치는 접두사의 길이, i == 문자열 P 를 처음부터 쭉 읽음)
1. P[i] != P[j]일 때 -- while문을 통해 j를 가장 최근에 접두사, 접미사가 같았던 곳으로 돌려놓는다.(P[i] == P[j] 가 될때까지, j 가 0이 되면 break)
2. P[i] == P[j]일 때 -- 현재 pi[i] 의 값을 j + 1 로 하고, j를 증가시킨다.
문자열 S를 처음부터 끝까지 읽으면서 부분 문자열 P가 있는지 확인하기
위에서와 마찬가지로, S[i] != P[j] 와 S[i] == P[j] 인 경우로 나누어 전자의 경우엔 j를 가장 왼쪽에서 겹쳤던 곳으로 되돌리고, 후자인 경우엔 j를 증가시키다가(겹치므로) P의 크기만큼 동일하다면 찾은 게 되고, j를 이전 겹쳤던 곳으로 돌려준다.
댓글
댓글 쓰기