3 / 16강

모든 후보를 살펴보는 완전 탐색

두 상품의 가격을 합쳐 예산을 정확히 맞추려 합니다. 먼저 가능한 두 상품을 전부 확인하는 방법을 떠올릴 수 있습니다. 이를 완전 탐색 또는 브루트 포스라고 합니다.

작은 입력에서는 좋은 출발점입니다

완전 탐색은 후보를 빠짐없이 만들고, 각 후보가 조건에 맞는지 확인합니다. 최적화 문제라면 조건에 맞는 모든 후보 중 가장 좋은 것을 골라야 합니다. 단순한 만큼 더 빠른 풀이와 결과를 비교하는 기준으로도 쓸 수 있습니다.

def find_pair(prices, budget):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] + prices[j] == budget:
                return (i, j)
    return None

print(find_pair([2, 5, 9, 7], 9))

출력은 (0, 3)입니다. 0번 상품 2와 3번 상품 7의 합이 9입니다. 같은 상품을 두 번 고르지 않도록 j를 i + 1부터 시작합니다. 답이 여러 개면 반복문에서 먼저 발견한 쌍을 반환합니다.

후보 수를 먼저 셉니다

• 두 항목을 고르면 약 n²/2개의 후보가 생깁니다.
• 각 항목을 고르거나 말거나 하면 부분집합이 2^n개입니다.
• 서로 다른 항목을 모두 나열하면 순열이 n!개입니다.

후보를 검사하는 비용도 곱해야 합니다. 후보가 2^n개인데 후보 하나를 검사하는 데 n번의 일이 필요하면 전체는 O(n·2^n)입니다. 후보 수만으로 전체 비용을 단정하지 마세요.

더 빨리 찾을 실마리

가격 x를 봤다면 필요한 다른 가격은 예산 - x입니다. 이미 본 가격을 해시 테이블에 기억하면 매번 이전 상품을 전부 확인할 필요가 줄어듭니다. 단, 같은 상품을 두 번 쓰지 않도록 조회와 저장 순서를 정해야 합니다. 구조는 해싱 수업을 참고하세요.

확인 문제

[4, 4]에서 합 8을 찾는 것은 가능할까요? [4]에서는 왜 다른 결과가 나와야 할까요?