[TIL] 24.01.19

1. 알고리즘 문제 해결

 

트리와 쿼리(백준 15681):

 임의의 루트와 간선의 정보가 주어지기 때문에, DFS나 BFS로 트리 내의 부모 자식 관계는 찾아낼 수 있다. 물론 그 정보를 바탕으로 각 쿼리에 대해 매번 탐색을 통해 서브트리의 정점 수를 세면 O(N*Q)로 당연히 시간 초과가 난다. 그래서 DP 문제를 풀듯이 각 정점을 루트로하는 서브트리의 정점 수를 저장해놓고, 쿼리들에 대해 바로 답을 출력해주도록 해야한다.

 나는 그 값들을 트리를 구축하면서 함께 구해버리기 위해 재귀를 통한 DFS를 사용했다. 유의해야하는건, 서브트리를 구성하는 정점의 수에 본인도 포함해야 한다.

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int> > adjacentList;

vector<int> subtreeVertexNum;

vector<int> parent;

int getSubNum(int v) {

        int subNum=0;

        for(auto n: adjacentList[v]) {

            if(parent[v]!=n) {

                parent[n] = v;

                subNum+=getSubNum(n);

            }

        }

       

        subNum++;

        subtreeVertexNum[v] = subNum;

        return subNum;

   

}

int main() {

    cin.tie(nullptr);

    cout.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int n, root, query;

    cin >> n >> root >> query;

    adjacentList = vector<vector<int> >(n+1, vector<int>());

    subtreeVertexNum = vector<int> (n+1, 0);

    parent = vector<int> (n+1, 0);

    for(int i=0; i<n-1; i++) {

        int v1, v2;

        cin >> v1 >> v2;

        adjacentList[v1].push_back(v2);

        adjacentList[v2].push_back(v1);

    }

    getSubNum(root);

    for(int i=0; i<query; i++) {

        cin >> n;

        cout << subtreeVertexNum[n] << "\n";

    }

   

}

 

코드는 위와 같다.

 

 

 

회사 문화 1(백준 14267): 

 이것도 위 문제와 비슷하게 DP+트리 문제이다. 칭찬 수치는 별 조건 없이 자신의 부하 직원들에게 재귀적으로 전달되고 단순 합이다. 그래서 칭찬 정보가 주어질 때마다 트리를 탐색하면서 부하직원(자식 노드 및 후손 노드)들에게 칭찬 점수를 업데이트 해줄 필요가 없다. 각 직원마다 받은 칭찬 점수를 모두 더해놨다가, 모든 칭찬에 대한 정보를 받고나서 최종적으로 업데이트 하면 된다.

 나는 특정 직원을 지정했을 때, 사장까지 상사 직원을 타고 올라갔다가 다시 역순으로 점수를 업데이트 할 수 있도록 했다. 물론 이 정보들은 저장해두고 재사용한다.

#include <iostream>

#include <vector>

using namespace std;

vector<int> parent;

vector<int> getScore;

vector<int> finalScore;

int getFinalScore(int n) {

    if(finalScore[n]==-1) {

        if(parent[n]!=-1) {

            finalScore[n] = getScore[n]+getFinalScore(parent[n]);

        }else {

            finalScore[n] = 0;

        }

    }

    return finalScore[n];

}

int main() {

    cin.tie(nullptr);

    cout.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    parent = vector<int>(n+1);

    getScore = vector<int>(n+1, 0);

    finalScore = vector<int>(n+1, -1);

    for(int i=1; i<=n; i++) {

        cin >> parent[i];

    }

    for(int i=0; i<m; i++) {

        int num, w;

        cin >> num >> w;

        getScore[num] += w;

    }

    for(int i=1; i<=n; i++) {

        cout << getFinalScore(i) << " ";

    }

   

}

 

 코드는 위와 같다. solved.ac 기준 난이도는 이 문제가 윗 문제보다 높다고 되어있는데, 오히려 이쪽이 아예 부모 노드를 입력 받고 시작할 수 있어서 이 문제가 훨씬 덜 수고스러웠다.

 

 

부분수열의 합(백준 1182):
 부분 수열의 합이라길래 누적합 배열 이용해서 O(n^2) 브루트 포스로 해결하려고 했는데, 제출하자마자 틀렸다. 주어진 예제도 부실해서 갈피를 못 잡고 있었는데, 알고 보니 내가 너무 당연하게 연속 부분 수열이라고 생각하고 풀고 있었다. 생각해보면 LIS나 LCS 문제를 풀 때는 당연하게 부분 수열은 연속할 필요 없다고 생각했었는데, 이번엔 왜 그랬는지 모르겠다.

 착각하고 있던걸 바로잡고나니, 모든 부분집합을 탐색해봐야 하는 조합문제가 되었다. 하필 수열엔 음수와 0이 존재할 수 있어서 탐색 중에 pruning 할 수 있는 케이스가 거의 없을 거 같았다. 그래서 무식하게 (1Cn+2Cn+...+nCn)n 번의 탐색이 필요할 거 같았는데, n이 작아서 얼추 가능하지 싶었다. DFS와 백트래킹으로 구현하고 통과했다.

 

 

2. 안드로이드 공부

 

 안드로이드에서 기본적으로 제공되는 BuildConfig를 import 할 수가 없는 문제가 생겼다. 찾아보니 Android Gradle Plugin 8.0 이상의 버전에서는 BuildConfig가 기본적으로 생성되지 않는다고 한다. 아무래도 java 코드이다 보니 성능 상의 이유로 불필요한 생성을 막아두는 방향인 것 같다. 얼마 전에 AGP를 최신버전으로 업데이트 했었는데, 그래서 처음보나 싶기도 하고.

 조금 더 찾아보니 build.gradle의 buildFeatures에서 buildConfig = true로 주면 활성화 할 수 있다길래, 리빌드까지 해주고 나서야 해결할 수 있었다. 그러면서 사소한 문제도 발견해서 해결했는데

 

kotlin-gradle-plugin의 버전관리를 위해 사용되는 kotlin_version이 원래 강의와 같은 '1.9.20'으로 되어 있어서 무슨

java.lang.IllegalStateException: Unsupported metadata version. Check that your Kotlin version is >= 1.0

 

이러한 오류가 발생했는데, 이것도 처음보는 오류였다. 

 

알고보니 내 코틀린 버전은 1.9.22였고 값을 맞춰주니 해결되었다.. 항상 느끼는거지만 저런 dependency들이나 플러그인 버전 관리해주는 부분에서 신경 쓸 곳이 많은 것 같다. 학교 다닐 때 파이썬의 가상환경을 셋팅하면서 참 번거롭다고 느꼈는데 이제와서 생각해보면 오히려 그게 궁극적으로는 버전 관리를 한결 편하게 주는거였다.

 

 

 

+ 해결된 줄 아니었는데, 막상 retrofit 관련 repository랑 인터페이스들 구현해놓고 디버그 모드로 빌드했더니 또 오류가 생겼다. 아무래도 사용 중인 Hilt의 버전과 지금 코틀린의 버전이 호환 자체가 안되는 거 같다. 찾아보고 수정해야 할듯..