[TIL] 24.04.11 알고리즘, 개인 과제 Dialog 에러

1. 알고리즘 문제 해결

 

 연속합 2(백준 13398):

 브루트 포스로 구한다면 O(n^2)의 시간복잡도를 가지기 때문에, 시간 제한 내로 풀 수 없다. DP를 이용해야 하는 문제.
 수열에서 수를 하나 제거할 수 있다는 조건 때문에, 1차원 배열 하나로는 풀 수 없고 1차원 배열 두 개를 이용해야 한다. 하나는 일반적인 경우의 연속합을 계산해 저장하고, 하나는 수를 하나 제거했을 때의 연속합을 저장한다.

 먼저 일반적인 경우의 연속합은 max(이전까지의 연속합+탐색중인 수, 탐색 중인 수)로 구할 수 있다. 이전까지의 연속합이 음수라면 현재 탐색 중인 수부터 새로 연속합을 구하는 것이 optimal한 값이기 때문이다.

 두번째로 수열에서 수를 하나 제거한 경우의 연속합은, max(이전까지의 연속합, 이전까지의 제거 연속합+탐색 중인 수)로 구할 수 있다. 현재 탐색 중인 수를 제외하는 경우와 그렇지 않은 경우로 나누어서 더 큰 값을 취하기 위함이다.

 

 DP 배열의 끝에 최적의 값이 들어있지는 않기 때문에(음수가 이어져 나올 경우, 앞서 나온 연속합 값이 더 큰 값이 됨), DP 배열을 한번 선형 탐색해서 최댓값을 구해주어야 한다. 나는 DP 배열들을 구하면서 그때 함께 구해주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    int n;
    cin >> n;

    vector<int> arr(n, 0);
    vector<int> accArr(n, 0);
    vector<int> exceptAccArr(n, 0);
    
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    int maxSum = arr[0];
    accArr[0] = arr[0];
    exceptAccArr[0] = 0;

    for(int i=1; i<n; i++) {
        accArr[i] = max(arr[i], accArr[i-1]+arr[i]);
        exceptAccArr[i] = max(accArr[i-1], exceptAccArr[i-1]+arr[i]);
        maxSum = max(maxSum, max(accArr[i], exceptAccArr[i]));
    }

    cout << maxSum;
}

 

 

2. 앱개발 숙련 주차 개인 과제

 

Dialog 관련 에러들

 꽤 무난하게 구현 중이었는데 종료를 위한 Dialog를 만들던 도중 에러가 생겼다.

 

java.lang.IllegalStateException: You need to use a Theme.AppCompat theme (or descendant) with this activity.

 

 backPressed()가 호출되면 이런 에러를 뱉으면서 팅겼다. 커스텀 뷰를 따로 적용하지도 않고, 기본 테마 그대로 쓰고 있는데 왜 이런 오류가 나는지 알 수가 없었다. 그래서 처음에는 다른 AlertDialog를 import 해야 하나 싶었다.

 

appcompat의 AlertDialog를 써서 문제가 생긴 줄 알았다

 

 처음엔 내 기본 테마가 Material3를 상속받고 있어서 그런가 싶어서, MaterialAlertDialogBuilder()를 이용해 보기로 했다.

 

 하지만 똑같은 에러를 뱉으며 죽어버렸다. 또 같은 타이밍에 앱이 죽는 걸 보면, 단순히 테마 문제는 아닐 것 같았다. 애초에 AppComaptActivity를 쓰고 있는 데다 Material 테마로 작성된 그간의 앱들은 이런 형태의 에러를 띄운 적이 없었다.

 그래도 혹시나싶어 기본 android의 AlertDialog를 import 해서 사용해 보기로 했다.

 

android.view.WindowManager$BadTokenException: Unable to add window -- token null is not valid; is your activity running?

 

 이번엔 다른 오류를 뱉으면서 죽는 앱.. 액티비티가 살아있는데, 왜 뷰를 붙이기 전에 죽는건지 의아했다. 그래서 어디선가 잘못된 Context가 전달되고 있구나 싶었다.

 

 

 코드를 한참 쳐다보다가 발견한건데, 왜 baseContext가 들어갔나 싶었다. baseContext가 들어갈 이유가 전혀 없었는데, 아마 레퍼런스의 파라미터들만 보면서 대강 집어넣다가 실수한 것 같았다.

 

 

 baseContext가 아닌 this를 통해 현재 액티비티 context를 전달하니, 그제서야 정상적으로 동작했다. 혹시나 싶어 확인해 봤는데, 아까 넣어봤던 다른 라이브러리들도 정상 작동했다. 다음엔 이런 실수 안 하게 좀 더 의식해야겠다.