[백준] 5582번 공통 부분 문자열 파이썬 풀이
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. 풀이 DP 테이블을 활용하자 아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다. [백준] 9251번 LCS 파이썬 풀이 https://www.acmicp..
[백준] 12904번 A와 B 파이썬 풀이
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 1. 풀이 S에 말고 T에 집중하자 처음에는 S에서 T를 만들어 나가는 방식으로 접근했다. S 뒤에 A나 B가 붙는 모든 경우의 수를 고려하면, 그 수가 엄청나게 많아진다. 위 그림만 보아도, B 1글자에서 만들 수 있는 4글자 문자열은 2^(4 - 1) = 8개이다. 최악의 경우라면 S 길이가 1이고, T의 길이가 1,000일 때니까, 경우의 수는 무려 2^..
[백준] 9251번 LCS 파이썬 풀이
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 가장 뒤의 문자부터 검사하자 맨 뒤 문자부터 서로 비교하면서 (1) 같으면 두 문자열에서 동시에 마지막 문자를 제거하고 (2) 다르면 문자열1의 마지막 문자만 제거하거나 문자열2의 마지막 문자만 제거하는 식으로 2가지 갈래로 나누어 가자. 더 이상 문자열을 비교할 수 없을 때는, 그 동안 동시에 제거된 문자 (C, E)가 바로 두 문자열의 L..