'9251' 태그의 글 목록

Notice

Recent Posts

Recent Comments

Link

Tags more

Archives

Today

Total

관리 메뉴

목록9251 (1)

Hello Ocean! 🌼

[알고리즘 스터디] 백준 #9251 LCS

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. => 연속하지 않아도 된다는 것이 포인트. 풀이 2차원 cache를 이용한 DP 방식으로 풀면 된다. 말로 풀어 쓴 것은 이해하기 힘드므로 그림을 그려보았다. s1 = ACAYKP s2 = CAPCAK 를 입력했을 때 cache의 모습이다. cache[i][j]에는 s1의 i 번째와 s2의 j 번째가 같을 때 값이 채워진다. (같지 않은 경우에는 0이 채워진다) 둘이 같을 때, 그냥 1을 채우는 것이 아니라 지난 구역에서 가장 큰 값+1을 채운다. 첫 번째 그림에서 빨..

Algorithm 2020. 4. 19. 00:36

이전 Prev 1 Next 다음

목록9251 (1)

Hello Ocean! 🌼

티스토리툴바