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

1. 알고리즘 문제 해결

 

가운데를 말해요(백준 1655):

 발상해내는데 꽤 걸린 문제다. 매번 정렬을 하면서 풀자니 O(n^2 log n)으로 시간 초과가 날 것이다. 일반적인 정렬 알고리즘이 아닌 Radix Sort나 Counting Sort를 써도 원소를 입력받을 때마다 반복한다면 O(n^2)을 넘기 때문에, 이 또한 불가능하다. 전체 동작 시간이 O(n log n) 선에서 끝나야 했다. 그래서 매번 리스트에 대해 이진 탐색으로 들어갈 자리를 찾아 삽입하고, 중앙값을 출력하게 해 볼까도 생각했다. 하지만 배열 기반 리스트라면 삽입 과정에서 O(n)이 걸리고, 연결 리스트라면 이진 탐색이 힘들어 보였다.

 어쨌든 입력은 n번을 받아야하고, 결국 입력을 받으면서 매번 O(log n)의 연산을 통해 중앙값을 찾아내야 한다는 소리였다. 구조상 AVL 트리도 문득 떠올랐지만, AVL 트리도 왼쪽 서브트리와 오른쪽 서브트리 내의 자식 수가 같도록 보장해 줄 순 없기 때문에 답은 아닌 것 같았다. 남은 건 우선순위 큐뿐이었다.

 

 우선순위 큐 두 개를 이용하면 매번 O(log n)만에 중앙값을 찾는 것이 가능하다. 대신 하나는 Max Heap 기반으로, 하나는 Min Heap 기반으로 생성해야 한다.

 

두 우선순위 큐의 top은 Mid 방향의 말단

 

 우선순위 큐 두 개를 저런 식으로 들고 있게 되면, 사실상 나는 정렬된 배열을 중앙값 기준으로 잘라 두 덩이로 들고 있는 꼴이 된다. 입력값을 매번 각각의 우선순위 큐에 번갈아가면서 집어넣고(대신 짝수 개일 땐, 중앙값 두 개 중 더 작은 값을 이용할 것이기 때문에 Max 쪽에 먼저 넣는다), 두 top 값을 비교해 MaxHeap의 top보다 MinHeap의 top이 작다면 방금 들어온 값에 의해 중앙값이 제 위치에 있지 않은 상태이다. 따라서 그때는 서로의 top을 교체해 주면, 방금 들어온 값이 제 자리를 찾아가게 된다.

 입력을 모두 받아 처리하고 나면 MaxHeap 쪽의 top을 확인해 중앙값을 얻을 수 있다. 구현하는 본 코드에서는 첫 원소는 반복문 밖에서 따로 받아서 넣고 있는데, 첫 원소만 들어왔을 때 비어있는 MinHeap(코드에선 MinPq)의 top을 참조하면서 발생하는 예외를 막기 위해서이다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

    int n, num;
    cin >> n;
    priority_queue<int> maxPq;
    priority_queue<int, vector<int>, greater<int> > minPq;

    cin >> num;
    maxPq.push(num);
    cout << maxPq.top() << "\n";

    for(int i=1; i<n; i++) {
        cin >> num;
        if(i%2==0) {
            maxPq.push(num);
        }else {
            minPq.push(num);
        }

        if(minPq.top()<maxPq.top()) {
            int temp = maxPq.top();
            maxPq.pop();
            maxPq.push(minPq.top());
            minPq.pop();
            minPq.push(temp);
        }

        cout << maxPq.top() << "\n";
    }

}

 

 

2. 사이드 프로젝트

 

 조금씩 진행하던 사이드 프로젝트가 마음에 안 들어서 싹 갈아엎기로 했다. 아키텍처나 로직 상 복잡해질 수 있는 부분이 있어서 튜터님들의 조언을 구하며 만들면 더 좋을 것 같아서도 있었다. 여쭤보기 용이하게 하려고 Figma로 와이어 프레임도 작성해 보고, 예전에 데이터베이스 전공수업 때 다뤘던 UML 다이어그램도 떠올려가며 구조도 러프하게 그려뒀다.

 재밌는 건 원래 질문할 게 좀 많았는데, 직접 이렇게 청사진들을 눈에 보이게 그리고 나니 질문의 대부분에 스스로 답을 할 수 있게 됐다. 괜히 시간을 들여서 이런 것들을 작성하는 것이 아닌 것 같다. 그럼에도 새로 코드를 작성하다 문제를 만났다.

 

 ❗ BuildConfig를 찾을 수 없는 문제

이건 전에도 한 번 겪은 적이 있는데, AGP 버전 8 이후로 BuildConfig의 생성은 기본 값이 아니게 됐기 때문이다.

 

Android Gradle Plugin 8.0.0 (April 2023)  |  Android Developers

Android Gradle 플러그인 8.0.0 (2023년 4월)  |  Android 개발자  |  Android Developers

 

 

 그래서 local.properties를 이용해 API 키를 은닉하려고 했는데, 코틀린 코드 내에서 BuildConfig가 찾아지지 않았다. 이 문제 자체는 앱 수준 build.gradle에서 buildFeatures를 수정해주면 해결이 가능한데, 이상하게도 나는 바로 해결이 되지 않았다.

    buildFeatures {
        buildConfig = true
    }

 

 저렇게 바꿨는데도, BuildConfig가 코드 내에서 자동으로 import 되지도 않고 직접 패키지명.BuildConfig로 import 해도 묵묵부답이었다. 물론 코드 자동완성도 동작하지 않았다. gradle 파일에 어디 오타라도 있나 싶어서 열심히 찾아봤는데도 문제는 찾을 수 없었고, 해결 방법은 허무했다.

 Invalidate Caches 사용 후에, 새로 한 번 빌드해주니까 바로 찾아졌다.. Clean Project만 해줬을 땐 바뀌지 않았는데, 아마 Rebuild Project도 해줬으면 고쳐졌을 것 같다.