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

1. 알고리즘 문제 해결

 

최소비용 구하기(백준 1916): 

 가중치가 음수인 간선이 없고, 시작점이 고정된 상태에서 최단 경로를 구하는 문제라 다익스트라 알고리즘으로 풀 수 있고, 가장 심플한 형태이다. 정점이라고 할 수 있는 도시의 개수가 1,000개 이하로 주어지기 때문에 O(V^2)의 시간복잡도로 풀어도 무방하겠지만, 굳이 그렇게 구현할 이유는 없으므로 우선순위 큐를 사용해 O((V+E)logV)의 시간복잡도로 풀었다.

 

 너무 잘 알려진 알고리즘이기에 이론적인 부분을 정말 간략하게 작성하자면..

 

- 시작점에서 향할 수 있는 노드를 찾아 비용 배열을 업데이트하고, 갈 수 없는 곳은 구현 상 들어올 수 없는 값으로 INF 처리한다.

- (노드, 비용) 정보들을 우선순위 큐에 집어넣고 비용이 작은 것이 top으로 올라올 수 있게 한다. 

 - 우선순위 큐의 top을 확인해 방문하지 않았던 노드라면 방문처리 하고, 그 노드와 인접한 노드들을 확인해서 기존에 가지고 있던 비용 배열과 비교한다. 만약 기존 비용 배열의 값(현재까지 구해둔 시작점->해당 노드 최소 비용)보다 현재 탐색 중인 노드까지의 최단경로+현재 탐색 중인 노드로부터 해당 노드까지의 비용 값이 작다면 배열을 업데이트하면서 우선순위 큐에 넣어준다.

- 이를 계속 반복해 주면 top이 목적지 노드일 때가 발생하는데, 이때 구해져 있는 최소비용을 출력해 주고 루프를 종료한다.

 

 이제 로직에 관한 내용 말고 구현에 관한 얘기를 잠깐 하자면 우선순위 큐의 우선순위가 보통 값이 큰 것이 우선순위가 높게 책정된 언어가 많으므로 이를 주의해야 한다. 내가 알고리즘 문제를 풀 때 사용하는 C++ 또한 그러한데, 이는 비용 값을 음수로 취한다든지, 아니면 연산을 위한 compare 구조체를 만들어 넣어서 해결해야 한다.

 보통 나는 부호를 바꾸는 방법을 주로 사용하는데, 이번 문제에서는 우선순위 큐 내에 Pair가 들어가기도 하고, 비교 기준에는 그중 하나의 인자만 사용하면 되는 케이스기 때문에 구조체를 직접 만들었다.

 

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#define INF 987654321

using namespace std;

struct cmp {

    bool operator()(pair<int, int> l, pair<int, int> r) {

        return l.second > r.second;

    }

};

int main() {

    int n, m, start, target, cost;

    cin >> n >> m;

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

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

        cin >> start >> target >> cost;

        adjList[start].push_back({target, cost});

    }

    cin >> start >> target;

   

    vector<int> costs(n+1, INF);

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

    costs[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp > pq;

   

    for(auto edge: adjList[start]) {

        costs[edge.first] = min(costs[edge.first], edge.second);

        pq.push({edge.first, edge.second});

    }

    isVisited[start] = true;

    while(!pq.empty()) {

        auto top = pq.top();

        pq.pop();

        if(isVisited[top.first]) continue;

        if(top.first==target) {

            cout << top.second;

            break;

        }

        isVisited[top.first] = true;

        for(auto edge: adjList[top.first]) {

            if(!isVisited[edge.first]) {

                if(costs[edge.first]>costs[top.first]+edge.second) {

                    costs[edge.first] = costs[top.first]+edge.second;

                    pq.push({edge.first, costs[edge.first]});

                }

            }

        }

    }

}

 

 

 알고리즘 과목을 수강할 때도 느꼈던 거지만, 그래프 알고리즘들은 정말 매력적이다. 현실의 문제로 바로 치환할 수 있는 경우가 많고, 로직도 잘 떠올라서 그런 것 같다.

 

 

 

