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

1. 알고리즘 문제 해결

 

 

문제집(백준 1766):

 위상 정렬 문제인데, 우선순위 큐를 활용하는 문제이다. 기존에 사용하던 위상 정렬 로직에서 진입차수가 0인 노드를 찾아 저장해두던 자료구조를 큐 대신 우선순위 큐로 사용하고(min heap), 방문 처리 및 우선순위 큐에 넣는 타이밍을 조금 다르게 했다.

 그래프를 입력 받고, 초기의 진입차수가 0인 노드들을 찾아 우선순위 큐에 집어 넣는다. 이 때 집어넣으면서 미리 방문처리를 하도록 한다. 이후에 우선순위 큐의 top을 확인해 출력하고(현 시점에서 가장 먼저 풀 수 있고 쉬운 문제에 해당), 해당 노드의 인접 노드들을 확인한다. 인접 노드들의 진입차수를 1 감소시킨 뒤, 그 시점에 그 인접 노드들의 진입차수가 0이 되었는지와 방문여부를 바로 확인해준다. 이렇게 해야 매 시점 문제 조건에 맞는 최적의 순서로 출력할 수 있다.  

 만약 진입차수가 0이고 방문하지 않은 노드라면 이를 우선순위 큐에 넣고, 방문처리 해 중복해서 들어가는 것을 방지해준다. 이 과정들을 우선순위 큐가 빌 때까지 반복한다. 문제의 입력 조건에서 항상 문제를 모두 풀 수 있는 경우를 보장하고 있으므로, 추가적인 처리 없이 해당 과정으로 온전한 답을 찾아낼 수 있다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

    int n, m;

    cin >> n >> m;

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

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

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

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

        int a, b;

        cin >> a >> b;

        adjList[a].push_back(b);

        inDegree[b]++;

    }

    priority_queue<int> pq;

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

        if(inDegree[i]==0) {

            pq.push(-i);

            isVisited[i] = true;

        }

    }

    while(!pq.empty()) {

        int top = -pq.top();

        pq.pop();

        cout << top << " ";

        for(auto vertex: adjList[top]) {

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

            if(inDegree[vertex]==0&&!isVisited[vertex]) {

                pq.push(-vertex);

                isVisited[vertex]=true;

            }

        }

    }

}

 

 

 

 

2. 사이드 프로젝트

 어제 고민했던 이미지 로더는, Coil을 이용해 적용했다. 내부 이미지 로더는 네트워크에서 받아오는 용도로 쓸 수 가 없었고, 공식 문서에서도 Glide나 Coil을 권장하고 있었다. Coil에선 AsyncImage를 통해 Compose에 좀 더 편하게 적용 가능하기도 했다.

 

 

 

 그리고 LazyColumn 내에 사용될 Composable에서 한번 누르면 펼쳐진 상태로 보여지게 하기 위해 expanded라는 State를 보유하고 있었는데, 거기서 조금 문제가 생겼다. 아이템을 펼친 상태로 두고 LazyColumn을 아래로 내렸다가 다시 올라오면 상태가 초기화 되어버리는 것이었다. 아무래도 recomposition이 발생하면서 초기값인 false가 되어버리는 거 같았다.

 그래서 by rememberSaveable을 이용했더니 이제 펼쳐진 상태는 유지가 되는데 다른 문제가 발생했다. 특정 키워드를 검색해 아이템을 펼치고, 다른 키워드를 검색했다가 다시 처음의 키워드를 검색해 돌아오면 여전히 아이템이 펼쳐져서 보이는 것.

 

 이는 별로 바람직한 경험은 아닌거 같아서 처리를 해야할 것 같다. 그 밖에도 Compose를 적용하면서 튜터님과 여러가지 문제에 대해 고민했는데, Preview의 원활한 이용을 위한 Hilt 적용 방안이나 미디어 타입에 따른 Compsable 분리 등 바꿔야 할 게 많았다. 주말에 수정할 시간이 나면 좋겠는데..

 

다른 걸 검색하고 다시 검색해도 여전히 펼쳐진 녀석..