BOJ 9251

안녕하세요 강의 잘 듣고 열심히 따라가고 있습니다. ㅎㅎ

Dynamic Programing 강의를 듣는 도중 궁금한점이 있어 질문 드립니다.

백준 9251문제는 Longest Common Subsequence를 구하는 문제인데

강의 내용에서 3가지 접근법인 브루트포스, 그리디, DP 순으로 설명해주시고 똑같이 따라하려고 노력하고 있습니다.

2가지 질문사항이 있습니다.

제가 생각해낸 풀이 Dictionary를 활용하여 LCS를 구하는 방법인데요. S1에 문자가 나온 횟수를 Dictionary로 저장하고 S2에 문자가 중복해서 나온 횟수를 빼주어 0이 되는 문자의 개수를 세는 방법입니다.

코드는 아래와 같이 작성하였습니다.

s1=list(input())

s2=list(input())

#print(s1,s2)

dicts = dict()

for i in s1:

if i not in dicts:

dicts[i]=1

else:

dicts[i]+=1

common=[]

for j in s2:

if j in dicts:

dicts[j]-=1

if dicts[j]==0:

common.append(j)

print(len(common))

감사합니다.

안녕하세요. 김승환님!

강의에서 언급한 다양한 풀이를 시도해보시고, 새로운 풀이까지 고민해보시는 모습 정말 보기 좋네요 ㅎㅎ

최장 공통 부분 수열(Longest Common Subsequence, LCS)의 정의는 두 문자열 또는 두 수열에서 공통으로 나타나는 부분 수열 중 가장 긴 것을 찾는 것이며, 다음과 같은 특징을 가집니다:

2번 질문부터 답변드리자면,

공유해주신 풀이는 딕셔너리 자료구조에 동일한 요소를 더하고 빼며 0이 되는 문자의 개수를 세는 방식으로 구현되어 있는데요.

문제의 요구사항이 각 문자열에 순서 상관없이 동일한 수만큼 포함된 요소의 길이를 구하는 것이었다면, 풀이하신 방법이 맞습니다.

하지만 LCS는 각 문자열에서 선택된 순서와 요소가 동일해야 하기 때문에 단순히 동일한 요소를 카운트해서 빼는 방식으로는 구할 수가 없습니다.

예외 케이스는 다음과 같습니다.

“ABCBDAB”

“BDCAB”

위 입력대로 LCS를 구해보면, “BCAB”입니다.

하지만 질문자님의 풀이대로라면, 2가 출력되는데요.

그 이유는 ABCBDAB, BDCAB 중에 동일한 갯수의 요소가 D, C이기 때문입니다.

1번 질문에 대한 답은,

풀이 논리가 어떤 풀이 방법에 속하는지 굳이 정의하자면, 브루트포스에 가깝다고 볼 수 있을것 같습니다.

브루트포스(Brute Force) 알고리즘은 문제 해결을 위해 가능한 모든 경우의 수를 시도해 보는 방법입니다.

공유해주신 풀이는 질문자님의 논리에 근거하여 딕셔너리 자료구조와 함께 s1과 s2 전체를 탐색했기 때문에, 논리에 맞는 모든 경우의 수를 시도해보는 방법에 가깝다고 보여집니다.

본래 LCS 풀이는 브루트포스로 풀이하려면 시간복잡도 O(2^m * 2^n)가 걸리지만, 질문자님 스스로의 논리에 근거하여 딕셔너리 자료구조를 활용하는 방법으로 이를 줄이려는 풀이로 볼 수 있을 것 같습니다.

또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.

감사합니다. :)

인프런 커뮤니티 질문&답변