[TIL] 24.02.28

1. 알고리즘 문제 해결

 

 

동전 1(백준 2294):

 어제 풀었던 '동전 2' 문제와 유사한 DP 문제이지만, 세부사항이 약간 다르다. '동전 2'에서와는 달리 합이 k원이 되는 동전 조합의 경우의 수를 묻고 있고, 가치가 중복된 동전이 주어지지 않는다. 어제처럼 바깥의 루프가 dp 배열이고(해당 금액을 만들 수 있는 경우의 수가 저장됨) 안쪽의 루프가 동전 배열이면 동전의 중복처리가 상당히 까다로워진다.

 따라서 바깥 루프를 동전 배열로 설정하면, 쉽게 해결할 수 있다.

 

#include <iostream>

#include <vector>

using namespace std;

int main() {

    int n, k;

    cin >> n >> k;

   

    vector<int> coins(n);

    vector<int> dp(k+1, 0);

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

        cin >> coins[i];

    }

    dp[0] = 1;

    for(auto c: coins) {

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

            dp[i+c] += dp[i];

        }

    }

    cout << dp[k];

}

 

 

 

 

동전 바꿔주기(백준 2624):

 조금 까다로웠던 DP 문제이다. 동전의 종류별로 사용할 수 있는 수량이 정해져있는 조건 때문에, 앞서 풀었던 동전 문제들과 달리 DP배열의 차원을 확장해서 풀어야 했다. 

 

 그래서 처음의 풀이는 차원 하나를 확장해 동전의 종류를 구분할 수 있게 해서 푼 것이었다. 이렇게 하면 dp[탐색 중인 동전 인덱스-1][]를 참조하여 같은 종류 동전의 여러개 사용으로 인한 의도하지 않은 경우의 수 추가를 피할 수 있다. 그런데 결국에는 탐색 중인 동전 인덱스-1 만 사용할 것이라면 굳이 2차원 배열을 쓸 필요가 없었다.

 그런데 그렇다고 차원을 축소하게 되면 이제 같은 동전 여러개를 사용하는 과정에서의 의도하지 않은 경우의 수 추가가 발생한다. 그러니까 가치가 v인 동전에 대해 계산 중일 때, dp[1]부터 dp[i](1<i<T)까지 갱신했다고 생각해보자. 뒤이어 탐색 중인 dp[i+1] 값에 대해 이게 이전에 v짜리 동전을 추가해서 얻어진 값인지, 아닌지 알기 어렵게 된다.

 

 이 부분을 해결하느라 꽤 고생했는데, 결국 간단한 발상으로 풀 수 있었다. dp배열 갱신을 앞에서부터 할 것이 아니라, 뒤에서부터 하면 해결되는 문제였다. 이렇게 하면 이전의 갱신과정으로 인한, 값에 대한 모호성 문제를 없앨 수 있다. 갱신되는 값의 인덱스는 탐색 중인 인덱스보다 무조건 뒤에 있기 때문에, 탐색 과정이 뒤에서 앞으로 일어난다면 갱신된 인덱스를 탐색하는 일이 없는 것이다. 그래서 최종적인 코드는 다음과 같다.

 

#include <iostream>

#include <vector>

using namespace std;

int main() {

    int t, k;

    cin >> t >> k;

    vector<int> dp(t+1);

    dp[0] = 1;

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

        int p, n;

        cin >> p >> n;

        for(int j=t; j>=0; j--) {

            for(int cnt=1; cnt<=n; cnt++) {

                int val = j+p*cnt;

                if(val>t) break;

                dp[val] += dp[j];

            }

        }

    }

    cout << dp[t];

}

 

 

 

2. 안드로이드 공부

 

- 코루틴을 쓰면서 async()는 자주 사용하지 않았는데, 이번에 문서를 읽어보면서 확실히 알아두면 쓰임새가 생길 것 같았다. async 메소드는 suspend 메소드에서 리턴하는 값을 Deffered 타입으로 받을 수 있는데, 이 값을 await()을 이용해 지연을 기다려 사용할 수 있다. 글로 적으면 조금 애매모호 해보이는데, 문서에 있는 코드 스니펫을 보면 이해가 쉽다.

 

import kotlinx.coroutines.*

fun main() {
    runBlocking {
        println("Weather forecast")
        val forecast: Deferred<String> = async {
            getForecast()
        }
        val temperature: Deferred<String> = async {
            getTemperature()
        }
        println("${forecast.await()} ${temperature.await()}")
        println("Have a good day!")
    }
}

suspend fun getForecast(): String {
    delay(1000)
    return "Sunny"
}

suspend fun getTemperature(): String {
    delay(1000)
    return "30\u00b0C"
}

 

Output:

Weather forecast
Sunny 30°C
Have a good day!

 

 

- 중첩된 코루틴을 사용할 때, 자식 코루틴에서 Exception이 발생하면 상위 코루틴까지 cancel이 발생하고, 상위 레벨까지 Exception이 전파되기 때문에 앱이 죽게 될 수 있다. 이를 미연에 방지하기 위해서는 다른 Exception 핸들링과 마찬가지로 try ~ catch 문을 통해 적절하게 핸들링이 필요하다.

 이 때, 이 핸들링에 대한 책임을 어디서 질 것인가에 대한 내용 또한 문서에 있었다. await()과 async()로부터 예를들면, 생산자 격인 async 블럭 내에서 처리하는 것을 추천하고 있다. 사실 Exception의 핸들링 시점은 앱 아키텍처 상에서도 어디서 처리할 지 고민을 많이 하게 만드는 부분이었는데, 이렇게 함수 간의 관계 관점에서도 생각해보니 새로웠다. 

 일단 중첩된 코루틴 내에서는 될 수 있으면 생산하는 측 scope에서 핸들링을 하도록 구현해야겠다.

 

- user-driven event 등에 의해 코루틴을 임의로 cancel 할 수 있다. 당연한 이야기이지만, 같은 스코프 내의 다른 코루틴이나 부모 코루틴에 대해서는 cancel이 불가능하고, 자식 코루틴에 대해서만 cancel이 가능하다. 근데 같은 수준의 스코프 내에 있는 코루틴은 구현하기에 따라 cancel 할 수 있을 거 같기도 한데, 내부 로직 상으로 거부되는지는 따로 테스트 해봐야겠다.