[프로그래머스/Python] Lv.2 피로도

문제: https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

사용 알고리즘: 완전 탐색

 

 

제한사항

• K 는 1 이상 5,000 이하인 자연수
• dungeons 의 던전 개수는 1 이상 8 이하
  • dungeons 의 각 행은 각 던전의 [최소 필요 피로도, 소모 피로도]
  • 최소 필요 피로도는 항상 소모 피로도보다 크거나 같음
  • 최소 필요 피로도와 소모 피로도는 1 이상 1,000 이하인 자연수
  • 서로 다른 던전의 [최소 필요 피로도, 소모 피로도]가 서로 같을 수 있음

 

입출력 예시

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

 

 

 

문제에서 가장 먼저 보였던거는 던전의 개수, 적은 개수이기 때문에 완전 탐색으로도 풀 수 있겠다 싶었다. 

-> 던전의 최대 개수는 8개이므로 최대 8! (40320)번의 for 문만 돌면 되겠구나 싶었음. 

 

그리고 사실 문제를 읽으면서 dfs 로 푸는건가? 싶기도 했지만, dfs 로 잘 못 풀어서 완전 탐색으로 먼저 도전했는데 별 문제없이 통과됐다. 

(통과 되고 찾아보니 dfs 로 푼 풀이도 많이 보였다)

 

 

일단 이 문제를 완전 탐색으로 풀어보자.

 

던전들을 탐색할 수 있는 모든 경우의 수를 다 돌아야하는데, 나는 itertools 에 permutations 를 사용해서 가능한 모든 경우의 수를 만들었다. 

 

먼저 던전의 인덱스로 배열을 만들고, 그 배열의 요소들을 가지고 가능한 모든 경우의 수를 만들었다. (순열)

(permutations 에 배열을 넣어주면 배열의 요소로 만들 수 있는 모든 순열 조합을 만들어준다)

 

각 턴에서 만들어진 order 의 각 요소를 돌면서 k 값이 던전의 최소 필요 피로도보다 크거나 같으면 k 값에서 소모 피로도를 빼주었다. 

 

 

전체 코드

def solution(k, dungeons):
    answer = 0    
    dungeons_index = [i for i in range(len(dungeons))] # 던전의 인덱스로 만들어진 배열
    for order in permutations(dungeons_index): # 인덱스 배열의 요소를 가능한 모든 순열로 만들어줌
        count = 0
        tempK = k # k 값은 각 턴마다 복사해서 사용
        for x in order:
            if tempK >= dungeons[x][0]:
                tempK -= dungeons[x][1]
                count += 1 # count 값 +1
        answer = max(answer, count) # 더 큰 값이 answer
    return answer

 

 

 

이제 dfs 로 푼 코드를 살펴보자. 

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0

def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

dfs 이기 때문에 재귀를 통해서 갈 수 있는 만큼 쭉쭉 타고 들어가도록 구현이 되어있다. 

배울만 했던 아이디어는 더 이상 갈 곳이 없어서 다시 돌아왔을 때 visited[j] = 0 으로 미방문 처리를 해주어서 다음 턴에서 문제 없이 visited 배열을 사용할 수 있는 것이었다. 기억해 두었다가 사용해보면 좋을 아이디어인 것 같다. 

 

그리고 나는 왜인지 global 은 잘 손이 가지 않아서 쓰지 않는데, 이런식으로 사용하기 좋은 것 같다. 

 

(오늘도 갈길이 먼 것을 느끼며.. ) 

 

 

시간 복잡도

 

- dungeon_index 배열 초기화

dungeons_index = [i for i in range(len(dungeons))]

# 시간 복잡도: O(n)

 

 

- 이중 for 문

for order in permutations(dungeons_index): # 가능한 모든 순열 생성 O(n!)
    count = 0
    tempK = k
    for x in order: # O(n)
        if tempK >= dungeons[x][0]:
            tempK -= dungeons[x][1]
            count += 1
   answer = max(answer, count)
   
# 시간 복잡도: O(n! * n)

 

 

그래서 총 시간 복잡도는 O(n) + O(n! * n) = O(n! * n) 이다. 

 

O(n! * n) 은 매우 빠르게 증가하므로 엄청 n 이 커질 수록 엄청 비효율적인 코드.. 이번 문제에서는 n 값이 작아서 통과할 수 있었던 듯

 

 

그렇다면 dfs 를 사용해서 푼 코드의 시간 복잡도는 어떻게 될까?

 

- dfs 함수

 

던전의 개수가 n 일 때, dfs 는 각 던전에 대해 두 가지 선택을 할 수 있다 -> 탐험하거나 / 탐험하지 않거나

-> 모든 던전에 대해 dfs 로 탐색하기 때문에 던전의 개수가 n개라면 탐색해야 할 경로의 수는 2^n 개

 

for 문을 돌면서 n 개의 던전을 확인할 수 있으므로 시간 복잡도는 O(2^n * n)

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0
            
# 시간 복잡도: O(2^n * n)

 

 

- 완전 탐색으로 푼 코드와 dfs 로 푼 코드의 시간 복잡도를 비교해보면 뭐가 더 클까?

 

당연히 완전 탐색으로 푼 코드의 시간 복잡도가 더 크다! 

아래 그래프로 보면 n 값이 커질수록 팩토리얼의 증가율이 제일 빠르게 증가하는 것을 알 수 있다.

(2^n 도 빠르게 증가하고 있지만 그거보다 더 빠르게 증가하고 있음)