[TIL] 24.01.17

1. 알고리즘 문제 해결

 

스택 수열(백준 1874):

 스택 자료구조를 이용한 단순 구현 문제.

 

 

외계인의 기타 연주(백준 2841):

 처음에 기타 줄을 누르는 손가락이 5개라고 생각해서 조금 복잡한 구현 방식을 떠올렸는데, 다시보니 손가락이 수십억개인 외계인이 기타를 치는 문제였다.  음의 수가 500,000개가 최대고 줄의 수도 6개 밖에 되지 않아서 그냥 스택 6개짜리 벡터 생성해서 풀었다. C++ 기준으로는 빈 스택의 top을 참조하지 않도록 조금 신경써줘야 한다.

 

 

오큰수(백준 17298):

 단순하게 브루트 포스로 접근하면 O(n^2)가 되어 시간초과가 날 것이다. 처음엔 i+1~n번째에 해당하는 부분 수열에 대해 인덱스를 포함한 pair로 만들고, 값과 인덱스 둘 모두 이용하는 우선순위 큐를 만들까 했다. 근데 그렇게 하면 힙을 구축하는 시간복잡도가 O(n log n)인데, 전체 수열을 순회하며 부분 수열이 계속 달라지고 비교연산자에 들어가야하는 기준 값도 달라지므로 매번 힙을 새로 구축해야 한다. 그렇게 되면 O(n^2 log n)으로 브루트 포스만도 못하게 된다.

 

  그래서 스택을 이용해 처리하기로 했다. 먼저 인접한 두 원소에 대해 생각해 보았을 때, 뒤에 나온 원소가 앞에 나온 원소보다 크다면, 앞에 있는 원소의 오큰수는 뒤에 나온 바로 그 원소가 될 것이다.

 그렇다면 처리해주어야 하는 케이스는 뒤에 나온 원소가 작거나 같은 경우인데, 이 부분에서 스택을 이용할 수 있다. 아직 오큰수가 발견되지 않은 원소는 스택에 쌓이도록 하는 것이다. 이후 남은 수열을 탐색하며, 매번 스택의 top에서부터 탐색 중인 원소보다 작은 값들을 모두 빼내고 그들의 오큰수로 탐색 중인 원소 값을 주면 된다.

 이렇게 되면 스택은 top으로 갈수록 작거나 같은 원소들만 존재하는 형태로 쌓인다. 따라서 최악의 경우는 수열이 내림차순으로 정렬된 경우로, 이 때도 2n번 가량의 비교연산만 필요하므로 O(n)이다.

 

 이건 코드로 보는게 더 간단할 것 같다..

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int n, num;

    cin >> n;

    vector<int> ans(n, -1);

    stack<pair<int, int> > st; //first: ind, second: value

   

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

        cin >> num;

        if(st.empty()) {

            st.push(make_pair(i, num));

        }else {

            while(!st.empty() && st.top().second<num) {

                ans[st.top().first] = num;

                st.pop();

            }

            st.push(make_pair(i, num));

        }

    }

    for(auto nge: ans) {

        cout << nge << " ";

    }

}

 

 내일부턴 아마도 재귀를 이용한 순열, 조합 문제들을 풀 것 같다.

 

 

2. 안드로이드 공부

- 어제에 이어서 강의를 들으며 앱을 만들고 있다. 생각보다 Material3와 Material2의 차이가 커서, 강의 내용을 그대로 따라할 수 있는 부분은 많지 않다. 강의에서 사용하는 코드를 쓰다가 빨간줄이 뜨면, 강의를 멈추고 해당 클래스나 함수의 원본 파일을 뜯어서 확인하고의 반복이다.

 레거시 버전의 파라미터에 대해 오버로딩 되어 있으면 좋겠는데, androidx.compose.material3 패키지에서는 유독 그런게 안 보인다. 그래서 달라진 것이 있으면 하나하나 따라가보면서 확인하고 있다.

 

강의 내용

실제 작성중인 코드

 

  - Composable 함수 내에서 AndroidView()를 이용하면 기존의 안드로이드 뷰 요소들도 이용이 가능하다. factory 파라미터를 이용해서 생성한다. 반대로 xml에서 Compose를 이용할 때는 ComposeView를 이용했던 걸로 기억하는데 다음에 상호운용하는 것도 연습해보면 좋을 것 같다.

 

 - 강의에서는 각종 컴포넌트들을 재사용할 수 있게 최대한 작은 부분으로 나누어 베이스가 되는 Composable들을 작성해두고 있다. 그리고 사용자 입장(개발하는 측)에서 용이하도록 Wrapper들도 정의한다.

 또 그것들을 재료로 해서 만든 복합적인 컴포넌트들을 종류별로 정의하고(종류별 sealed class 내에 data class나 일반 class들로 정의해서 묶고 있는 sealed class를 상속받게 함), 이 또한 활용하기 쉽게 object와 그 확장함수를 이용해 한 번 더 가공해주고 있다.

 처음에는 굳이 이렇게까지 해야하나 싶었지만, 막상 써보니 생산성이 압도적이었다. 처음 한 번 고생해두면, 이후에 작업하기 편하니까 이런 방식에 익숙해져야 할 것 같다. 그런데 막상 혼자 이런식으로 가공하려면 경험치가 부족해서 아직 어려워 보이기도 하고..ㅋㅋㅋ

 

 얼추 컴포넌트들 끝내고 Preview 만들어서 확인해보니까, 대부분 저런식으로 멀끔하게 나왔다. 내일부터는 기능 로직 짜는 부분들 공부하면 될 것 같은데, 아마 로직은 xml 기반으로 짤 때랑 크게 달라지는 건 없지 않을까 싶다.