99클럽 코테 스터디 22일차 TIL - 완점탐색,백트래킹 (프로그래머스- 피로도)

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

프로그래머스

• 오늘의 학습 키워드 : 완전탐색,백트래킹?
• 공부한 내용 

1️⃣ 처음 쓴 풀이법

#처음 쓴 풀이법
def permutations(elements,k,dungeons,current=[]):
    if not elements or k <= 0:
        return len(current)
        
    max_len = len(current)  # 현재 길이로 초기화
    for i in range(len(elements)):
        next_elements = elements[:i]+elements[i+1:]
        if k >=dungeons[elements[i]][0]:
            print(max_len,current)
            max_len = max(max_len, permutations(
                next_elements, 
                k - dungeons[elements[i]][1], 
                dungeons, 
                current + [elements[i]]
            ))
    return max_len

def solution(k, dungeons):
    elements = [i for i in range(len(dungeons))]  # 던전의 인덱스를 리스트로 초기화
    answer = permutations(elements, k, dungeons)  # 탐험 가능한 최대 던전 수 계산
    return answer

 

1. solution 동작

 

• elements는 각 던전의 인덱스 리스트. 예를 들어, 던전이 3개라면 [0, 1, 2].
• permutations 함수에 초기 피로도 k와 던전 정보 dungeons를 전달해 탐험 가능한 최대 던전 수를 반환.

 

def solution(k, dungeons):
    elements = [i for i in range(len(dungeons))]  # 던전의 인덱스를 리스트로 초기화
    answer = permutations(elements, k, dungeons)  # 탐험 가능한 최대 던전 수 계산
    return answer

 

2. permutations 동작

    if not elements or k <= 0:
        return len(current)

• 탐색 가능한 던전이 없거나(not elements), 피로도가 0 이하가 되면 탐색을 종료하고 현재 탐험한 던전 수를 반환: return len(current).

max_len = len(current)  # 현재까지 탐험한 던전 수
for i in range(len(elements)):
    next_elements = elements[:i] + elements[i+1:]  # 현재 선택한 던전을 제외한 나머지 던전
    if k >= dungeons[elements[i]][0]:  # 최소 필요 피로도를 만족하면 탐험 가능
        max_len = max(max_len, permutations(
            next_elements,
            k - dungeons[elements[i]][1],  # 소모 피로도 차감
            dungeons,
            current + [elements[i]]  # 탐험한 던전을 추가
        ))

 

==> 여기서 개선점 if not elements 로 사용시에는 시간복잡도 O(n)이므로 current를 이용하는 것이 아닌 visited를 이용한 풀이

2️⃣ 두번째 개선된 풀이법(current 이용하는 것이 아닌 visited인 boolean 이용하기)

def permutations(elements, k, dungeons, visited, count):
    max_len = count  # 현재까지 탐험한 던전 수를 초기값으로 설정
    
    # 탐험 가능한 모든 던전을 순회
    for i in range(len(elements)):
        # 던전 i를 탐험 가능할 때만 진행
        if not visited[i] and k >= dungeons[elements[i]][0]:
            visited[i] = True  # 던전 i를 방문 표시
            # 재귀 호출로 다음 탐험 진행 (현재 던전을 탐험한 상태로 진행)
            max_len = max(max_len, permutations(
                elements, 
                k - dungeons[elements[i]][1],  # 소모 피로도를 차감한 남은 피로도
                dungeons, 
                visited, 
                count + 1  # 탐험한 던전 수 증가
            ))
            visited[i] = False  # 백트래킹: 방문 상태 복구
            
    return max_len  # 탐험 가능한 최대 던전 수 반환


def solution(k, dungeons):
    elements = [i for i in range(len(dungeons))]  # 던전의 인덱스를 리스트로 초기화
    visited = [False] * len(dungeons)  # 각 던전의 방문 여부를 저장하는 리스트
    return permutations(elements, k, dungeons, visited, 0)  # 탐험 가능한 최대 던전 수 반환

 

3️⃣ 세번째 개선된 풀이법(visited 이용하고 조건 하나 더 추가하기 현재 max_count보다 작을 경우 중지하는 조건)

def permutations(elements, k, dungeons, visited, count, max_count):
    # 현재 탐험한 던전 수와 최대 던전 수 갱신
    max_count[0] = max(max_count[0], count)

    # 남은 피로도로 탐험 가능한 던전 수가 현재 max_count보다 작으면 중단
    possible = 0
    for i in range(len(elements)):
        if not visited[i] and k >= dungeons[elements[i]][0]:
            possible += 1
    if count + possible <= max_count[0]:  # 더 탐험해도 최대치에 도달할 수 없으면 중단
        return

    # 탐색 진행
    for i in range(len(elements)):
        if not visited[i] and k >= dungeons[elements[i]][0]:  # 탐험 가능 여부
            visited[i] = True
            permutations(
                elements,
                k - dungeons[elements[i]][1],  # 소모 피로도 차감
                dungeons,
                visited,
                count + 1,
                max_count
            )
            visited[i] = False  # 백트래킹: 방문 복구


def solution(k, dungeons):
    elements = [i for i in range(len(dungeons))]
    visited = [False] * len(dungeons)
    max_count = [0]  # 최대 던전 수를 저장할 변수 (리스트로 전달해 참조 가능하게 함)
    permutations(elements, k, dungeons, visited, 0, max_count)
    return max_count[0]

 

• 오늘의 회고
  • 오늘은 오랜만에 백트래킹..? 공부해서 생각보다 푸는데 오래 시간 걸렸던것 같다. 
  • 내일도 백트래킹을 이용한 완전탐색 나오면 좋겠다.. 그러면 좀더 더 잘 알 수 있을지도??