반응형 LCS3 [백준/C++] LCS 3 (No. 1958) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 어떻게 풀 수 있을까 고민을 많이 했다.단순한 LCS 와 다르게 3개의 문자열에 대한 LCS를 구하는 문제였기 때문이다. 처음에는 3중 for문을 이용해 a, b, c의 문자열이 같은지 비교하고 LCS를 구해 min값을 출력하면 되는 줄 알았지만, 반례가 존재했다. 그래서 2개의 문자열만 비교하는 방법을 확장해 문제를 풀었다.먼저 a, b, c 문자열의 각 i, j, k번을 비교해보자. 그리고 LCS[i][j][k]를 a_i, b_j, c_k번 문자열까지 비교한 경우의 LCS라고 가정하자. 그러.. 2024. 11. 12. [백준/C++] LCS 4 (No. 13711) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS를 찾는 문제인데, 특이한 조건이 있다.바로 수열의 크기 N이 주어지면 1~N의 숫자를 가진 순서가 다른 수열이 2개 주어진다는 것이다. 만약 이 조건을 대충 넘기고 그냥 풀게 되면 조건으로 주어지는 N이 10만이므로 일반적인 LCS로 문제를 풀게되면 O(N^2)으로 시간초과가 나게 될 것이다. 이제 어떻게 하면 O(N^2)보다 빠르게 문제를 풀 수 있을지 생각해보자. 잘 생각해보면 1~N의 숫자가 2개의 수열에 한 번만 등장하기 때문에 하나의 수열의 i번째 index가 다른 수열의 몇 번째 자리에.. 2024. 5. 26. [백준/C++] LCS 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS 문제로 Memoization을 잘 이용해 문제를 풀 수 있다. 풀이를 고민하다가 두 문자를 비교해 같은 경우 이전에 구했던 LCS를 이용해 경우를 추가하면 되겠다는 생각이 들었다. 그래서 이전의 결과를 이용하기 위해 2차원 배열을 만들고 다음과 같이 정의했다. (DP[i][j] = 1번 문자열의 1~i번 문자와 2번 문자열의 1~j번 문자를 이용해 LCS를 만든 경우의 최대길이) 이제 정의를 이용해 아래 예시를 따라가 보자. 그림에서 빨간 네모가 색칠해진 칸을 DP[i][j]라고 하자.그러면 이 경우.. 2024. 5. 8. 이전 1 다음 반응형
