알고리즘 14주차

동적 계획법

 

---

 

[Gold V] LCS - 9251

2402-ECC-AlgorithmStudy/백준/Gold/9251. LCS/LCS.py at main · daj33/2402-ECC-AlgorithmStudy

 

[Silver I] 지름길 - 1446

2402-ECC-AlgorithmStudy/백준/Silver/1446. 지름길/지름길.py at main · daj33/2402-ECC-AlgorithmStudy

다익스트라 알고리즘 사용하기

graph = [[] for _ in range(d+1)]
dist = [inf]*(d+1)

 

• graph[i]:  i에서 도달 가능한 다른 지점들과 그 거리에 대한 정보. 인접 리스트.
• dist: 시작 지점에서 각 지점까지의 최단 거리를 저장. 무한대 초기화.

 

for i in range(d):
    graph[i].append((i+1, 1))
for _ in range(n):
    start, dest, length = map(int, sys.stdin.readline().split())
    if dest<=d:
        graph[start].append((dest, length))

 

• 기본 경로: 지점 i에서 지점 i+1까지의 거리는 1
• 지름길: 도착 지점(dest)이 목표 거리(d)를 넘지 않는 경우에만 지름길 추가

 

q = []
heapq.heappush(q, (0,0))
dist[0] = 0

• 우선순위 큐(최소 힙: 거리 기준)를 사용하여, 현재까지의 거리가 가장 짧은 지점부터 탐색
• (거리, 도착 지점) 형식으로 초기값 (0, 0)을 큐에 삽입
• 시작 지점(0)에서의 최단 거리를 0으로 초기화

while q:
    w1, u = heapq.heappop(q)

    for v, w2 in graph[u]:
        cost = dist[u] + w2
        if dist[v] > cost:
            dist[v] = cost
            heapq.heappush(q, (cost, v))

• graph[u]: 현재 지점 u에서 도달 가능한 모든 지점 v와 거리 w2
• cost = dist[u] + w2: 현재 지점까지의 최단 거리(dist[u])와 인접 지점으로 가는 거리(w2)를 합산하여 새로운 비용(cost)을 계산
• if dist[v] > cost: 계산된 비용(cost)이 기존에 저장된 최단 거리(dist[v])보다 작으면 갱신
• heapq.heappush(q, (cost, v)): 갱신된 거리를 우선순위 큐에 추가

예제 1번 적용

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

 

w1, u = (0, 0)

i) v, w2 = (50, 10) dist[50] = 10 갱신 성공 ... push(10, 50) 

ii) v, w2 = (50, 20)  cost = 20 갱신 실패 

iii) v, w2 = (1, 1) dist[1] = 1 갱신 성공 ... push(1, 1) 

 

w1, u = (1, 1)

i) v, w2 = (2, 1) dist[2] = dist[1] + 1 = 2 갱신 성공 ... push(2, 2) 

 

.

.

.

 

w1, u = (10, 10)

i) v, w2 = (11, 1) dist[11] = dist[10] + 1 = 11 갱신 성공 ... push(11, 11)

 

w1, u = (10, 50)

i) v, w2 = (100, 10) dist[100] = dist[50] + 10 = 20 갱신 성공 ... push(20, 100)

ii) v, w2 = (51, 1) dist[51] = dist[50] + 1 = 11 갱신 성공 ... push(11, 51)

 

 

.

.

.

w1, u = (49, 49)

i) v, w2 = (50, 1) dist[50] = dist[49] + 1 = 50 갱신 실패 

w1, u = (11, 51)

i) v, w2 = (52, 1) dist[52] = dist[51] + 1 = 12 갱신 성공 ... push(12, 52)

 

.

.

.

w1, u = (20, 60) 

i) v, w2 = (61, 2) dist[61] = dist[60] + 1 = 21 갱신 성공 push(21, 62)

w1, u = (20, 100)

i) v, w2 = (101, 1) dist[101] = dist[100] + 1 = 21 갱신 성공 push(21, 101)

 

.

.

.

 

 

[Bronze I] 알고리즘 수업 - 피보나치 수 1 - 24416

 

2402-ECC-AlgorithmStudy/백준/Bronze/24416. 알고리즘 수업 － 피보나치 수 1/알고리즘 수업 －

 

[Gold V] 평범한 배낭 - 12865

 

2402-ECC-AlgorithmStudy/백준/Gold/12865. 평범한 배낭/평범한 배낭.py at main · daj33/2402-ECC-AlgorithmStudy