[AI 부트캠프] DAY 42 - 코딩 테스트 3

[오늘의 일지]

코딩 테스트 - 동적 계획법 (DP), 힙, 다익스트라 공부하기

[상세 내용]

코딩 테스트 사전 지식

동적 계획법 (Dynamic Programming; DP)

- 동적 계획법(Dynamic Programming; DP)은 컴퓨터 과학과 수학에서 최적화 문제 및 결정 문제를 해결하기 위한 강력한 알고리즘 기법 중 하나입니다. 주로 반복되는 부분 문제(subproblem)를 효율적으로 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 방법으로 사용됩니다. 동적 계획법은 다양한 문제에 적용됩니다. 일반적으로 최적화 문제를 해결하는 데 사용되며, 예로는 피보나치수열 계산, 최장 공통부분 문자열 찾기, 배낭 문제, 그래프 경로 문제 등이 있습니다. DP는 반복되는 계산을 줄이고, 최적화된 해결책을 찾는 데 사용되는 강력한 알고리즘입니다. DP는 다음과 같은 특징을 갖고 있습니다.

• Optimal Substructure (최적 부분 구조): 큰 문제를 작은 부분 문제로 나눌 수 있으며, 작은 부분 문제의 최적 해결 방법을 결합하여 전체 문제의 최적 해를 찾을 수 있어야 합니다.
• Overlapping Subproblems (중복되는 부분 문제): 동일한 부분 문제가 여러 번 계산되는 경우, 결과를 캐싱하여 중복 계산을 피합니다. DP 알고리즘은 다음 두 가지 접근 방식으로 나뉩니다:

- DP 알고리즘은 다음 두 가지 접근 방식으로 나뉩니다

• Top-Down (Memoization): 재귀적인 방식으로 큰 문제를 작은 부분 문제로 분할하고, 중복 계산을 피하기 위해 작은 부분 문제의 결과를 캐싱합니다. 이를 메모이제이션(Memoization)이라고도 합니다.
• Bottom-Up (Tabulation): 작은 부분 문제부터 시작하여 큰 문제까지 순차적으로 해결합니다. 작은 부분 문제의 결과를 테이블에 저장하고, 이를 활용하여 큰 문제를 해결합니다.

- 피보나치수열의 예시 : 그냥 계산하면 위에서 나오는 중복문제가 시간복잡도를 커지게 한다

# 기존 피보나치 수열 계산 코드
def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

 

- DP의 Top-Down 방식을 적용한 피보나치수열

memo = {}

def fibo(n):
    if n == 1 or n == 2:
        return 1
    if n not in memo:
        memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]

 

- DP의 Bottom-Up 방식을 적용한 피보나치수열

memo = {}

