TIL 30일차 (피로도 - Kotlin | 액티비티 생명주기 개념 정리)

코드카타

 

피로도

 

문제

 

해당 문제는 주어진 피로도 내에서 탐험할 수 있는 최대 던전수를 반환하는 문제이다.

모든 가능한 던전 탐험 경로를 고려해야 하기에 완전탐색으로 풀어야 한다.

 

 

제한사항에서 정보 얻기

제한사항에서 최대로 주어지는 던전의 개수는 8개라 명시되어있기에, 

 최악의 경우에도 시간복잡도가 O(8!)밖에 나오지 않는다.

 

그렇기에 완전 탐색으로 풀어도 시간초과가 나지 않는다.

 

 

입출력 예시

 

입장 피로도 순으로 정렬해서 푼다 => 3번 던전을 못가게 된다.

소모 피로도 순으로 정렬해서 푼다 => 1번 던전을 못가게 된다.

 

배열의 정렬로는 풀 수 없기에 모든 던전 탐험 경로를 다 탐색해야한다.

 

 

풀이

class Solution {
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        var visit = BooleanArray(dungeons.size) // 던전 방문 표시
        var cnt = 0 // 현재까지 탐험한 던전 개수
        var res = 0 // 최대로 탐험할 수 있는 던전 개수

        // 깊이 우선 탐색
        fun dfs(k: Int, n: Int, dungeons: Array<IntArray>) {
            // 현재 탐험하는 던전 방문 표시
            visit[n] = true
            cnt++

            // 현재까지 발견한 최대 탐험 던전의 개수를 갱신
            if (res < cnt) res = cnt

            // 현재 던전에서 이동가능한 다른 던전 탐색
            for (i in dungeons.indices) {
                val remainK = k - dungeons[n][1] // 현재 던전을 탐험하고 남은 피로도

                // 현재 피로도가 방문한 적 없는 남은 던전의
                // 최소 피로도 이상이면 바로 그 다음 던전으로 이동한다.
                if (!visit[i] && (dungeons[i][0] <= remainK)) dfs(remainK, i, dungeons)
            }

            // 피로도가 부족해 던전을 더 이상 탐색할 수 없다면
            // 현재 던전을 방문하지 않은 상태로 되돌린다. (백트래킹)
            visit[n] = false
            cnt--
        }

        // 모든 던전을 시작점으로 하여 완전탐색 실행
        for (i in dungeons.indices) {
            dfs(k, i, dungeons)
        }
        return res
    }
}

DFS(깊이 우선 탐색)을 통해 완전 탐색을 진행한다.

 

현재 탐색하는 던전을 방문표시하고 해당 방문표시를 이용해

재귀 호출로 현재 던전에서 이동가능한 다른 던전을 탐색한다.

 

DFS의 백트래킹을 활용해 던전을 더 이상 탐험할 수 없는 경우에는,

해당 던전을 방문하지 않았던 상태로 돌아가서 다른 경로를 탐색할 수 있다.

 

 

DFS를 사용한 이유

DFS는 지정한 시작점에서 부터 탐색을 시작하며,

주어진 방향으로부터 한 경로를 최대한 깊게 탐색한 후

다시 돌아와서 다른 경로를 탐색하는 방식이다.

 

한 가지 경우를 검증하고, 해당 경우가 틀렸다면 이전 단계로 돌아가는 방식은

재귀와 동일한 형태의 알고리즘을 갖기에 DFS는 재귀로 구현된다.

 

해당 문제를 해결하려면 모든 던전 탐험 경로를 탐색하면서

던전을 더 이상 탐험할 수 없는 경우에는 이전 상태로 돌아가

다른 경로를 탐색해야 되기에 깊이 우선 탐색을 활용하였다.

 

 

회고

애초에 문제가 완전탐색란에 분류가 되어있어서

저 문제를 풀려면 완전탐색 개념을 이용해된다는 건 알고있었지만

 

나중에 코팅테스트를 볼 때를 생각해,

왜 해당 문제가 완전탐색 알고리즘을 쓰는지 정리해봤다.

특정 알고리즘을 쓸 때 이유는 알고 써야한다고 생각한다.

 

이번 문제를 풀면서 깊이 우선 탐색을 어떤 상황에서 사용하는지,

해당 알고리즘은 어떤식으로 구현하는지를 배우게되었다.

 

---

 

안드로이드 앱 개발 입문 4주차 정리 (2)

 

액티비티 생명주기

 

액티비티 생명주기란?

액티비티에는 생명주기(LifeCylce)는 액티비티가

생성되고 소멸되기까지의 일련의 상태 변화를 의미한다.

 

Android에서는 다양한 상황에 따라 액티비티의 상태가 변화하며,

이를 효과적으로 관리하기 위해 일련의 콜백 메서드들이 제공된다.

 

 

액티비티의 수명

액티비티의 수명은 액티비티가 생성되고 종료되기까지의 전체 과정을 의미한다.

 

onCreate()를 호출해 액티비티를 생성해 레이아웃 설정을 진행하며,

onDestroy()를 호출해 모든 리소스를 해제하고 액티비티를 소멸시킨다.

 

 

액티비티를 시각적으로 확인이 가능한 구간

사용자가 액티비티를 시각적으로 확인할 수 있는 구간은

onStart()의 호출 시점부터 onStop()가 호출 시점까지에 해당한다.

 

이 기간 중엔 해당 액티비티는 사용자가 상호 작용이 가능하다.

onStop()이 호출되면 새 액티비티가 시작되며 해당 액티비티는 표시되지 않는다.

 

시스템은 액티비티의 전체 수명 내내 onStart() 및 onStop()을 여러 번 호출하는데

이 때 액티비티는 사용자에게 표시되었다 숨겨지는 상태를 오가게 된다.

 

 

액티비티가 전경에서 동작하는 구간

액티비티가 전경(foreground)에서 동작하는 구간,

즉 해당 액티비티가 사용자와 직접 상호작용 할 수 있는 구간은

onResume()의 호출 시점부터 onPause()가 호출되기 전까지에 해당한다.

 

이 기간 중에는 이 액티비티가 모든 액티비티의 앞에 표시된다,

액티비티가 포커스를 잃게 되면 onPause()를 호출하여 액티비티를 일시 정지시킨다.