그리디

그리디는 매 순간 가장 좋아 보이는 선택을 하는 방법이다.

그리디가 최적의 답을 보장하려면 해당 문제에 다음과 같은 성질이 필요하다.

• 그리디 선택 속성: 현재의 최선 선택이 최종 최적해에도 포함된다.
• 최적 부분 구조: 전체 문제의 최적해가 부분 문제의 최적해로 구성된다.

그리디는 빠르고 단순하지만, 현재의 최선이 전체의 최선으로 이어진다는 근거가 있는 문제에서만 최적의 답을 보장한다.

그런데 그걸 어떻게 판단하지?

완전 탐색

가능한 경우를 모두 탐색하는 방법이다.

1. 가능한 경우를 모두 만든다.
2. 각각 조건에 맞는지 확인한다.
3. 조건을 만족하는 것 중 정답을 선택한다.

numbers = [1, 2, 3, 4]

for i in range(len(numbers)):
    for j in range(i + 1, len(numbers)):
        if numbers[i] + numbers[j] == 5:
            print(numbers[i], numbers[j])

실제로 확인하는 순서는 아래와 같다.

1 + 2 = 3
1 + 3 = 4
1 + 4 = 5 ✅
2 + 3 = 5 ✅
2 + 4 = 6
3 + 4 = 7

출력 결과는 다음과 같다.

1 4
2 3

모든 조합을 확인하기 때문에 정답을 놓치지 않는다.

완전 탐색의 대표적인 구현 방법

1. 반복문

경우의 수가 단순하고 작을 때 사용한다.

for i in range(10):
    for j in range(10):
        # 모든 i, j 확인

2. 순열과 조합

파이썬에서는 itertools를 사용할 수 있다.

from itertools import combinations

numbers = [1, 2, 3, 4]

for selected in combinations(numbers, 2):
    if sum(selected) == 5:
        print(selected)

출력 결과는 다음과 같다.

(1, 4)
(2, 3)

순서가 중요하면 permutations()를 사용한다.

from itertools import permutations

for selected in permutations([1, 2, 3], 2):
    print(selected)

3. DFS와 백트래킹

선택을 여러 단계 반복해야 하는 경우에 사용한다.

numbers = [1, 2, 3]
selected = []


def dfs(index):
    if index == len(numbers):
        print(selected)
        return

    # 현재 숫자를 선택
    selected.append(numbers[index])
    dfs(index + 1)
    selected.pop()

    # 현재 숫자를 선택하지 않음
    dfs(index + 1)


dfs(0)

언제 사용할까?

먼저 경우의 수가 작은지 충분히 계산해야 한다.

N = 10, 2^N = 1,024      → 가능
N = 20, 2^N = 약 100만   → 보통 가능
N = 50, 2^N = 약 1,000조 → 사실상 불가능

대략 파이썬에서는 연산량이 수백만에서 수천만 정도라면 문제의 시간 제한에 따라 시도할 수 있다.

그리디와 완전 탐색 비교

그리디

• 지금 가장 좋아 보이는 것만 선택한다.
• 빠르지만 최적해를 놓칠 수 있다.

완전 탐색

• 가능한 모든 경우를 확인한다.
• 경우의 수가 많으면 시간이 오래 걸린다.

DP

핵심 논리는 다음과 같다.

현재 답을 이전에 구한 답으로 만들 수 있는가?

• 이전 계산 결과를 저장해서 재사용한다.
• 같은 계산을 반복하지 않도록 이전 결과를 저장한다.

예를 들어 피보나치 수열은 다음과 같은 관계를 가진다.

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)

n = 5
dp = [0] * (n + 1)

dp[1] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])  # 5

동적 계획법은 이전 결과를 저장하고, 다음 계산 때 꺼내서 쓴다.

대표 문제는 다음과 같다.

• 피보나치
• 계단 오르기
• 최소 비용 구하기
• 배낭 문제

해시

특정 값이 존재하는지 또는 값에 대응하는 정보를 빠르게 찾는 구조다.

파이썬에서는 주로 dict와 set을 사용한다.

dict, 값과 정보를 연결

scores = {
    "민수": 90,
    "영희": 85,
}

print(scores["민수"])  # 90

"민수"라는 Key와 90이라는 Value가 연결되어 있다.

개수를 셀 때도 많이 사용한다.

