[TIL] 24.03.29 알고리즘, 사이드 프로젝트, CS 리마인드

1. 알고리즘 문제 해결

 

특정한 최단 경로(백준 1504):

 시작 정점이 정해져있고, 각 edge의 비용에 음수가 존재하지 않으므로 다익스트라 알고리즘을 통해 최단거리(최소비용)를 구할 수 있다. 대신 주어진 두 정점을 반드시 거쳐야 한다. 요즘 계속 풀었던 그 패턴인데, 이번 문제도 마찬가지로 조건 별로 나누어서 비용 배열을(코드의 visited vector) 처리해줄 필요가 있다.

 

 등장할 수 있는 조건은 두 정점 중 아무것도 거치지 않은 경우, v1만 거친 경우, v2만 거친 경우, 두 정점 모두 거친 경우로 총 4가지이다. 주어지는 정점의 수가 작기 때문에, 비용 배열의 크기는 문제되지 않을 것이다. 다익스트라 알고리즘에 사용할 우선순위 큐의 경우, 비용이 적은 선택지를 최우선으로 두었고 비용이 같다면 조건을 더 많이 충족한 선택지가 높은 우선순위를 가지도록 했다.

 

 조건 충족 상태는 v1, v2에 대해 각각 bool로 들고 있다가 필요한 연산은 모두 비트 연산을 통해 처리했는데, 이럴거면 애초부터 bool 두 개를 들고 있을게 아니라 int 하나로 들고 있을 걸 그랬다. 크게 의미는 없지만서도..

 그리고 이 문제는 조건을 충족하는 경로가 존재하지 않을 수 있으므로, 루프 아래에는 -1을 출력할 수 있도록 하고 마무리 했다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 2000000000

using namespace std;
typedef pair<pair<int, int>, pair<bool, bool> > pp; //{{cost, vertex},{v1Visited, v2Visited}}

struct cmp {
    bool operator() (pp& l, pp& r) {
        int lVisit = l.second.first + l.second.second;
        int rVisit = r.second.first + r.second.second;
        
        if(l.first.first == r.first.first) {
            return lVisit < rVisit;
        }else {
            return l.first.first > r.first.first;
        }

    }
};

int main() {
    int n, e;
    cin >> n >> e;
    vector<vector<pair<int, int> > > adjList(n+1); //vertex, cost
    int a, b, c;
    int v1, v2;

    for(int i=0; i<e; i++) {
        cin >> a >> b >> c;
        adjList[a].push_back({b, c});
        adjList[b].push_back({a, c});
    }
    cin >> v1 >> v2;

    vector<vector<int> > visited(n+1, vector<int>(4, INF)); //0: none, 1: v1, 2: v2, 3: v1&v2
    priority_queue<pp, vector<pp>, cmp> pq;
    if(v1 == 1) {
        visited[1][1] = 0;
        pq.push({{0, 1}, {true, false}});
    } else {
        visited[1][0] = 0;
        pq.push({{0, 1}, {false, false}});
    }

    while(!pq.empty()) {
        int curCost = pq.top().first.first;
        int curNum = pq.top().first.second;
        bool curV1Flag = pq.top().second.first;
        bool curV2Flag = pq.top().second.second;
        pq.pop();

        int state = (curV2Flag<<1)+curV1Flag;

        if(curNum==n && state==3) {
            cout << curCost;
            return 0;
        }

        if(visited[curNum][state]<curCost) continue;

        for(auto next: adjList[curNum]) {
            int nextNum = next.first;
            int nextCost = curCost+next.second;
            if(nextNum == v1) {
                if(visited[nextNum][state|1]>nextCost) {
                    visited[nextNum][state|1] = nextCost;
                    pq.push({{nextCost, nextNum}, {true, curV2Flag}});
                }
            }else if(nextNum == v2) {
                if(visited[nextNum][state|2]>nextCost) {
                    visited[nextNum][state|2] = nextCost;
                    pq.push({{nextCost, nextNum}, {curV1Flag, true}});
                }
            }else {
                if(visited[nextNum][state]>nextCost) {
                    visited[nextNum][state] = nextCost;
                    pq.push({{nextCost, nextNum}, {curV1Flag, curV2Flag}});
                }
            }
        }
    }

    cout << "-1";
}

 

 

