HackerRank: 공통 하위(가장 긴 공통 후속) — JavaScript

반응형

해커랭크에 대한 공통 차일드 챌린지는 고전적인 LCS(Longest Common Sequence) 문제의 별명이다. 이 문제에 대한 링크는 다음과 같습니다.

시퀀스는 0개 이상의 문자가 삭제된 원래 문자열에서 파생된 새로운 문자열이며, 문자열에 남아 있는 문자의 상대적 순서를 변경하지 않습니다.

이 문제와 관련된 우리의 작업은 주어진 문자열 2개에 공통적인 가능한 가장 긴 연속의 길이를 찾고 반환하는 것이다. 공통 수열이 없으면 0을 반환합니다.

이 문제를 해결하기 위한 몇 가지 다른 접근법이 있다. 브루트 포스 접근법은 각 문자열에 대해 가능한 모든 수열을 생성하고 가장 긴 공통 수열을 찾는 것을 포함한다. 이는 기하급수적인 시간 복잡성을 의미하며, 이 과제에서 문자열 길이에 대한 제약 조건이 5000으로 증가하므로 테스트 시간이 초과될 수 있습니다.

 

육안 검사를 사용하여 이 두 글자의 공통적인 후속 결과를 찾으십시오.

a b d e f

a c d f

여러분은 아마 두 줄 사이를 왔다 갔다 하며 공통점을 유지하다가 결국 끝에 다다랐다는 것을 알아차렸을 것입니다. 그래서 비교와 보존의 요소가 둘 다 있었습니다. 매 순간 당신은 집중적인 하위 문제를 다루고 있었고, 그 해결책은 당신이 이미 확립한 것에 첨부되어 있었다.

본질적으로, 당신은 당신이 알았던 몰랐던 간에 동적 프로그래밍을 수행하고 있었다! 줄이 길면 진행 상황을 메모하고 자리를 지키기 위해 각 줄의 위치에 연필 포인트를 유지했을 수 있습니다.

 

하위 문제라는 단어를 들으면 재귀가 생각날 수도 있고(아닐 수도 있다!) 재귀는 분명 이 과제를 해결할 수 있는 방법이다. 시각 학습자이기 때문에 진행 상황을 추적하기 위해 테이블 접근 방식을 사용하기로 선택했지만, 각 비교에서 내린 결정을 설명하기 위해 실제 하위 문제를 살펴보는 것이 도움이 됩니다.

이 부분적인 문제들을 이해하기 위해서 끈의 끝 부분부터 비교를 시작하겠습니다. 왜일까요? 왜냐하면 현재 진행 중인 일의 길이에 대한 모든 결정은 그 전에 있었던 일에 달려있기 때문입니다.

a b d e f

a c d f

앞에 나온 것을 보지 않고, 두 "f"를 고려해야 할 때 이미 LCS의 길이를 알고 있다고 가정하자. 우리가 확실히 말할 수 있는 것은 공통 "f"s가 현재 공통 수열에 더해질 수 있기 때문에 LCS = 1 + LCS이다.

 

뒤로 작업:

a b d e

a c d

"e"와 "d"가 일치하지 않는데 어떻게 하죠? 이 시점에서, 우리는 "abd"와 "acd"에 대한 LCS 길이를 계산하고, "abde"와 "ac"에 대한 LCS 길이를 계산해야 합니다. 즉, 하나의 마지막 글자를 자르고 다른 문자열과 비교하여 LCS 길이를 구합니다. 그럼 다른 한 쌍은 반대로 해주세요. 이 경우 전자는 2개, 후자는 1개입니다. 그래서 우리는 가장 긴 것에 관심이 있기 때문에 2의 값을 취하겠습니다. 빈 문자열의 베이스 케이스에 도달할 때까지 더 거슬러 올라가도 되지만, 이 시점에서 2가 정확한지 육안으로 확인할 수 있습니다. 그리고 계속해서, f`s back을 더하면, 우리의 최종 LCS의 길이는 3입니다.

LCS("abdef", "acdf")는 3이다.

 

각 하위 문제에 대한 의사 결정 과정을 스케치했으므로 동적 프로그래밍 표를 작성할 수 있습니다.

하위 문제를 실행하려면 0이 있어야 하므로 빈 문자열의 기본 케이스를 추가했습니다. 이제 우리는 처음부터 줄을 비교할 수 있습니다.

빈 문자열이나 임의의 길이의 문자열을 빈 문자열과 비교하면 0이 됩니다. 그래서 우리가 글자를 비교하기 시작할 때 우리의 LCS는 0입니다.

비교:

"a"와 "a"는 대각선으로 왼쪽에 있는 셀을 바라본다. 이 셀은 두 개의 a가 제거될 때 문자열을 나타냅니다. 그래서 우리는 1을 더하고 셀을 채운다:

 

"a"와 "ab"(열 전체에 걸쳐 문자열이 누적됨) - 셀을 왼쪽과 위의 셀을 비교합니다. "a"와 "a"의 값을 ""와 "ab"의 이전 LCS 값을 살펴본 결과입니다. 최대값 1과 0을 입력합니다. 이 값은 1입니다.

이 방식으로 표를 채우고 오른쪽 아래에는 최종 LCS가 있습니다.

이제 하위 문제를 유사 코드화하면 됩니다.

 

• 크기가 s1.length + 1, s2.length + 1인 0으로 2차원 배열 lcs를 초기화합니다. 빈 문자열로 시작하는 추가 열과 행이 설명됩니다.
• lcs[i][j]를 통해 반복한다.
• 각 행 문자와 각 열 문자를 비교합니다.
• 값이 같으면 lcs[i -1][j — 1]에 있는 값에 1을 더하십시오.
• 또는 lcs[i — 1][j](위의 셀)와 lcs[i][j — 1(왼쪽 셀)의 최대값을 구하십시오.
• 테이블이 완성될 때까지 계속합니다.
• lcs[s1.length][s2.length]를 반환합니다.

그리고 자바스크립트의 마지막 코드는 다음과 같다.

이 코딩 도전은 제가 동적 프로그래밍의 표 기술을 사용하여 처음 접한 것입니다. 알고리즘의 이면에 있는 추론을 이해하고 그것을 표에 적용하는 데 시간이 좀 걸렸지만, 저는 그 과정이 복잡해 보이는 것을 추적해서 제가 머리를 감쌀 수 있는 아주 기본적인 하위 문제들로 요약하는 제 능력을 향상시켰다고 느낍니다. 이 코드를 약간 수정하면 다음 과제는 실제 결과 후속 결과를 반환하는 것입니다. 먹어봐. 그럴 거야!

해피 코딩!