def fibo(n):
    for i in range(3, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

 

힙 (Heap - priority queue)

- 힙(Heap)은 특정한 규칙을 따르는 이진트리(Binary Tree) 기반의 자료구조로, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙은 우선순위 큐, 힙 정렬, 그래프 알고리즘(최단 경로 탐색), 스케줄링 등 다양한 애플리케이션에서 사용되며, 데이터에서 가장 크거나 작은 값을 빠르게 찾아야 하는 상황에 유용합니다. 힙은 다음과 같은 특징을 갖고 있습니다. 

• 완전 이진트리(Complete Binary Tree): 힙은 완전 이진트리 구조를 갖습니다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 순서대로 채워져 있는 트리입니다.
• 부모-자식 노드 간의 관계: 힙에서 각 노드는 부모 노드와 자식 노드 간의 관계를 갖습니다. 최소 힙(Min Heap)의 경우 부모 노드의 값은 자식 노드의 값보다 작거나 같아야 하고, 최대 힙(Max Heap)의 경우 부모 노드의 값은 자식 노드의 값보다 커야 합니다.
• 우선순위 규칙: 힙은 우선순위 규칙에 따라 노드의 값을 저장합니다. 최소 힙에서는 가장 작은 값을 가진 노드가 루트 노드에 위치하며, 최대 힙에서는 가장 큰 값을 가진 노드가 루트 노드에 위치합니다.

- 힙은 주로 다음 두 가지 연산을 지원함

• 삽입(Insertion): 새로운 값을 힙에 추가합니다. 이때, 힙의 특성을 유지하기 위해 값을 추가한 후에 필요에 따라 노드들을 재배치합니다.
• 추출(Extraction): 힙에서 우선순위가 가장 높은(또는 낮은) 값을 추출합니다. 이때, 루트 노드의 값을 반환하고, 루트 노드를 제거한 후에 힙의 특성을 유지하기 위해 다른 노드들을 재배치합니다.

출처:https://ko.wikipedia.org/wiki/%ED%9E%99_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

 

- 힙 사용 코드

from heapq import heapify, heappop, heappush
# heap의 선언(리스트와 같이 만든다)
heap = [] 

# heap의 선언(기존에 있는 리스트에 선언)
a = [3, 5, 2, 1, 6, 4]
heapify(a)

# heap의 원소 추가
heappush(a, 0)

# heap의 원소 삭제
heappop(a)

 

다익스트라(Dijkstra)

- 다익스트라(Dijkstra) 알고리즘은 그래프 내에서 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 네덜란드의 컴퓨터 과학자 Edsger W. Dijkstra에 의해 개발되었습니다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 사용되며, 음수 가중치를 가지는 간선이 없는 경우에 사용하기 적합합니다. 다익스트라 알고리즘은 그래프 내의 모든 노드를 탐색하므로 시간 복잡도는 O(V^2) 또는 O(V^3) 일 수 있습니다. 그러나 우선순위 큐를 사용하여 최소 거리 노드를 효율적으로 선택하는 버전인 "개선된 다익스트라 알고리즘"을 사용하면 시간 복잡도를 O(E + V*log(V))로 개선할 수 있습니다.

• E: 그래프의 간선(Edges)의 수를 나타냅니다.
• V: 그래프의 노드(Vertex)의 수를 나타냅니다.

- 다익스트라 기본 알고리즘

1. 시작 노드에서부터 모든 다른 노드까지의 최단 거리를 저장하는 배열을 초기화합니다. 시작 노드의 최단 거리는 0으로 설정하고, 다른 노드들의 최단 거리는 무한대(infinity)로 초기화합니다.
2. 아직 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다. 처음에는 시작 노드를 선택합니다.
3. 선택한 노드를 현재 노드로 하고, 현재 노드와 연결된 모든 인접 노드를 검사합니다. 인접 노드를 통해 현재 노드로 가는 거리를 계산하고, 이 거리가 현재까지 저장된 최단 거리보다 짧으면 최단 거리를 업데이트합니다.
4. 모든 노드를 방문할 때까지 2단계와 3단계를 반복합니다. 방문한 노드는 표시하고, 이미 최단 거리가 계산된 노드는 다시 방문하지 않습니다.
5. 모든 노드에 대한 최단 거리가 계산되면, 시작 노드로부터 다른 노드까지의 최단 경로를 찾을 수 있습니다.

 

출처:https://pages.cs.wisc.edu/~pin-chun/

 

연습문제

- DP

LeetCode - The World's Leading Online Programming Learning Platform

 

LeetCode - The World's Leading Online Programming Learning Platform

 

- 다익스트라

LeetCode - The World's Leading Online Programming Learning Platform

 

[마무리]

 오늘도 어제에 이어서 요즘 코딩 테스트에서 중요하게 다뤄지고 있는 자료구조와 알고리즘에 대해서 개념적으로 배워보고 연습문제도 풀어보았습니다. 오늘이 마지막날이고 개념적으로도 가장 어려운 부분이라 그냥 개념을 이해한다는 생각으로 수업을 들었습니다. 나이도가 어찌 되었든 이제는 큰 틀이 완성이 되었으니 처음부터 파트별로 차근차근 연습문제들을 잘 찾아 풀어보면서 개념을 복습하고 문제해결 능력을 잘 키워봐야 할 거 같습니다.