[TIL] 24.05.01 알고리즘, 몇 가지 질의응답

1. 알고리즘 문제 해결

 

 

카드 팩 구매하기(백준 15823):

 푸느라 꽤 애를 먹었다. 각 카드 팩을 구성하는 카드 수가 1~N 장이 될 수 있고, 해당 장 수의 카드팩으로 구성할 수 있는지 확인하는 데에도 O(N)만큼 걸리기 때문에 모든 경우를 탐색하면 시간복잡도가 O(N^2)에 달한다. 이려면 N이 최대 100,000까지 입력될 수 있으므로, 제한시간을 아득하게 넘을 것이다.

 

 일단 주어진 카드 배열에 대해 x장짜리 카드팩 m개가 성립가능한지 확인하는 것은, 투 포인터나 슬라이딩 윈도우 방식으로 구해내면 O(n)에 해당하고 이보다 더 줄일 수는 없을 것 같았다.

 그렇다면 저 x의 범위를 줄여야 하는데, 처음에는 DP로 접근했지만 마땅한 점화식이 떠오르지 않았다. 하지만 계속 DP로 접근하려고 시도하다가 만약 x장짜리 카드팩 m개를 만들 수 있다면 x-1장짜리 카드팩부터 1장짜리 카드팩 m개는 당연히 만들 수 있다는 생각이 들었다. 이를 토대로 생각을 바꾸면, 1~N 사이에 위치한 x의 가능 최댓값을 탐색하는 문제로 치환할 수 있게 된다. 우리는 연속된 값 사이에서 조건에 맞는 값을 찾아내는 합리적인 방법을 알고 있다.

  

 나는 이진 탐색을 사용하기로 했고, 조건에 일치하는지 검사하는 로직이 O(n)만큼 걸리고 이진 탐색을 통해 최적값을 찾아내는데 O(log n)만큼 걸릴 것이므로 총 시간복잡도는 O(n log n)으로 통과할 거라고 생각했다.

 이진 탐색의 경계 설정을 조심해야 했는데, 일단 mid 값에 해당하는 장 수의 카드팩 m개가 만들어진다면 mid 값을 포함하여 더 큰 값들을 탐색해보아야 한다. 만들어질 수 없다면 당연히 start부터 mid-1까지 범위에 이진 탐색을 다시 시도해보아야 한다. 탐색이 종료되는 시점은 mid 값이 start 값과 같을 때일 것이다(mid = (start+end+1)/2로 한다고 했을 때이고, 이는 유효한 값이 버림처리에 의해 탐색되지 않는 경우를 없애기 위함이다).

 

 구현을 끝내고 보니, 로직은 심플하게 잘 작성됐고 Large케이스(1<=M<=N)까지 잘 통과하는 것을 확인할 수 있었다. 구현 자체보다는 로직을 발상하는 것이 힘들었던 문제였다. 비결정 문제를 결정 문제로 치환하고, 해를 구하는 과정을 최적화 하는 것이 핵심.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> cards;
int n, m;

bool checkAvail(int num) {
    vector<int> lastInd(500001, -1);
    int count = 0;
    int start=0, end=0;

    while(end<n) {
        if(lastInd[cards[end]]>=start) {
            start = lastInd[cards[end]] + 1;
        }
        lastInd[cards[end]] = end;
        
        if(end-start+1==num) {
            count++;
            start=end+1;
        }

        if(count==m) {
            return true;
        }
        end++;
    }

    return false;
}

int binarySearch(int start, int end) {
    int mid = (start+end+1)/2;

    if(start==mid) return start;
    if(checkAvail(mid)) {
        return binarySearch(mid, end);
    }else {
        return binarySearch(start, mid-1);
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    cards = vector<int>(n);
    for(int i=0; i<n; i++) {
        cin >> cards[i];
    }

    cout << binarySearch(1, n);
}

 

 

 

2. 튜터님들과 고민한 것

 지급된 강의들을 보다가 개발 프로세스에 대해 다루는 내용이 있었는데, 문득 여러가지 의문이 들었다. 그래서 튜터님 두 분에게 질문드렸고, 많은 조언을 들을 수 있었다.

 

- 깃허브 Public Repository에 프로젝트를 업로드할 때 키 은닉을 내가 하던 방식대로(local.properties 이용) 해도 되는가?

 문제 없는 방식이고, 오히려 현업에서는 BuildConfig나 코드 내에 바로 넣기도 한다.(기본적으로 Private Repository를 활용하고, 깃허브가 아니라 다른 사설 Repository를 이용하는 경우도 많기 때문에)

 

- 이용한다면, AGP 9.0에 BuildConfig가 아예 비활성화 되는 것으로 알고 있는데 어떻게 대응해야 하는가?

 지금 사용하는 용법처럼, 9.0 이상에도 유효한 활성화 시키는 방식을 이용하면 되고, 혹여 문제가 생긴다면 암/복호화 과정을 수동으로 처리하거나 keyStore를 이용하는 방법도 있음.

 

- 컴파일 될 때, 그렇게 들어가는 키 값들은 암호화 되는가? 코드 난독화를 진행하면 암호화 되는가? 안된다면 디컴파일 했을 때 키 값이 그대로 노출되는 것이고 문제는 없는가?

 raw한 String 리소스 자체가 암호화 되진 않겠지만, 이를 디컴파일해서 역으로 찾아내는 것은 매우 힘들고, 또 코드 내에서 동적으로 여러 부분을 통해 키를 만들어 내는 방식을 채용한 뒤 난독화를 진행하는 방법도 있다.

 

- aab로 패키징할 때와 apk로 패키징할 때, 보안 측면에서 다르게 대응해야 하는지?

 aab도 서명이 필요하고, 안전하다. 패키징 되는 내부 등은 직접 한 번 확인해 볼 것!

 

- 유닛 테스트 공부를 위한 레퍼런스

 각 모듈에 테스트가 필요한 범위 등을 잘 생각해보고, 공식 문서에서 도움을 얻기 힘들다면 블로그 등도 많이 참조해 볼 것. JUnit은 자바시절부터 쓰이던 레거시한 방식이니까, Kotest도 찾아볼 것.

 

- 내가 생각하는 일반적인 클린 아키텍처 앱 구조에서 걷어내야 할 것

 나는 Domain 레이어에서 다루는 엔티티들을 Wrapper 클래스를 이용해서(Result, Result.Sucess, Result.Error 등) 다루는 것을 선호했는데, 이는 불필요할 수 있다고 하셨다.

 Domain에서 정의된 상태나 결과 값을 이용해서, Presentation 레이어에서 좀 더 일관된 처리를 할 수 있지 않을까 하는 측면에서였는데, 튜터님께서는 코틀린을 이용해 잘 처리할 수 있다면 불필요하다고 생각하셨다. Exception 자체를 throw하고 이를 Presentation에서 catch하면 되지 않냐고 하셔서, 많은 생각을 해보게 된 것 같다. 나는 Presentation에서는 발생한 Exception 클래스 자체는 몰라야 한다고 생각했는데, 그런 것도 아닌 것 같다.

 Data 레이어에서 각종 예외나 에러 처리를 비즈니스 로직에 정해진 클래스로 해서, Presentation에서 해당 클래스의 확장함수 등을 이용해 바로 처리하는 것이 이상적이지 않을까 하는 게 내 생각이었는데, 튜터님의 조언에 따라 그런 것 없이 해봐야겠다.

 

 그리고 불필요한 부분을 자꾸 덜어내는 연습을 해봐야겠다. 구조를 위한 구조는 존재해서는 안되니까 말이다.