최장 공통 부분 수열2 DNA sequence(DNA 시퀀스)에서 dynamic programming(동적 계획법) 이용 Longest Common Subsequences(LCS, 최장 공통 부분 수열) 찾는 python 코드 두 문자열의 Longest Common Subsequence (LCS)를 찾는 알고리즘을 구현한 것입니다. LCS는 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 문자열입니다. 동적 계획법을 사용하여 LCS를 찾는 과정: lcs 함수는 두 문자열 X와 Y를 입력으로 받아 LCS를 계산합니다. 문자열의 길이 m과 n을 구하고, (m+1) x (n+1) 크기의 행렬 dp을 초기화합니다. 동적 계획법을 사용하여 행렬 dp을 채웁니다. 행렬의 각 요소는 해당 위치까지의 두 문자열의 부분 문자열들 간의 LCS 길이를 저장합니다. 행렬 dp에서 LCS를 추출하는 백트래킹 과정을 수행합니다. 이를 통해 실제 LCS 문자열 lcs_str을 구합니다. 먼저 lcs 함수를 최적화를 위해 한 번 호출하고,.. 2023. 4. 4. dynamic programming (동적 계획법) Manhattan Tourist problem(MTP), Longest Common Subsequences (LCS) Manhattan Tourist problem (MTP) - 격자 모양의 도로와 건물들 사이에서 최적의 경로를 찾는 것 여행자가 최대한 많은 여행지를 들리는 MTP문제의 예시 * (별): 여행자가 들릴만한 장소 ->(화살표) : 도로 원 안의 숫자 : 들린 장소의 갯수 기존의 Recursive Algorithm(재귀 알고리즘)을 이용하여 문제를 MTP문제를 해결하려 할 경우 문제점: 중복 계산: 재귀 알고리즘에서는 중복되는 부분 문제를 여러 번 계산하는 경우가 많습니다. 이로 인해 많은 시간과 연산 리소스가 낭비되며, 전체 알고리즘의 효율성이 크게 저하됩니다. 메모리 사용: 재귀 알고리즘은 함수 호출을 통해 문제를 푸는데, 각 함수 호출은 스택 메모리에 저장되어야 합니다. 따라서 많은 함수 호출이 발생하.. 2023. 4. 4. 이전 1 다음
