잘 알고 있는 사람이 기록하는 것이 아닌,,, 모르는 사람이 알아가려고 하는 과정을 담은 글입니다.
더 잘 설명된 글이 많을테니... 귀중한 시간 낭비 마시고,,, 설명을 보고 싶으시다면 뒤로가기 버튼,,, 무지한 사람의 고뇌를 엿보고 싶으시다면,,, 스크롤...
우선 이런걸 왜 찾으려고 했을까? 라는 생각이 들면서 수업을 듣기 시작하는데.(교과서에는 DNA 염기서열 일치하는것 한다고 되어있긴 했음)
결국 하나하나 다 비교하면서 하려면 너무 시간이 많이들고 컴퓨터 자원도 많이 필요로 하니 효율적으로 필요한것을 얻기 위한 고뇌의 흔적을 배운다고 생각하며 토닥토닥..
우선 내가 몰랐던거는 ADCB, ABC 두개의 LCS를 구할때
AC도 되고, AB 도 LCS가 된다는것(난 이어져있어야 한다고 생각을 했다.)
결국 중간에 다른 글자가 껴있어도 그 글자를 건너 뛰고 순서를 생각할 수 있다는것.
효율 이런거 잘 모르겠고 가장 무식하게 구할수 있는 방법은 뭘까?
그것조차 바로 떠오르기 힘든 나였는데,,,
생각해보면 ADCB의 경우 각 알파벳이 속해잇는 자리 ㅁㅁㅁㅁ에 각각 그 알파벳을 포함시킬지 아닐지 선택하기 때문에 넣는다, 안넣는다 2가지 경우의 수가 각 자리에 있으므로
2(넣는다 안넣는다)*2(넣는다 안넣는다)*2(넣는다 안넣는다)*2(넣는다 안넣는다) = 2^4이 된다는것.
그러면 ABC는 2^3 = 8 개의 경우의 수가 나올것이고.
그 다음 16개와 8개중 일치하는 것을 찾고 그다음 그중에 가장 긴것의 개수를 세면 될 것이다.
그러면 abc 8개 경우의 수에 대해 16개랑 각각 맞춰봐야함으로 8*16 = 2^3 * 2^4 = 2*7
=> 결국 O(2*(m+n))이라는 어마무시하게 큰 비효율성을 보여주는 방법임을 알 수 있다.
| # Time: O(2^(n + m)), Space: O(n + m) def dfs(s1, s2): return dfsHelper(s1, s2, 0, 0) def dfsHelper(s1, s2, i1, i2): if i1 == len(s1) or i2 == len(s2): return 0 # if the characters match if s1[i1] == s2[i2]: return 1 + dfsHelper(s1, s2, i1 + 1, i2 + 1) # if the characters don't match else: return max(dfsHelper(s1, s2, i1 + 1, i2), dfsHelper(s1, s2, i1, i2 + 1)) |
위에 코드가 시간복잡도가 가장 비효율적인 O(2^(m+n)) 알고리즘, 재귀 호출로 모든 경우의 수를 살펴보는것을 알 수 있다.(같을 경우, 다를 경우 base case 인 i1 == len(s1) or i2 == len(s2) 에 도달할때까지 모든 경우에 대해 재귀호출)
효율적으로 구하기 위한 방법으로 똑똑하신 분들께서 고안해낸 또 다른 방법은 Dynamic Programming으로 접근하는 것인데,
INTP 인 내 머리에 떠오르는 것은 얼마나 Dynamic 하길래 Dynamic 이라고 이름을 지었지...
넘어가고, 결국 뭔가 Dynamic Programming에서 공통적으로 이야기 하고 싶은것은 sub-problem 에 관한 것인데.
하나의 문제를 작은 문제로 나눠서 문제를 해결한다는 거다.
Memoization
| # Time: O(n * m), Space: O(n + m) def memoization(s1, s2): N, M = len(s1), len(s2) cache = [[-1] * M for _ in range(N)] return memoHelper(s1, s2, 0, 0, cache) def memoHelper(s1, s2, i1, i2, cache): if i1 == len(s1) or i2 == len(s2): return 0 if cache[i1][i2] != -1: return cache[i1][i2] if s1[i1] == s2[i2]: cache[i1][i2] = 1 + memoHelper(s1, s2, i1 + 1, i2 + 1, cache) else: cache[i1][i2] = max(memoHelper(s1, s2, i1 + 1, i2, cache), memoHelper(s1, s2, i1, i2 + 1, cache)) return cache[i1][i2] |
위 방법에 대해 이미 호출해본적 있는 값에 대한 부분은 저장을 해두고 이미 호출한 재귀 함수면 저장되어있는 값을 불러오기 때문에 추가적인 호출을 하지 않는다. (이 방법으로도 시간 복잡도를 상당히 개선시킬 수 있다)
A/DCB, A/BC 에서 A가 같기 때문에, 1 + (DCB, BC)의 LCS를 구하는 문제로 더 작게 나눌수가 있다.
dp = [[0] * (M+1) for _ in range(N+1)] 이때 M+1 , N+1을 하는 이유는 A가 같은 경우처럼 처음에 같았을때 1을 더해주는거를 해야하는데 왼쪽 대각에 0이 있어야 더할수 있기 때문이다.
같을때는 왼쪽 대각에 있는 값에서 +1을 해주고, 다를때는 왼쪽 한칸, 위에 한칸 중 더 큰값으로 채워주면 된다.
->DCB와 ABC를 비교하는 곳을 보면 D와 A를 비교하는데 같지 않으니 왼쪽 한칸, 위에 한칸 중 더 큰값인 1로 채워주는데, 이 행위에 대해 생각을 해보면 전에 해왔던 결과를 끌어오는 느낌? 여기까지는 너가 미리 해놨는데 한단계 더해보니까 같네, 다르네 그러면 전에 해놨던 결과에 지금 비교한 결과가 같으니까 하나를 더하면서 대각으로 내려가, 다르니까 전에 해왔던 결과 중 큰거 가져와(어차피 최대한 큰 길로 갈꺼니까)
머리가 어지럽긴한데... 위에 방식을 설명한 코드는 다음과 같습니다.
DP(Bottom-up)
| # Time: O(n * m), Space: O(n + m) def dp(s1, s2): N, M = len(s1), len(s2) dp = [[0] * (M+1) for _ in range(N+1)] for i in range(N): for j in range(M): if s1[i] == s2[j]: dp[i+1][j+1] = 1 + dp[i][j] else: dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) return dp[N][M] |
1. dp 라는 배열을 만든다.
2. 비교하는 것들의 길이의 따라 for 문으로 비교하며 같으면 1 더해서 대각으로 다르면 오른쪽, 밑에 있는것중에 비교해서 큰거로 우대각에 있는거에 집어 넣는다.
3. 배열의 마지막에 있는게 LCS 값, 리턴한다.
Memoization ,DP(Bottom-up) 차이점.
글을 작성하다보니 궁금해서 GPT에 물어보니
| 요약 • 메모이제이션 (Top-Down): 재귀 호출을 이용하고, 캐시에 저장된 값을 재사용해 중복 계산을 피합니다. • DP (Bottom-Up): 반복문을 통해 작은 문제부터 순서대로 해결하여 최종 답을 구합니다. |
라고 합니다. 갓PT.
밑에는 메모리 효율성을 좀 더 높인 방법인데, 접근 방식은 어차피 내가 구하는 다음 행과 현재 내가 있는 행만 있으면 구할수 있는데 왜 모든 배열에 대한 정보를 다 가지고 있는가? 라는 질문에서 나온 방법이라고합니다...(효율성에 미친 사람들...)
사실 메모리 줄이고 속도 줄이는게 다 돈이긴 하니까요...
Memory Optimized Bottom-up
| # Time: O(n * m), Space: O(m) def optimizedDp(s1, s2): N, M = len(s1), len(s2) dp = [0] * (M + 1) for i in range(N): curRow = [0] * (M + 1) for j in range(M): if s1[i] == s2[j]: curRow[j+1] = 1 + dp[j] else: curRow[j+1] = max(dp[j + 1], curRow[j]) dp = curRow return dp[M] |
코드를 보면
dp = >0000
cur= >0000
이렇게 행이 두개가 있는데 비교 대상이 같으면 curRow[j+1]을 dp[j]에서 하나 더해서 넣어주고 그렇게 반복문 돌려서 curRow 다 채워준 다음에 curRow를 dp로 넘겨주고 그렇게 전dp는 버려지고 끝까지 두개의 행만 가지고 하다가 결국 dp[M]을 구해서 값을 찾아내는 놀라운 방법입니다.