[TIL] 24.02.27

1. 알고리즘 문제 해결

 

 

포도주 시식(백준 2156):

 간단한 유형의 DP 문제이다. 대신 두번째 규칙 때문에 DP 테이블을 나눠서 생각할 필요가 있다. DP 테이블을 3 x n 형태의 2차원 배열로 선언하고, 각 행이 선택 여부를 구분하여 나타낼 수 있도록 했다. 

 

 - dp[0][k]에는 k번째 포도주를 선택하지 않는 경우를 저장한다.

 - dp[1][k]에는 k-1번째 포도주를 선택하지 않고, k번째 포도주를 선택하는 경우를 저장한다.

 - dp[2][k]에는 k-1번째 포도주와 k번째 포도주를 모두 선택하는 경우를 저장한다.

 

 이 때, dp[2][k]를 계산할 때는 dp[1][k-1] 값만을 이용해야하는 것은 명확하며, 모든 DP 테이블 값을 계산한 후에 n번째 열 중 가장 큰 값을 출력해주면 된다.

 

 

 

동전2(백준 2294):

 이 문제도 간단한 유형의 DP 문제이다. 크기가 k+1인 dp배열을(동전 수가 담기게 됨) 생성하고 충분히 큰 값으로 초기화한다. 문제조건 상 101 이상이면 무방하다. 이후, 처음 가지고 있던 동전들을 탐색하며, 해당 동전의 가치를 인덱스로하는 dp배열 값에 1을 대입한다.

 그리고 1부터 k번째 원소까지 dp배열을 탐색하며 탐색 중인 원소 값이 초기화 값이 아닐 때(가진 동전으로 생성될 수 있음을 의미), 가진 동전 배열을 순회하며 dp[탐색 중인 인덱스+순회 중인 동전 가치]의 값에 min(해당 값, dp[탐색 중인 인덱스]+1)를 대입해준다.

 위 과정을 반복하며 모든 탐색이 끝난 후, dp[k] 값이 초기화 값이라면 -1을 출력하고 아니라면 dp[k] 값을 출력해 마무리한다. 문제 조건 상, 동전을 입력받을 때 10,000보다 큰 값은 받지 않고, 입력 받는 자료구조도 Set을 채택해 중복을 제거해주면 조금 더 성능의 우위를 가져갈 수 있을 거 같다.

#include <iostream>

#include <vector>

#include <algorithm>

#define MAX_COIN 987654321

using namespace std;

int main() {

    int n, k;

    cin >> n >> k;

   

    vector<int> coins(n);

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

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

        cin >> coins[i];

    }

    for(auto c: coins) {

        if(c<=k) dp[c] = 1;

    }

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

        if(dp[i]!=MAX_COIN) {

            for(auto c: coins) {

                if(i+c<=k) dp[i+c] = min(dp[i+c], dp[i]+1);

            }

        }

    }

    cout << (dp[k]==MAX_COIN ? -1 : dp[k]);

}

 

 

 

2. 안드로이드 공부

 

- Compose에서 State Hoisting을 할 때, 콜백 람다를 이용해 퍼포먼스를 챙기고 합리적인 구조로 만들 수 있다. 그러니까 하향식으로 State를 전달하고, 상향식으로 이벤트를 전달 받는 것이다.

 이렇게 Composable을 설계하면 Stateful한 자식 Composable을 Stateless하게 만들 수 있고, Stateless한 Composable은 UI 재사용성이나 테스트 용이성 측면에서 유리하다. 뿐만 아니라, Recomposition의 발생 빈도도 줄일 수 있어 성능 상의 이점도 생긴다.

 알면서도 잘 떠오르지 않는 부분이었는데, 이제는 조금 더 의식하고 코드를 짜보아야겠다.

 

- Lazy list들은 RecyclerView처럼 자식 뷰들을 재활용하지 않는다. 애초에 기존의 xml과는 다른 방식으로 UI를 그리기 때문에, 당연한 소리일 수도 있지만 차이가 있는 부분이다. 스크롤을 통해 리스트의 끝에 도달했을 때 emit 할 수 있는 Composable이 남아있다면, 이를 emit 하는 단순한 방식이다.

 Composable을 emit 하는 것이 안드로이드 View를 인스턴스를 생성하는 것에 비해 훨씬 비용이 적게 들기 때문에 가능한 방식이고, 이는 RecyclerView에 비해 훨씬 적은 양의 보일러 플레이트 코드를 가능하게 한다.

 그래도 이전에 봤던 문서에서는,  RecyclerView가 성능상 LazyColumn보다 미세하게 앞선다고는 했던거 같다.

 

- remember를 이용해 할당해둔 State 값은 composable이 Composition에 유지되는 동안에만 유지된다. 그러니까 xml에서도 나타나는 문제처럼, 화면 회전 등에 의해 Activity가 재생성된다든지 하면, remember API를 이용했더라도 State 값은 소실된다. 물론, ViewModel을 이용해 유지하는 방법이 있겠지만, 오로지 UI 자체만을 위한 State라면 ViewModel이 들고 있는 것이 썩 괜찮은 구조는 아닌 것 같다.

 Compose는 이를 위한 remeberSaveable을 제공하고 있다. 확실히 동적인 UI를 그릴 때, 불필요한 코드 없이 화면 회전, 다크모드 등에 대응하기 좋을 것 같다.