풀이

풀이과정 생각정리

• 던전에 대한 매개변수가 모두 주어지므로, 해당 변수들을 모두 처리하며 조건에 맞게 처리하고 탐험할 수 있는 던전의 수를 리스트에 저장하고자 함
• 이 경우에 순열 (permutation)을 사용하여 모든 요소를 생성하고 비교해보고자 함

정답 코드

from itertools import permutations

def solution(k, dungeons):
    answer = []
    # 테스트 케이스가 적기때문에 모든 경우의 수를 만들어 놓고, 그 안에서 조건을 생성하여
    # 모든 경우에 대한 답을 구하고, 그 중 최대 던전 수를 구하는 로직으로 구성함
    for i in permutations(dungeons, len(dungeons)):
        necessity = k # 현재 피로도
        count = 0 # 완료한 던전 수
        
        # print(i)
        
        for j in i:
            if necessity >= j[0]: # 만약 피로도가 최소 필요도 보다 높다면
                necessity -= j[1] # 현재 피로도에서 소모 피로도를 빼준다
                count += 1 # 던전을 1번 완료하였으므로 1을 더해준다.
                
            else:
                break # 그렇지 않으면 break
        
        answer.append(count) # 탐험할 수 있는 던전 수를 저장하기
    
    # print(answer)
    
    return max(answer)

코드리뷰

아래는 작성하신 코드의 로직과 상세한 코드 리뷰입니다. 이 내용을 Velog 포스팅에 그대로 활용하셔도 좋습니다.

---

코드 로직 개요

이 코드는 피로도 문제에서, 주어진 피로도 k와 각 던전의 최소 필요 피로도와 소모 피로도가 담긴 리스트 dungeons를 이용하여,
모든 가능한 던전 방문 순서를 생성한 후, 각 순서대로 던전을 탐험할 수 있는지 시뮬레이션합니다.
각 순서에서 탐험할 수 있는 던전의 수를 구하고, 그 중 최대값을 결과로 반환합니다.

핵심 아이디어는 완전 탐색(Brute Force)를 통해 모든 순서를 고려하는 것입니다.
입력 데이터(던전의 수)가 많지 않으므로 itertools.permutations를 사용하여 모든 경우의 수를 생성해도 성능 문제가 없습니다.

---

코드

from itertools import permutations

def solution(k, dungeons):
    answer = []
    # 테스트 케이스가 적기 때문에, 모든 경우의 수(던전 순서)를 만들어 놓고,
    # 각 경우에 대해 조건을 검사하여 탐험할 수 있는 던전의 개수를 구한 후, 
    # 그 중 최대 던전 수를 구하는 로직입니다.
    for i in permutations(dungeons, len(dungeons)):
        necessity = k  # 현재 피로도
        count = 0      # 탐험한(완료한) 던전 수
        
        # 생성된 순열 i는 던전들의 방문 순서를 나타냅니다.
        for j in i:
            # 각 던전 j는 [최소 필요 피로도, 소모 피로도] 형태입니다.
            # 만약 현재 피로도(necessity)가 해당 던전의 최소 필요 피로도 이상이면,
            if necessity >= j[0]:
                necessity -= j[1]  # 던전을 탐험하고 나면, 소모 피로도만큼 현재 피로도를 차감합니다.
                count += 1         # 탐험 성공 시, 탐험한 던전 수를 증가시킵니다.
            else:
                # 현재 피로도가 부족하면 더 이상 탐험할 수 없으므로, 해당 순열에 대한 탐험을 중단합니다.
                break
        
        # 이 순열에서 탐험할 수 있는 던전의 수(count)를 answer 리스트에 저장합니다.
        answer.append(count)
    
    # 모든 순열 중에서 탐험할 수 있는 던전 수의 최댓값을 반환합니다.
    return max(answer)

---

상세 코드 리뷰

1. from itertools import permutations

• itertools.permutations
  • Python의 내장 모듈인 itertools에 있는 permutations 함수는 주어진 iterable(여기서는 dungeons)의 모든 가능한 순서를 생성합니다.
  • 예를 들어, 던전이 3개라면 3! (즉, 6)가지의 순서가 만들어집니다.

2. 후보 순열 생성 및 시뮬레이션

• for i in permutations(dungeons, len(dungeons)):
  • len(dungeons)를 두 번째 인자로 주어 전체 던전을 모두 사용하는 순열(모든 방문 순서)을 생성합니다.
• necessity = k
  • 각 순열마다 초기 피로도를 k로 설정합니다.
• for j in i:
  • 생성된 순열 i의 각 던전을 순서대로 확인합니다.
• 조건 검사 (if necessity >= j[0]:)
  • 현재 피로도가 해당 던전의 최소 필요 피로도 이상이면, 던전을 탐험할 수 있습니다.
  • 탐험 후에는 necessity -= j[1]를 통해 현재 피로도에서 소모 피로도를 차감합니다.
  • count를 증가시켜 탐험한 던전 수를 기록합니다.
• else: break
  • 만약 현재 피로도가 던전을 탐험하기에 부족하면, 더 이상 해당 순열에서는 추가 던전을 탐험할 수 없으므로 내부 반복문을 종료합니다.

3. 결과 저장 및 최종 반환

• answer.append(count)
  • 각 순열(던전 방문 순서)마다 탐험한 던전의 수를 리스트 answer에 저장합니다.
• return max(answer)
  • 모든 경우 중에서 가장 많은 던전을 탐험할 수 있는 순서가 정답이므로, answer 리스트에서 최댓값을 반환합니다.

---

언제 완전 탐색(Brute Force) 기법을 사용해야 하는가?

• 입력 크기가 작을 때:
  • 이 문제의 경우 던전의 수가 상대적으로 작기 때문에, 모든 순서를 생성해도 성능에 큰 문제가 없습니다.
• 모든 가능한 경우를 고려해야 할 때:
  • 조건에 따라 순서가 결과에 큰 영향을 미치는 경우, 모든 순서를 직접 시뮬레이션하여 최적의 해답을 찾습니다.

---

결론

이 코드는 모든 던전 순서를 생성하여 각 순서마다 시뮬레이션하고, 최대 탐험 가능 던전 수를 찾아 반환하는 완전 탐색(Brute Force) 접근법입니다.