[TIL] 24.03.21 알고리즘, 사이드 프로젝트

1. 알고리즘 문제 해결

 

 

ACM Craft(백준 1005): 

 위상 정렬 문제인데, DP의 개념을 적용해야 한다. Kahn 알고리즘을 이용해 위상 정렬을 하되, 그 과정에서 진입차수를 빼줄 때 최소 시간 요구치를 함께 업데이트해줘야 한다. 그리고 큐에서 front를 확인할 때, 해당 건물번호가 승리를 위해 필요한 건물의 번호라면 그 건물을 짓는데 필요한 최소 시간 요구치를 출력해 주면 된다.

 

 위상 정렬을 위한 기본적인 알고리즘 구현 방식은 저번 게시물( [TIL] 24.03.20 알고리즘 (tistory.com) ) 참조.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    cout.tie(nullptr);

    int T, n, k, target;

    cin >> T;

    for(int t=0; t<T; t++) {

        cin >> n >> k;

        vector<vector<int> > adjList(n+1, vector<int>());

        vector<pair<int, int> > inDegree(n+1, {0, 0}); // { inDegreeNum, timeToNeed }

        vector<int> timeTake(n+1);

        vector<bool> isVisited(n+1, false);

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

            cin >> timeTake[i];

        }

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

            int a, b;

            cin >> a >> b;

            adjList[a].push_back(b);

            inDegree[b].first++;

        }

        cin >> target;

        int time = 0;

        queue<int> q;

        bool getGoalFlag = false;

        while(true) {

            bool flag = false;

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

                if(inDegree[i].first==0 && !isVisited[i]) {

                    q.push(i);

                    flag = true;

                }

            }

            if(!flag) break;

            while(!q.empty()) {

                int front = q.front();

                q.pop();

                if(front == target) {

                    cout << inDegree[front].second+timeTake[front] << "\n";

                    getGoalFlag = true;

                    break;

                }

                isVisited[front] = true;

                for(auto vertex : adjList[front]) {

                    if(inDegree[vertex].first>0) inDegree[vertex].first--;

                    inDegree[vertex].second = max(inDegree[vertex].second, inDegree[front].second+timeTake[front]);

                }

            }

            if(getGoalFlag) break;

        }

    }

}

 

 

 

2. 사이드 프로젝트

ViewModel을 Compose UI에 적용해보고 있다. 

 

 

 만들어둔 Composable에서 searchViewModel을 참조하고 있는데, 이는 타고 올라가보면 Activity에 주입된 ViewModel을 참조할 수 있도록 했다. 그리고 LazyColumn도 간단하게 테스트하려고 content를 items로 구성해 놨었는데, 성능을 위해 itemsIndexed를 이용하도록 변경했다. 

 

 

 key 값으로 마땅한 것이 보이지는 않았다. 처음에는 PagingSource쪽에서 검색어 쿼리를 이용해 아이디를 직접 만들어 붙여 보낼까 생각도 했는데, 그렇게 되면 검색어는 다르지만 내용은 같은 이미지, 영상에 대해 다른 id를 부여하는 치명적인 결함이 생길 것이다. 그렇다고 링크의 url을 사용하자니 검색의 단위가 게시물이 아니기 때문에 한 게시물 내에서 이용된 이미지가 여러 개 검색되는 경우에 난감해진다. 그래서 썸네일의 url을 key값으로 주기로 했다. 이는 각 이미지나 영상 별로 고유한 값을 갖고 있으니까.

 

 그리고 테스트를 위해 간단하게 각 mediaItem의 내용 문자열 하나만 넘겨 확인하던 것을, 본격적으로 이용하기 위해 mediaItem 자체를 참조할 수 있게 바꾸었다. 물론 이는 하위 Composable에서 state로 쥐고 있게 된다.

 

 이제 저 item으로부터 값들을 꺼내어 내용물들을 생성하는데, 간단하게 info와 date만 출력되게 해보았다. 그러려면 UI 동작을 통해 실제 쿼리를 수행할 수 있도록 해야 한다. 

 

Composable

실제 이용하는 부분에서 넘기는 함수

 

 

 적당히 콜백함수를 받을 수 있게 해두고, SearchBar 내의 속성들을 적절하게 이용해서 구현했다. Ime 쪽을 어떻게 쓸지 정해두지 않아서, 관련된 부분들은 아직 비워둔 상태이다. Compose를 공부할수록, 함수가 일급 객체인 특징이나 구조 분해와 같은 코틀린의 강점들이 크게 와닿는 것 같다.

 이렇게 또 최소기능에 최소기능만을 더해 구현해두고 실제로 실행해 보니 아래와 같이 잘 실행되었다. 검색어를 바꿔서 다시 검색했을 때도, 성능 저하 없이 잘 동작하는 것처럼 보인다.

 

 

 

 뿌려지는 데이터가 조금 이상할 때도 있었는데, 직접 구현한 PagingSource 내에서 로직상 빼먹은 부분이 있어 간단하게 수정해 해결했다(새로 검색결과를 받을 때, 쥐고 있는 리스트를 초기화를 안 해서 생기는 문제였음).

 이미지를 어떻게 할 지도 고민을 해야하는데, xml의 리사이클러뷰였다면 아마 Coil이나 Glide를 이용했겠지만, Compose는 자체적인 이미지 로더가 꽤 준수했던 것으로 기억하고 있다. 아마 이건 내일 찾아서 비교해 보고 적용하게 될 것 같다. 스크롤의 끝을 감지해서, 추가 페이지를 로드해 오도록 하면 검색을 위한 로직은 얼추 마무리되지 싶다.

 다음은 내부 DB와 좋아요 기능 구현이나, 에러 핸들링을 위한 클래스 wrapping 등을 손대야 한다.