2. 사이드 프로젝트

 기존에 생겼던 expanded가 재검색시에도 유지되는 문제를 해결했다. 

 

 

 이런식으로 rememberSaveable에 key값으로 검색 이벤트마다 달라지는 값을 넣어서 해결하려고 했고, 생각대로 잘 동작해주었다. 지금은 ViewModel 차원에서 검색 요청 때마다 랜덤한 숫자를 내보내는 StateFlow를 이용하고 있는데, 나중에 객체의 해시코드를 넘길까싶기도 하다. 아니면 특정한 로직에 의해 고유할 수 있는 id값을 생성하도록 하든가. 희박한 확률이지만 중복 키가 발생할 수도 있으니까..

 

 

 그리고 하는 김에 이미지와 영상 컴포넌트 composable을 분리했다. 영상 컴포넌트의 경우 클릭했을 때 펼쳐지는 로직을 사용하지 않을 것이기도 하고, 이미지와 영상쪽에 각각 사용되는 아이콘도 다른 것이 존재한다. 그리고나서, 이제 raw한 데이터를 받을 것이 아니라 Result로 감싸 에러처리도 겸할 수 있도록 래핑할 클래스들도 만들었다.

 

 

 여기서 이제 병합된 미디어 리스트에 로컬 DB(좋아요 여부)를 언제 병합할 것인지, 그리고 Result 클래스로 래핑은 언제 해야하는지가 궁금했다. 이런 부분이 오면 확실히 경험치가 필요한 부분들이 많다는 것을 느낀다.

 그래서 이 부분을 튜터님께 질문드려서 꽤 오랜시간 이야기를 나누었다. 질문 드린 부분에 대한 설명을 듣느라도 있었지만, 기존에 구현해뒀던 MediaSearchPagingSource를 전면 수정해야 했다.

 

 나는 해당 소스쪽에서 이미지 API 및 동영상 API의 결과를 받아와서 병합하고, 통합된 결과에 대한 페이징 처리를 해서 Presentation쪽에 뿌려주도록 하고 있었다. 하지만 튜터님께서 그렇게 되면 Data 레이어쪽에서 Presentation에 의존성을 가지는 형태가 될 수 있다고 하셨고, 또 Presentation 레이어가 여럿일 때 혹시 동시에 다음 페이지를 요청하게 됐을 때 위험성에 대해 설명해주셨다. Paging3 라이브러리를 어설프게 입맛대로 구현해서 응용하려다가 놓친 부분이 많았다.

 튜터님께서는 해당 통합된 리스트에 대한 페이징 처리를 ViewModel쪽에서 하도록 권장하셨다. 처음에는 나름 거대하다싶은 이 로직이 다 내려갈 수 있나 싶었는데, 생각해보니 그냥 페이징처리만 안 한 병합 데이터를 받으면 되니까 가능하겠다 싶었다. 

 

 원래는 DB와의 병합 및 Result 클래스로의 래핑 시점이 정해지면 후딱 구현하고, 로컬 DB 구현을 시작하려고 했는데 아무래도 이쪽 대공사를 먼저 해야할 것 같다. 그래도 오늘 튜터님과 나눈 대화는 나한테 정말 좋은 경험치가 된 느낌이라, 대공사가 부담스럽게 느껴지진 않는 것 같다. 얼른 이 사이드 프로젝트도 깔끔하게 끝내고, 예전에 만들던 또 다른 앱 리팩터링을 시도해 보고싶다.

 

3. CS 리마인드

[운영체제] 2. OS 서비스 (tistory.com)

[운영체제] 2. OS 서비스

 

느긋하게 쓰다보니 늦어졌지만, 오늘 또 글 하나를 마무리할 수 있었다.