[TIL] 24.01.23

1. 알고리즘 문제 해결

 

외판원 순회 2(백준 10971):

 외판원 순회 문제(TSP) 문제는 이미지의 문제 설명에서도 나와있듯이, 굉장히 유명한 문제이다. 내 기억으로 NP-hard에 속하는 문제인데, 근사해를 찾는 것이 아닌 최적해를 찾는 알고리즘의 경우 가장 빨라도 지수시간이 걸렸던 것으로 기억한다. DP로 푸는 것과 Branch and Bound로 푸는 것을 배웠었는데, 두 쪽다 실제 코드로 구현하는 것은 만만하지 않다.

 이 문제는 도시의 수 범위가 최대 10개까지이므로, 사실 순열 문제로 치환해서 풀게 되면 (10-1)! 만큼의 탐색이 필요하므로, 무난하게 통과할 수 있을 것이다. 하지만 예전에 배웠던 것을 한 번 리마인드할 겸, DP와 비트마스킹을 이용해 풀기로 했다. 

#include <iostream>

#include <vector>

#include <algorithm>

#define INF 987654321

using namespace std;

int n;

vector<vector<int> > costMatrix;

vector<vector<int> > dp;

int TSP(int curV, int visitMask) {

    if(visitMask == (1<<n)-1) { //모든 정점 방문

        if(costMatrix[curV][0]==0) {

            return INF;

        }

        return costMatrix[curV][0];

    }

    if(dp[curV][visitMask] != -1) { //이미 방문함

        return dp[curV][visitMask];

    }

    dp[curV][visitMask] = INF;

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

        if(costMatrix[curV][i]==0) { //간선 연결 체크

            continue;

        }

        if((visitMask & (1<<i)) == (1<<i)) { //다음 정점이 방문한 곳

            continue;

        }

        dp[curV][visitMask] = min(dp[curV][visitMask], costMatrix[curV][i]+TSP(i, visitMask | 1<<i));

    }

    return dp[curV][visitMask];

}

int main() {

    cin >> n;

    costMatrix = vector<vector<int>>(n, vector<int>(n));

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

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

        for(int j=0; j<n; j++) {

            cin >> costMatrix[i][j];

        }

    }

    cout << TSP(0, 1);

}

 

 코드는 위와 같은데, 흔히 잘 알려진 풀이이다. 굳이 비트마스크를 이용해서 방문도시 집합을 나타내는 이유는 공간복잡도 때문이다. 배열이나 Set을 이용하는 것보다 훨씬 메모리를 적게 사용하며 속도도 빠르다. dp 테이블은 어떤 정점에서부터 아직 방문하지 않은 모든 정점을 순회했을 때 가질 수 있는 최소 비용을 담게 된다. 결국 저 TSP 함수는 재귀를 통해 base condition(모든 정점을 방문한 상태인 경우)에 도달할 때까지 작은 부분 문제로 나뉘어져 해결되는 것이다. 

 

 그리고 이런 방식으로 접근하게 되면

 

 브루트 포스로 절대 풀 수 없는 범위의 N이 주어지는 외판원 순회(백준 2098)도 해결할 수 있게 된다.

 

 

 

 

계란으로 계란치기(백준 16987):

 브루트 포스로 푸는 방법을 생각해보면, O(n^n)인데 N의 범위가 8까지이므로, 충분히 가능하다. 어느정도 백트래킹을 적용할 수 있는데다, 시간 제한도 2초라서 더 넉넉해보였다. 

#include <iostream>

#include <vector>

using namespace std;

int n, cnt=0;

vector<pair<int, int> > eggs;

void DFS(int current) {

    if(current==n) {

        int destroyed = 0;

        for(auto p: eggs) {

            if(p.first<=0) {

                destroyed++;

            }

        }

        cnt = max(cnt, destroyed);

        return;

    }

    bool flag = false;

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

        if(i!=current && eggs[current].first>0 && eggs[i].first>0) {

            flag = true;

            eggs[i].first -= eggs[current].second;

            eggs[current].first -= eggs[i].second;

            DFS(current+1);

            eggs[i].first += eggs[current].second;

            eggs[current].first += eggs[i].second;

        }

    }

    if(!flag) {

        DFS(current+1);

    }

}

int main() {

    cin >> n;

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

        int s, w;

        cin >> s >> w;

        eggs.push_back(make_pair(s, w));

    }

    DFS(0);

    cout << cnt;

}

 

 조금 특이할거라곤 flag를 사용한건데, flag가 true가 되는 경우는 현재 들고 있는 계란이 이미 깨진 경우거나, 다른 모든 계란이 깨진 경우이다. 이 경우엔 문제 조건에 의해 그냥 계란을 내려놓고 넘어가야 하기때문에, 이 경우에도 DFS를 지속할 수 있도록 처리해줬다.

 

 

2. 안드로이드 공부

 

 또 Material3의 차이로 강의와 동일하게 동작하지 않는 부분들이 있었다.

 

 

1. Scaffold 내의 topBar로 집어넣은 TopAppBar의 modifier의 background 속성이 적용되지 않고 있다.

2. TopAppBar 내의 title로 집어넣은 Text의 세로 중앙 정렬이 되지 않고 있다.

3. Scaffold의 content 내용물이 topBar의 크기를 고려하지 않고 있다.

 

1번 같은 경우에는, Material3의 TopAppBar의 경우 Modifier를 이용해 색상을 지정하는 것이 아닌 colors attribute가 따로 존재했다. TopAppBarColors를 인자로 받고있는데, 이를 바로 생성할 순 없고 TopAppBarDefaults.topAppBarColors()의 인자를 지정해서 생성할 수 있었다.

2번 같은 경우에는, 이게 이상적인 해결방안인지는 모르겠으나, Text를 바로 이용하는 것이 아니라 Row로 한번 감싸주었다. 그리고 그 Row에 대해 verticalAlignment를 설정해 본인의 내용물을 세로 중앙 정렬하도록 했다. 물론, Text에 지정했던 Modifier 관련 설정 값들은 Row쪽으로 빼주었다.

 

3번 같은 경우에는, 실제로 Material3 Scaffold의 content 람다를 열게 되면 웬 PaddingValues 값을 it으로 받게 된다. 이 또한 기존의 Material과는 다른 부분인데, 처음에는 그 용도를 몰라 따로 이용하지 않았다. 안드로이드 스튜디오에서 해당 값을 처리해야한다고 빨간줄을 띄웠기에, 그냥 이와 같이 방치해놓았었다.

 

 하지만 찾아보니 Material3부터는 저 값을 이용해 content padding을 사용자가 처리해주어야 한다는 것을 알게 되었고, 내용물들을 감쌀 Column을 하나 생성해 padding 값을 주어 이를 해결했다.

 

 저렇게 모든 부분을 수정해주고 나서야 아래와 같이 의도한 UI를 확인할 수 있었다.