seonjoo2030   2년 전

우선, 

QWEQWE

WERQWE

이런 문자열들이 입력으로 들어왔다면, 

첫 번째 문자열의 첫 번째 단어부터 선택하여 두 번째 문자열과 비교합니다.

그리고 같은 부분이 있으면 문자를 배열에 저장시키고, 두 번째 문자열에서 같은 단어가 나온 다음 부분부터 

첫 번째 문자열의 두 번째 문자와 비교합니다. 

이런 방법으로 첫 번째 문자열을 기준으로 비교하고, 다음으로 두 번째 문자열을 기준으로 다시 검사합니다.

그런 다음 그 중에 최장길이인 것을 찾아 출력하게 했습니다.

A

AAAA 

이거나 혹은 그 반대도 제대로 나오긴 합니다. 

상식적으로 생각해 봤을 때, 최악의 경우, 1000개의 문자를 각각 1000번 씩 검사하고, 반대로 또 검사해서

엄청 많이 검사를 해야 하는 것이라 런타임 에러가 나는 것 같은데, 이 이유 때문에 LCS 알고리즘을 사용할 수 밖에 

없는 것인가요??

djm03178   2년 전

검사를 엄청 많이 하는 것은 런타임 에러와는 무관합니다. 단순히 너무 많은 작업을 하는 게 문제라면 시간 초과를 받습니다. 런타임 에러는 프로그램에게 허용되지 않은 동작을 해야 납니다.

의심이 가는 곳은 45번째 줄인데, t + size는 res에 할당된 메모리 범위를 초과할 수 있어 보입니다.

seonjoo2030   2년 전

감사합니다. 해당 부분 배열 길이를 늘려 수정을 했습니다. 

런타임 에러는 사라졌지만, 틀렸다고 나옵니다..

아무리 생각해도 어디가 틀린 것인지 잘 모르겠습니다. 

첫 번째 문자열과 두 번째 문자열에 모든 문자에 대해서 경우의 수를 다 구한 것 같은데 제가 실수한 부분이 어딘지 모르겠습니다 ㅜㅜ

djm03178   2년 전

반례들입니다.

seonjoo2030   2년 전

감사합니다 ㅜㅜ 

이런 반례들을 찾기가 너무 어렵네요...

최적해의 일부분이 최적해가 되지 않는 경우가 있더군요...

그냥 LCS알고리즘으로 풀어야 하나 봅니다...ㅜㅜ

아무튼 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.