[Algorithm] LIS(Longest Increasing Subsequence; 최장 증가 부분 수열)
LIS(Longest Increasing Subsequence; 최장 증가 부분 수열) 어떠한 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제 이때, 부분 수열은 서로 연속할 필요는 없다. 어떠한 수열에서 일부 원소를 선택해 새로 만든 수열은 '부분 수열'이며 그 수열이 오름차순으로 정렬되어 있으면 '증가하는 부분 수열'이다. ex) 수열 [10, 20, 10, 30, 20, 50] 해당 수열에서 [10, 20, 30, 50], [10, 20, 50], [10, 50],... 등 많은 증가 부분 수열이 있지만 많은 증가 부분 수열 中 가장 길이가 긴 수열은 4개의 원소를 가진 [10, 20, 30, 50]이다. 따라서 [10, 20, 30, 50] 최장 증가 부분 수열이다. LIS는 DP(D..
2022. 3. 14.
[Algorithm] LCS (최장 공통 부분 수열, 최장 공통 부분 문자열)
LCS의 2가지 Longest Common Subsequence (최장 공통 부분 수열) Longest Common Substring (최장 공통 부분 문자열) Subsequence와 Substring의 차이점 Subsequence : 전체 문자열에서 꼭 연속적이지는 않은 부분 문자열 Substring : 전체 문자열에서 연속된 부분 문자열 str1 : 'ABECJ' str2 : 'ABKJG' 공통 부분 수열 -> {}, {A}, {B}, {J}, {A, B}, {A, J}, {B, J}, {A,B,J} -> 최장 공통 부분 수열 str1 : 'ABECJ' str2 : 'TABJG' 공통 부분 수열 -> {}, {A}, {B}, {A, B} -> 최장 공통 부분 문자열 Longest Common Subs..
2021. 10. 3.
[Algorithm/Python(파이썬)] 유클리드 호제법(Euclidean algorithm)
유클리드 호제법(Euclidean algorithm) 2개의 자연수의 최대공약수를 구하는 알고리즘 비교대상의 두 개의 자연수 n, m (단 n >m)에서 n을 m으로 나눈 나머지를 r이라고 했을때 GCD(n, m) = GCD(m, r)과 같고 r이 0이면 그때 m이 최대공약수이다. 라는 원리를 활용한 알고리즘 GCD (Greatest Common Divisior) - 최대공약수 두 수 혹은 그 이상의 여러 수의 공통인 약수 중 최대 인 수 12의 약수 : 1, 2, 3, 4, 6, 12 8의 약수 : 1, 2, 4, 8 8과 12의 최대 공약수 : 4 # 유클리드 호제법을 이용한 최대 공약수를 구하는 파이썬 코드 def gcd(n, m): while (n > 0): m,n = n, m % n return..
2021. 7. 1.
