dynamic programming (동적 계획법) Manhattan Tourist problem(MTP), Longest Common Subsequences (LCS)

Manhattan Tourist problem (MTP)

- 격자 모양의 도로와 건물들 사이에서 최적의 경로를 찾는 것

 

여행자가 최대한 많은 여행지를 들리는 MTP문제의 예시

* (별): 여행자가 들릴만한 장소

->(화살표) : 도로

원 안의 숫자 : 들린 장소의 갯수

 

 

기존의 Recursive Algorithm(재귀 알고리즘)을 이용하여 문제를 MTP문제를 해결하려 할 경우 문제점:

1. 중복 계산: 재귀 알고리즘에서는 중복되는 부분 문제를 여러 번 계산하는 경우가 많습니다. 이로 인해 많은 시간과 연산 리소스가 낭비되며, 전체 알고리즘의 효율성이 크게 저하됩니다.
2. 메모리 사용: 재귀 알고리즘은 함수 호출을 통해 문제를 푸는데, 각 함수 호출은 스택 메모리에 저장되어야 합니다. 따라서 많은 함수 호출이 발생하면 스택 메모리가 급격히 증가하여 스택 오버플로우(stack overflow)가 발생할 수 있습니다.
3. 실행 시간: 중복 계산으로 인해 실행 시간이 증가할 수 있습니다. 특히 큰 입력에 대해 재귀 알고리즘이 상당히 느려질 수 있으며, 이는 실제 응용에서 제한적인 성능을 나타낼 수 있습니다.

동적 계획법을 사용하여 MTP를 해결하는 방법: 

1. 격자의 각 지점에 대해 최적의 경로 값을 초기화합니다.
2. 격자의 지점들을 순회하면서, 각 지점에 대해 이전 경로에서 얻을 수 있는 최적의 값을 계산합니다.
3. 도착 지점까지의 최적 경로 값을 계산합니다.
4. 도착 지점부터 역추적하여 시작 지점까지의 최적 경로를 찾습니다.

 

Longest Common Subsequences (LCS)

두 개 이상의 문자열에서 가장 긴 공통 부분 문자열을 찾는 문제입니다.

이는 DNA 서열 비교에 자주 사용되는 기술로, 유사한 구조를 갖는 DNA 서열을 찾아내는 데 도움이 됩니다.

 

ex)

• DNA 서열 1: AGGTAB
• DNA 서열 2: GXTXAYB

이 두 DNA 서열의 LCS는 "GTAB"입니다.

 

backtracking algorithm

Dynamic proframming 방법을 사용하여 LCS문제를 solve하는 예시:

https://concho.tistory.com/88

DNA sequence(DNA 시퀀스)에서 dynamic programming(동적 계획법) 이용 Longest Common Subsequences(LCS, 최장 공통

1. 먼저, 두 서열의 길이에 따라 (서열1 길이 + 1) x (서열2 길이 + 1) 크기의 행렬을 만듭니다. 이 예시에서는 8x8 크기의 행렬이 필요합니다.
2. 행렬의 첫 번째 행과 열을 모두 0으로 초기화합니다.
3. 행렬을 채우기 위해 각 행과 열에 대해 다음을 수행합니다:
   • 두 문자열의 현재 문자가 일치하면, 대각선 위에 있는 값에 1을 더합니다.
   • 두 문자가 일치하지 않으면, 왼쪽 값과 위쪽 값 중 더 큰 값을 선택합니다.

행렬의 마지막 값 (5)이 두 DNA 서열의 LCS의 길이입니다. 이제 이 행렬을 사용하여 역추적을 수행하면 실제 LCS 문자열을 찾을 수 있습니다:

• 역추적을 시작하기 전에, 현재 위치를 행렬의 마지막 셀(오른쪽 하단)으로 설정합니다.
• 현재 셀의 왼쪽 값과 위쪽 값을 확인합니다.
  • 대각선 위 셀에서 현재 셀로 이동한 경우 (즉, 두 문자가 일치한 경우), 현재 문자를 LCS 문자열에 추가하고 대각선 위 셀로 이동합니다.
  • 그렇지 않은 경우, 왼쪽 값과 위쪽 값을 비교하고 더 큰 값이 있는 셀로 이동합니다.
• 시작점에 도달할 때까지 이 과정을 반복합니다.

자세한 역추적 과정:

1. 오른쪽 하단 셀(5)에서 시작합니다.
2. 대각선 위 셀에서 현재 셀로 이동한 경우 (두 문자가 일치하는 경우), 현재 문자 'A'를 LCS 문자열에 추가하고 대각선 위 셀로 이동합니다.
3. 현재 셀(4)의 왼쪽 값과 위쪽 값을 비교합니다. 왼쪽 값과 위쪽 값이 같기 때문에 왼쪽 셀 또는 위쪽 셀 중 하나로 이동할 수 있습니다. 여기에서는 위쪽 셀로 이동합니다.
4. 대각선 위 셀에서 현재 셀로 이동한 경우 (두 문자가 일치하는 경우), 현재 문자 'T'를 LCS 문자열에 추가하고 대각선 위 셀로 이동합니다.
5. 대각선 위 셀에서 현재 셀로 이동한 경우 (두 문자가 일치하는 경우), 현재 문자 'G'를 LCS 문자열에 추가하고 대각선 위 셀로 이동합니다.
6. 현재 셀(2)의 왼쪽 값과 위쪽 값을 비교합니다. 왼쪽 값과 위쪽 값이 같기 때문에 왼쪽 셀 또는 위쪽 셀 중 하나로 이동할 수 있습니다. 여기에서는 위쪽 셀로 이동합니다.
7. 대각선 위 셀에서 현재 셀로 이동한 경우 (두 문자가 일치하는 경우), 현재 문자 'A'를 LCS 문자열에 추가하고 대각선 위 셀로 이동합니다.
8. 시작점에 도달했으므로 역추적을 완료합니다.

역추적 과정을 통해 찾은 LCS 문자열은 "ATGTA"입니다. 이 문자열은 두 DNA 서열 ATGTTAT와 ATCGTAC에서 가장 긴 공통 부분 문자열입니다.

 

Edit Distance

편집 거리(Edit Distance)는 두 문자열이 얼마나 다른지를 측정하는 방법입니다. 더 구체적으로 말하면, 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산 수를 나타냅니다. 편집 연산에는 대표적으로 세 가지가 있습니다:

1. 삽입(Insertion): 문자를 추가합니다.
2. 삭제(Deletion): 문자를 삭제합니다.
3. 대체(Substitution): 문자를 다른 문자로 교체합니다.