numbers = [1, 2, 1, 3, 1]
counts = {}

for number in numbers:
    counts[number] = counts.get(number, 0) + 1

print(counts)  # {1: 3, 2: 1, 3: 1}

set, 존재 여부 확인

members = {"민수", "영희", "철수"}

if "영희" in members:
    print("존재함")

대표 문제는 다음과 같다.

• 중복 확인
• 등장 횟수 세기
• 전화번호나 이름 검색
• 두 숫자의 합 찾기

스택

스택은 나중에 넣은 값을 먼저 꺼내는 자료구조다.

넣기: 1 → 2 → 3
꺼내기: 3 → 2 → 1

파이썬에서는 list로 구현한다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

print(stack.pop())  # 3
print(stack.pop())  # 2

대표적인 예는 괄호 검사다.

text = "(())"
stack = []

for char in text:
    if char == "(":
        stack.append(char)
    else:
        if not stack:
            print("잘못된 괄호")
            break
        stack.pop()
else:
    if not stack:
        print("올바른 괄호")
    else:
        print("잘못된 괄호")

(를 만나면 저장하고, )를 만나면 가장 최근의 (를 제거한다.

대표 문제는 다음과 같다.

• 괄호 검사
• 뒤로 가기
• 실행 취소
• DFS
• 가장 가까운 큰 수 찾기

핵심 질문은 다음과 같다.

가장 최근에 저장한 값을 먼저 확인해야 하는가?

한눈에 비교

heap

파이썬에서는 heapq를 사용한다. 기본은 최소 힙이라서 가장 작은 값이 heap0에 있다.

힙(Heap)은 가장 큰 값 또는 가장 작은 값을 빠르게 꺼내기 위한 자료구조

예를 들어 숫자를 이렇게 넣었다고 치자 (5,2,8,1)

최소 힙에서는 항상 가장 작은 1을 먼저 꺼낼 수 있고, 최대 힙에서는 항상 가장 큰 8을 꺼낼 수 있다. 다만 내부가 완전히 정렬이 되어있지 않다. 최소 힙은 오직 다음 규칙만 지킨다.

부모가 자식보다 작거나 같다.

그래서 최소 힙의 맨 위에는 항상 최솟값이 있다.

시간은 보통 다음과 같다.

• 값 후기
• 최솟값 또는 최댓값 제거 : O(log n)
• 최솟값 또는 최댓값 확인 : O(1)

정렬은 전체 순서가 필요할 때 사용하고, 힙은 현재 가장 작은 것 하나를 반복해서 선택해야 할 때 유용

예를 들면 작업 우선순위, 가장 짧은 경로를 찾는 다익스트라, 가장 작은 음식 두 개를 계속 섞는 문제등에 사용된다.

파이썬의 heapq는 기본적으로 최소 힙

파이썬에써는 heapq를 사용. 기본은 최소 힙이라서 가장 작은 값이 항상 heap0에 있어.

import heapq

heap =

heapq.heappush(heap, 5) heapq.heappush(heap, 2) heapq.heappush(heap, 8) heapq.heappush(heap, 1)

print(heap0) # 1.최솟값 확인 print(heapq.heappop(heap)) # 1. 최솟값 제거 print(heapq.heappop(heap))

heap 리스트 전체가 정렬된 모습은 아님

print(heap)

출력된 리스트가 완전히 정렬되어 있지 않아도 heap0은 항상 최솟값이다. 기존 리스트를 힙으로 바꾸려면 heapify()를 사용한다.

numbers = 5,2,8,1 heapq.heapify(numbers) print(numbers0) #1

최대 립이 필요하면 가장 간단하게 값에 -를 붙인다.

import heapq

heap =

heapq.heappush(heap,-5) heapq.heappush(heap,-2) heapq.heappush(heap,-8)

maximum = -heapq.heappop(heap)

print(maximum) # 8

우선순위를 함께 저장할 때는 튜플을 넣으면 돼. 튜플의 첫 번째 값부터 비교

import heapq

heap =

heapq.heappush(heap, (2, "청소")) heapq.heappush(heap, (1, "공부")) heapq.heappush(heap, (3, "게임"))

priority, task = heapq.heappop(heap)

print(priority, task)

heapq.heappush(heap, value) # 추가 heapq.heappop(heap) # 최솟값 제거하고 반환 heap0 # 최솟값 확인만 하기