[TIL] 24.01.25

1. 알고리즘 문제 풀이

 

 

순열장난(백준 10597):

 백트래킹으로 구현하는 문제. 주어지는 수열의 길이로 N을 알아낼 수 있고, 조금 신경써서 백트래킹 조건을 설정해주면 된다. 나는 수열의 끝까지 탐색이 끝났을 때를 base condition으로 설정했고, 여러 복구 수열이 나왔을 때 중복 출력을 방지하기 위해 checkFlag를 두었다. 그리고 탐색 중인 경우라면, 수열 내에서 현재 탐색중인 index에 대해 한 자릿수로 볼 때와 두 자릿수의 일부로 볼 때로 나누어 recursive하게 구현했다.

#include <iostream>

#include <vector>

using namespace std;

string s;

bool checkFlag=false;

int n;

vector<bool> isUsed;

vector<int> ans;

void solve(int ind) {

    if(checkFlag == true) {

        return;

    }

    if(ind==s.size()) {

        for(auto num: ans) {

            cout << num << " ";

        }

        checkFlag = true;

        return;

    }

    int cur = s[ind]-'0';

    if(cur==0) {

        return;

    }

    if(!isUsed[cur]) {

        isUsed[cur] = true;

        ans.push_back(cur);

        solve(ind+1);

        ans.pop_back();

        isUsed[cur] = false;

    }

    if(ind<s.size()-1) {

        cur = cur*10+s[ind+1]-'0';

        if(cur <= n && !isUsed[cur]) {

            isUsed[cur] = true;

            ans.push_back(cur);

            solve(ind+2);

            ans.pop_back();

            isUsed[cur] = false;

        }

    }

}

int main() {

    cin >> s;

   

    if(s.size()>9) {

        n = (s.size()-9)/2 + 9;

    }else {

        n = s.size();

    }

    isUsed = vector<bool> (n, false);

    solve(0);

   

}

 

 

 

 

좋은수열(백준 2661):

 마찬가지로 백트래킹 문제이다. 수열의 첫 자리부터 1~3을 순서대로 넣어보며 진행한다. 수를 넣어보아서 현재까지의 수열이 좋은 수열이라면 다음 자리로 진행하고, 아니라면 더 큰 수를 넣거나 백트래킹으로 돌아가게 된다. 위 문제처럼 flag 처리로 중복 출력을 막았다.

 좋은 수열인지 판단하는 법은 현재의 인덱스-1부터 만들어둔 수열의 절반까지 내려가며 현재의 인덱스에 넣은 수와 같은 수를 찾는다. 그리고 찾아낸 인덱스와 그 왼쪽 수열, 현재 인덱스와 그 왼쪽 수열(찾아낸 인덱스+1까지)을 비교해가며 수열이 동일한지 확인해서 처리한다. 수열의 절반까지 탐색했음에도 동일한 수열이 없었다면, 좋은 수열이므로 다음 자리(인덱스)로 진행할 수 있다.

#include <iostream>

#include <vector>

using namespace std;

bool flag = false;

int n;

vector<int> v;

void solve(int ind) {

    if(flag) return;

    if(ind==n) {

        for(auto num: v) {

            cout << num;

        }

        flag = true;

        return;

    }

    for(int num=1; num<=3; num++) {

        bool globalFlag = false;

        v[ind] = num;

        for(int i=ind-1; i+1>=(ind+1)/2; i--) {

            if(v[i]==num) {

                bool localFlag = true;

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

                    if(v[ind-k]!=v[i-k]) {

                        localFlag = false;

                        break;

                    }

                }

                if(localFlag) {

                    globalFlag = true;

                    break;

                }

            }

        }

        if(!globalFlag) {

            solve(ind+1);

        }

    }    

}

int main() {

    cin >> n;

    v = vector<int>(n);

   

    solve(0);

}

 

 

 

2. 안드로이드 공부

 기존까지는 클린 아키텍처를 적용하더라도, 단일 모듈 앱으로 짜보고 있었는데 이번에는 presentation, domain, data 레이어를 다중 모듈로 처리해보고 있다. 간단한 쇼핑몰을 구현하게 될 것 같은데, feature와 core모듈로 분리할까 하다가 일단 단순한 구조로 구성해보기로 했다. 아무래도 단일 모듈로 할 때보다는 더 신경써야할 부분이 많고 피로도가 있다.

 gradle 상에서 implementation project()로 모듈 간의 종속성을 부여할 수 있어, 클린 아키텍처를 구성함에 있어서 좀 더 명확해지는 느낌이다. 

 MainActivity 쪽에서 이용할 Screen을 Scaffold와 Navigation 기반으로 대강 구성해두고, entity들과 room 이용을 위한 설계중인데 현재까지는 딱히 막힘 없는 것 같다.

 

 

 +DB에서 지원하는 데이터 형식 아닐 경우 @TypeConverter와 GsonBuilder를 이용해서 Entity와 String간 컨버팅을 해주어야 한다.