2. 챌린지 반 실시간 세션

 월요일이라 챌린지 반 실시간 세션도 진행됐다. MVVM에 관한 간략한 설명과 사용하는 이유, 그리고 이를 안드로이드에서 구현하기 위해 AAC의 ViewModel 사용법도 안내해 주셨다. 아직까지는 알고 있는 범위 내였지만, 생각할 거리들을 같이 제안해 주셔서 더 좋았던 것 같다.

 또 이번 주의 과제로는 본 커리큘럼에서 만들었던 회원가입 과제의 일부를 MVVM으로 리팩터링 하는 것이 주어졌다. 크게 복잡한 것은 없고 단순히 ViewModel만 적용하면 되는 거라, 간단하게 해 볼 수 있을 것 같다. 

 

3. 사이드 프로젝트

 저번 금요일에 고민하던 문제를 마저 고민했는데, 아직은 저울질 중이다.

 사실 Content로 쓰일 아이템은 리스트(LazyColumn)에서 쓰일 listItem 형태로 래핑하고, 그것을 Error hadling을 위한 Result 같은 클래스로 래핑 할 생각이었어서 그냥 listItem에 isExpanded 값을 넣어버릴까 하는 생각도 든다. 그렇게 되면 새로 페이지 검색 시, 새로운 리스트로 바뀌기 때문에 문제가 해결될 것이다. 

 

 대신에 그렇게 처리한다면, 오로지 UI를 위해 존재하는 State가 프로퍼티 형태로 각 아이템 객체에 존재해야 하고, 이를 이용하려면 매번 ViewModel을 이용해 반영하고 갱신해야 한다. Content용 Composable이, ViewModel이 아닌 아이템을 받고 있어서 ViewModel을 이용하려면 상위 Composable로 이벤트를 올리거나 ViewModel 자체를 받아와야 하겠지만 이건 콜백 함수로 간단하게 해결할 수 있는 문제다.

 

 그럼에도 고민하는 건, ViewModel이 지엽적인 상태 처리를 위한 값을 데이터 리스트의 각 요소마다 들고 있는 게 올바른 형태인가? 또 ViewModel은 Domain 영역으로부터 Result로 래핑 된 값을 받게 될 텐데, 이를 매번 언래핑 해서 로직 처리를 하는 게 올바른가? 그리고 로직 상에 ViewModel을 거치도록 끼게 되면서 생기는 성능 상의 저하가 응당 감내할만한 부분인가? 등을 고민하고 있다.

 

 다른 방법으로는 상위 Composable인 LazyColumn쪽에서 해당 rememberSaveable한 State를 쥐고 넘겨주는 형태로 구현해, 내부에선 LaunchedEffect 등으로 초기 설정을 해주는 방법도 생각 중이다. 사실 이건 state hoisting 하는 것까진 좋은데, 그런다고 매 검색마다 해당 값들이 특정한 초기값을 가지게 할 수 있는가가 또 문제다. 검색에 관한 State를 만들어서 매 검색이 고유할 수 있도록 만들든가, 매 검색마다 변경되는 스위치 등을 이용한다면 불가능하지는 않을 것이다.

 

 그런데 LazyColumn 내에서 컨텐츠들이 파괴되고 생성되는 타이밍을 세심하게 캐치할 수가 없기 때문에, 생각대로 될지 의문이다. 검색으로 인해 내용물이 파괴되고 생성되는 건지, 스크롤로 인해 내용물이 파괴되고 생성되는 건지 이를 특정할 수 있을까..

 

 또 다른 방법으로는 위처럼 검색과 관련된 State를 이용해, 이를 하위 Content용 Composable에도 넘겨주고, 이를 remember api 쪽에 key로 넘겨주어 초기화를 유도하는 방법이다. 이는 아직 관련 내용에 익숙한 게 아니라서 될지 안될지는 불투명하다. 결국 rememberSaveable 내에 아이템을 고유하게 식별할 key와 현재 검색에 대한 식별 key가 주어져야 한다는 게 내 예상인데, 생각대로만 된다면 이쪽이 가장 합리적인 선택지가 될 것 같다. 내일 마저 건드려봐야겠다.