[TIL] 24.04.15 알고리즘, 앱개발 숙련 주차 개인과제

winterry 2024. 4. 15. 20:49

1. 알고리즘 문제 해결

Ah-Choo!(백준 15822):

DP 문제이다. 점화식을 찾는 것이 제일 까다로웠다. 처음에 두 파형에 대해서 대응되는 시점을 지정하는 과정을 잘못 이해해서 시간을 더 쓰게 된 것 같다. 시점이 N개이면 대응 관계도 N개만 존재해야 하는 줄 알았는데, 문제를 다시 읽어보니 그런 제한은 명시돼있지 않았고, 오히려 각 시점은 하나 이상의 대응되는 시점을 가져야 한다는 조건이 핵심이었다.

그렇게 생각한다면, 점화식을 찾기 한결 편해진다. 파형 X의 시점 i와 파형 Y의 시점 j를 대응시킨다고 생각하면 고려할 경우는 세 가지이다.

- 파형 X의 시점 i-1과 파형 Y의 시점 j-1이 대응되었던 경우

- 파형 X의 시점 i-1과 파형 Y의 시점 j가 대응되었던 경우

- 파형 X의 시점 i와 파형 Y의 시점 j-1이 대응되었던 경우

그 이전 시점들에 대해서는 고려할 필요가 없는게, 이미 직전 시점에 대한 계산에 반영되어 있기 때문이다. 따라서 세 경우 중 가장 작은 케이스를 찾아 현재 대응시키는 두 시점의 파형 오차 값을 더해주면 될 것이다.

이제 이 방법을 토대로 파형 X의 모든 시점과 파형 Y의 모든 시점을 앞에서부터 대응시켜보며 N*N 크기의 dp 배열을 채워나가면, dp[N][N]에 두 파형의 최소 거리가 저장되게 된다.

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> xArr(n);
    vector<int> yArr(n);
    vector<vector<int> > dp(n+1, vector<int>(n+1, 987654321));

    for(int i=0; i<n; i++) {
        cin >> xArr[i];
    }

    for(int i=0; i<n; i++) {
        cin >> yArr[i];
    }

    dp[0][0] = 0;

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            int diff = xArr[i-1]-yArr[j-1];
            dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + diff*diff;
        }
    }

    cout << dp[n][n];
}

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

오늘로 추가 기능까지 모두 구현했다.

정작 이 기능들은 저번 주에 끝냈는데, 오늘 시간을 꽤 쓴 부분은 퍼미션 처리였다. 안드로이드에서 권장하는 퍼미션 처리 방식이 여러 번 바뀌어 왔었고, 공식 문서에 적힌 방법을 적용해 보려고 하니 또 낯선 느낌이 들었다.

큰 골자는 비슷한데, 일단 ActivityResultLauncher를 활용하는 부분이 내가 알던 것과는 조금 달랐다. 원래 무슨 퍼미션 요청한 것에 응답하는 액티비티 메소드를 오버라이드 해서 구현하지 않았었나 싶었다. 결국에는 레퍼런스와 아예 똑같은 구조로 디자인 하지는 않았고, 내가 생각했을 때 좀 더 깔끔해 보이는 방식으로 구현했다.

    private val notificationPermissionLauncher = registerForActivityResult(
        ActivityResultContracts.RequestPermission()
    ) { isGranted ->
        if(isGranted) {
            makeNotification()
        }else {
            if(ActivityCompat.shouldShowRequestPermissionRationale(this, Manifest.permission.POST_NOTIFICATIONS)) {
                makeDialog(getString(R.string.request_permission_title),
                    getString(R.string.request_permission_msg)) {
                    requestNotificationPermission()
                }
            }else {
                Snackbar.make(
                    binding.root,
                    getString(R.string.noti_failure_no_permission),
                    Snackbar.LENGTH_SHORT
                ).show()
            }
        }
    }

필요한 퍼미션이 허용되어 있는지 확인하고, 아니라면 유저에 의해 명시적 거부와 다시 표시 하지 않음 중 어떤 것을 선택했는 지 확인한다. 그냥 거부한 상태면 Dialog를 띄워 권한을 요구한다. 아니고 다시 표시 하지 않는 상태(유저에 의해서든, 연속된 거부로 안드로이드 차원에서든)라면 SnackBar를 이용해 권한이 없어서 실행할 수 없다고 알리기로 했다.

의도대로 동작하는 것을 확인했다.

그 밖에도 다양한 기능들이 요구대로 동작하는 것을 확인했고, 아마 README 작성 이후에 바로 제출하면 될 것 같다.

내일부터는 챌린지반 과제를 해야하는데 비교적 간단한 아키텍처로 Retrofit을 통해 데이터를 받아와 UI로 뿌려주는 작업이다. 마침 이용하게 될 API도 카카오API라 어째 기존에 진행하던 사이드 프로젝트와 상당 부분 닮아있다. 물론 그 프로젝트는 두 API를 따로 받아와 한 화면에 정렬해서 뿌려줘야 하고, UI를 Compose를 통해 그리고 있지만 비즈니스 로직의 큰 흐름은 비슷하니 금방 하지 않을까 싶다.