[TIL] 24.04.09 알고리즘, 앱개발 숙련 주차

1. 알고리즘 문제 해결

 

LCS 2(백준 9252): 

 오랜만에 따로 알고리즘 문제를 풀었다. 캠프의 루틴에 따라 매일 매일 프로그래머스의 알고리즘 문제를 하나씩 풀고있긴 하지만, 결이 좀 다르다. 제시된 문제들이 비교적 간단하고, 백준 문제들처럼 입력과 출력, 제한 시간 및 메모리 등이 확실하게 주어지지 않는 문제도 많아서 알고리즘 사고를 연습하기 보다는 코틀린에 더 익숙해지는 용도로 쓰고 있다.

 한동안 팀 프로젝트를 진행하느라, 개인적으로 이렇게 알고리즘 문제를 풀지 못했는데 오랜만에 푸니까 더 재밌게 느껴지는 것 같다.

 

 이 문제는 알고리즘 과목을 수강하면 DP를 배우면서 한번쯤은 공부하는 문제가 아닐까 생각한다. 브루트 포스로 해결하자면 각각의 문자열의 길이가 n과 m이라고 했을 때, 시간복잡도가 O(n * 2^m)에 달할 것이다. 대강 생각해본거라 확실하지는 않지만, 한 문자열에 대해 모든 부분 수열을 만들어 보려면 O(2^n)만큼 걸릴 것이고 또 그걸 다른 문자열과 선형탐색으로 매번 비교해봐야 하니 맞을 것이다.

 여튼 수업 때 다루기도 하고, 이미 너무나도 잘 알려진 알고리즘 문제이기도 하다. 그 로직도 심플하다.

 

- 어떤 두 문자열 X, Y의 끝 문자가 같다면, 두 문자열의 LCS의 끝 문자도 당연히 같을 것이다. 그리고 X의 끝 문자와 Y의 끝 문자를 떼고 새로운 LCS를 생각할 수 있다.

- 만약 다르다면, 새로운 LCS는 X의 끝 문자를 뗀 경우와 Y의 끝 문자를 뗀 경우로 다시 생각해볼 수 있을 것이다.

- 최장 공통 부분 수열이므로, 당연히 두 선택지 중 더 긴 LCS를 만들 수 있는 쪽을 선택해야 한다.

- 끝 문자를 떼내다가 어떤 문자열의 길이가 0이 된다면 LCS 그 때의 LCS 길이는 0일 수밖에 없다.

- 이걸 점화식으로 만들면 아래와 같이 될 것이다.

그림판에 마우스로 써서 글씨가 좀 그렇다

 

- 식을 훑어봐도 알 수 있고, 개념을 그려봐도 알 수 있듯이 2차원 배열을 통해서 각 상태의 LCS 길이를 저장해둔다면 재사용해서 O(nm)만에 LCS 길이를 찾아낼 수 있을 것이다.

 

 이 로직을 간단하게 구현했고, 실제 LCS에 해당하는 문자열은 되추적을 통해 알아냈다. 되추적을 하는 방법은 너무 당연하지만, dp 배열의 가장 끝(dp[n][m])에 있는 값으로부터, 해당 값이 올 수 있던 경로를 반대로 찾아가면 된다. 되추적 과정에서 두 끝 문자가 일치하는 경우에 해당 문자를 LCS 문자열에 담아뒀다가 마지막에 출력해주면 끝이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    vector<vector<int> > dp(s1.size()+1, vector<int>(s2.size()+1, 0));

    for(int i=1; i<=s1.size(); i++) {
        for(int j=1; j<=s2.size(); j++) {
            dp[i][j] = (s1[i-1]==s2[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]));
        }
    }

    int i = s1.size();
    int j = s2.size();
    vector<char> revLcs;
    while(i>0 && j>0) {
        if(s1[i-1]==s2[j-1]) {
            revLcs.push_back(s1[i-1]);
            i--;
            j--;
        }else {
            if(dp[i-1][j]>dp[i][j-1]) {
                i--;
            }else {
                j--;
            }
        }
    }
    
    cout << dp[s1.size()][s2.size()] << "\n";
    for(int k=revLcs.size()-1; k>=0; k--) {
        cout << revLcs[k];
    }
}

 

 

 

2. 앱개발 숙련 주차

 오늘부로 이제 새로운 주차인 앱개발 숙련 주차에 진입했다. 

 

 

 ViewBinding이나 RecyclerView, Fragment 등 안드로이드 구현의 기본기를 배우는 주차인듯 했다. 인트로에 적힌 CRUD 때문에 통신이나 DB작업도 다루게 되나 했는데 훑어보니 그건 아닌 것 같았다. 

 

 

 전반적으로 어려운 내용은 없는 것 같다. 개인 과제도 확인했는데 이번에도 무리 없이 구현할 수 있는 내용들이었다. 확인하면서 구조는 머리 속에 다 그렸으니, 그리 오래 걸리진 않을 것 같다.

 오늘은 지급된 강의를 반절정도 들었는데, ViewBinding의 사용과 다양한 AdapterView들에 대해 설명하고 있었다. 실상 쓰는건, RecyclerView에 ListAdapter 쓰는 형태가 제일 많았던 거 같은데 GridAdapter 등은 처음 보는 개념이었다. 그래서 내가 예전에 학습하면서 놓친 부분이 있나 했는데, 아니나 다를까 강의에서도 실무에서 대부분 RecyclerView를 사용한다고 언급해서 안심했다.

 그래도 알고 있던 내용이라도 다시보고, 조금이라도 더 나아갈 수 있게 노력해야겠다. 챌린지반 공부도 진행하고, 사이드 프로젝트도 진행하는 것과 함께.