🐨결정 문제와 최적화 문제: 이해와 예시

결정 문제와 최적화 문제: 이해와 예시

결정 문제 (Decision Problem)

결정 문제는 ‘예’ 또는 '아니오’로 답할 수 있는 문제입니다. 예를 들어, "주어진 그래프에 사이클이 있는가?"와 같은 문제가 결정 문제입니다.

예시: 소수 판별 문제

주어진 숫자가 소수인지 판별하는 결정 문제는 다음과 같이 정의할 수 있습니다:

Input: 양의 정수 n
Output: n이 소수인지 여부 (예: “Yes” 또는 “No”)

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# Example usage
print(is_prime(11))  # Output: True
print(is_prime(15))  # Output: False

결정 문제 예시: 그래프에서 사이클 판별하기

Input: 무방향 그래프 G
Output: 그래프 G에 사이클이 존재하는지 여부 (예: “Yes” 또는 “No”)

def has_cycle(graph):
    visited = set()
    for node in graph:
        if node not in visited:
            if has_cycle_helper(graph, node, visited, parent=None):
                return True
    return False

def has_cycle_helper(graph, current, visited, parent):
    visited.add(current)
    for neighbor in graph[current]:
        if neighbor not in visited:
            if has_cycle_helper(graph, neighbor, visited, current):
                return True
        elif neighbor != parent:
            return True
    return False

# Example usage
graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['C']
}
print(has_cycle(graph))  # Output: True

최적화 문제 (Optimization Problem)

최적화 문제는 주어진 조건 아래에서 어떤 목적 함수의 값을 최대화하거나 최소화하는 것을 목표로 하는 문제입니다. 예를 들어, "주어진 그래프에서 최대한 많은 정점을 방문하는 최단 경로는 무엇인가?"와 같은 문제가 최적화 문제입니다.

예시: 배낭 문제 (Knapsack Problem)

주어진 가방에 최대한 가치 있는 물건을 넣는 최적화 문제로 배낭 문제를 살펴봅시다.

Input:

각 물건의 무게(weights)와 가치(values)
가방의 최대 수용 무게(capacity)

Output: 가방에 넣을 수 있는 물건들의 조합으로 얻을 수 있는 최대 가치

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# Example usage
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # Output: 7

최적화 문제 예시: 동전 거스름돈 문제

주어진 동전의 가치와 거슬러줘야 할 금액이 주어졌을 때, 가장 적은 수의 동전을 사용하여 거스름돈을 주는 문제입니다.

Input:

동전의 가치(coins)
거슬러줘야 할 금액(amount)

Output: 거스름돈으로 사용된 동전의 최소 개수

def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage
coins = [1, 2, 5]
amount = 11
print(min_coins(coins, amount))  # Output: 3 (1개의 5원 동전, 3개의 2원 동전)

저작자표시 비영리 변경금지

붉은 각설탕

🐨결정 문제와 최적화 문제: 이해와 예시