목록부분수열 (2)

미새문지

크래프톤 정글 week03, day24 - 알고리즘 문제

가장 긴 부분수열 수열 A가 입력되면 가장 긴 증가하는 부분 수열 구하기 import sys input = sys.stdin.readline def longLCS(a): # 받은 문자열의 길이를 체크 length = len(a) # 처음 시작을 1로 해야 원소가 처음 나올때 1이 체크된다. list = [1]*length # 처음껀 비교대상이 없기 때문에 1부터 시작 for i in range(1, length): # i 이전 수들끼리 비교해야 하기 때문에 i까지 반복 for j in range(i): # i값이 j값보다 크고(증가 수열) 리스트에 i를 넣었을 때 기존 리스트보다 길면 갱신 if a[i] > a[j] and list[i] < list[j]+1: list[i] = list[j]+1 # 리스..
크래프톤 정글/TIL 2024. 2. 20. 01:04
크래프톤 정글 week03, day19 - LCS 문자열 방식, 부분 수열 방식

LCS(Longest Common Subsequence) 공통 부분 문자열 중 가장 길이가 긴 문자열을 말하는 ‘최장 공통 부분 수열’이라고 한다. LCS는 최장 공통 문자열이라고도 불리는데 그 차이는 최장 공통 부분 수열은 문자열 안의 공통된 문자를 다 구한다 최장 공통 문자열은 문자열 안의 공통된 문자 중 연속된 문자를 구한다. 다이나믹 프로그래밍(DP)방식으로 구현된다. ​ LCS - Substring(최장 공통 문자열) 두 문자열을 비교하는 표인데 이 때, 반드시 두 문자열의 가장 앞 칸은 0으로 해야 한다. 만약 두 문자열 중 어느 것이라도 첫 번째 문자가 일치하면 그 좌표의 -1 좌표에서 값을 참조해야 하는데 [0, 0]이면 앞 칸이기 때문에 음수로 참조하게 되고 에러가 발생한다. 최장 공통 ..
크래프톤 정글/TIL 2024. 2. 20. 00:46
이전 Prev 1 Next 다음