[TIL] 24.02.05

1. 알고리즘 문제 해결

 

숨바꼭질 2(백준 12851):

 저번에 풀었던 숨바꼭질 문제와 유사하지만 조금 다르다. 이번에는 가장 빠른 시간으로 동생을 찾는 방법의 수도 출력해야하기 때문에, 저번처럼 BFS를 하면서 단순하게 방문여부로 pruning 할 수 없다. 단순한 방문여부 대신 가장 처음 방문했을 때가 몇 초인지를 저장하는 방식으로 접근해볼 수 있다. 이렇게 되면 이후 탐색 도중 같은 점을 방문하게 되었을 때, 현재의 초와 방문기록에 저장된 초를 비교해 현재의 초가 더 크다면 pruning 할 수 있다. 그리고 반복문의 초반부에 최단 시간으로 찾는 방법이 찾아진 상태인지 확인하고, 그 여부에 따라 가망이 없는 탐색을 중단할 수도, 또다른 최단 시간 도달 방법이라면 카운트에 더해줄 수 있을 것이다. 실제로 코드로 구현하면 다음과 같다.

#include <iostream>

#include <queue>

#include <vector>

#define MAX_SEC 987654321

using namespace std;

vector<int> isVisited(100001, -1);

bool isValid(int x) {

    return x>=0 && x<=100000;

}

int main() {

    int n, k;

    cin >> n >> k;

    queue<pair<int, int> > q;

    q.push({n, 0});

    int minSec = MAX_SEC;

    int minCount = 1;

    while(!q.empty()) {

        pair<int, int> cur = q.front();

        q.pop();

        if(minSec!=MAX_SEC) {

            if(cur.second>minSec) {

                continue;

            }else if(cur.first==k) {

                minCount++;

                continue;

            }

        }

        if(isVisited[cur.first]==-1) {

            isVisited[cur.first] = cur.second;

        }else if(isVisited[cur.first]<cur.second) {

            continue;

        }

        if(cur.first==k) {

            minSec = cur.second;

            continue;

        }

        if(isValid(cur.first+1)) q.push({cur.first+1, cur.second+1});

        if(isValid(cur.first-1)) q.push({cur.first-1, cur.second+1});

        if(isValid(cur.first*2)) q.push({cur.first*2, cur.second+1});

    }

    cout << minSec << "\n" << minCount;

}

 

 

2. 안드로이드 공부
  강의 위주로 공부할 때는, 그날 그날 새로 알게 되는게 많아서 글로 남길 것도 많은데 요즘은 또 실제 구현 위주로 연습해보고 있어서 막상 글로 남길게 적은 것 같다. 고민하는 과정과 시도를 남기는 것도 좋을 것 같지만, 체계적으로 처음부터 하나하나 남기는게 아닌지라 단편적인 부분만 쓰려니 설명하기 난감한 부분이 있다. 그래서 요즘은 TIL을 쓰더라도 짧게 끝내게 된다. 오히려 강의를 들을 때보다 더 많은 시간을 투자하고 있는데도 그렇다. 

 

 요즘은 뮤직 플레이어 앱을 구현 해보고 있는데, 생각보다 Seek Bar 처리하는거나 실시간 가사 처리하는 부분에서 고민할 게 많다. 음악의 진행상태를 어느정도 간격으로, 어떤 구조를 이용해 업데이트 할 지, 각각 예상되는 퍼포먼스를 그려보면서 고민 중이다. 그리고 Foreground 서비스와 실제 View가 동기화된 플레이어를 제공하고 싶은데, 이 부분도 생각할 게 많다. 원래 Foreground 서비스는 구현할 생각이 없었어서, 무난하게 뷰모델 내에서 MediaPlayer를 처리할 생각이었는데 갑자기 구현하는 쪽으로 계획이 바뀌어서 구조도 조금 바꿔야 할 것 같다. Application쪽을 이용할 지, 아니면 뷰모델 내에 유지할지, 서비스 쪽으로 옮길지, 그리고 옮기고 나서 상호 간의 통신은 어떻게 할 지도 생각해봐야 한다.