백준 플레를 향해서 - 12월 둘째주(12.5~12.11)

사실 입대하기 전 알고리즘 공부를

 

DP, 트리 자료구조 정도에서 멈췄던 것 같다.

 

DP를 조금 더 풀어보고 다익스트라 알고리즘, 트리, 힙을 조금 더 공부해보려고 했다.

 

1) DP - 백준 11053 : 가장 긴 증가하는 부분 수열

#DP
import sys

n = int(sys.stdin.readline().strip())
lst = list(map(int,sys.stdin.readline().strip().split()))

answer = [[] for _ in range(n)]


def dp(i):
    j = i-1
    while j >= 0:
        temp = answer[j]
        if temp[-1] < lst[i] and len(temp) >= len(answer[i]):
            answer[i] = temp+[lst[i]]
        j -= 1
    if answer[i] == []:
        answer[i] = [lst[i]]
    
max = 0
for i in range(n):
    dp(i)
    if len(answer[i]) > max:
        max = len(answer[i])
print(max)

처음 생각했던 방식이 메모리초과로 잘 돌아가지 않았던 기억이 난다

주어진 문제를 분할해서 푼다는 개념을 떠올렸더니 풀이에 도움이 됐던 것 같다.

 

2) DP - 백준 2096 : 내려가기

import sys,copy

n = int(sys.stdin.readline().strip())

temp = list(map(int,sys.stdin.readline().strip().split()))
maxlst = copy.deepcopy(temp)
minlst = copy.deepcopy(temp)

for i in range(1,n):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    
    max0 = max(maxlst[0],maxlst[1]) + a
    min0 = min(minlst[0],minlst[1]) + a
    
    max1 = max(maxlst[0],maxlst[1],maxlst[2]) + b
    min1 = min(minlst[0],minlst[1],minlst[2]) + b
    
    max2 = max(maxlst[2],maxlst[1]) + c
    min2 = min(minlst[2],minlst[1]) + c
    
    maxlst = [max0,max1,max2]
    minlst = [min0,min1,min2]
    
    
print(f"{max(maxlst)} {min(minlst)}")

이 문제 역시 문제를 분할해서 푼다는 개념을 떠올리면 금방 풀 수 있었다.

 

3) 다익스트라 - 백준 1753 : 최단경로

 

import sys,heapq

INF = int(1e9)

v,e = map(int,sys.stdin.readline().strip().split())
start = int(sys.stdin.readline().strip())
graph = [[] for _ in range(v)]
minlst = [INF]*v

for i in range(e):
    a,b,w = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,w))
           
def dijkstra(start):
    heap = [(0,start)]
    minlst[start] = 0
    
    while heap:
        dist,now = heapq.heappop(heap)
        if minlst[now] < dist:
            continue
            
        for endPoint,w in graph[now]:
            if minlst[endPoint] > minlst[now] + w:
                minlst[endPoint] = minlst[now] + w
                heapq.heappush(heap,(minlst[endPoint],endPoint))
        
                 
dijkstra(start-1)

for i in range(v):
    if minlst[i] == INF:
        print('INF')
    else:
        print(minlst[i])

다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로 가는 최단경로를 구하는 알고리즘이다.

이 때 정점간의 거리(간선의 가중치)가 항상 양수일때만 사용할 수 있다.

 

이때 힙 자료구조를 활용하면 시간복잡도를 개선할 수 있다.

처음에 힙을 이용하지 않고 풀려다가 시간초과가 발생했고

반복문의 조건을 제대로 따지지 않았다가 힙의 크기가 너무 커져 메모리초과가 발생했던 기억이 난다.

 

그냥 구현하는 법을 외워두는게 좋은 것 같다.

 

4) 다익스트라 - 백준 1504 : 특정한 최단 경로

import sys,heapq
INF = int(1e9)

n,e = map(int,sys.stdin.readline().strip().split())
graph = [[] for _ in range(n)]
minlst = [0]*n

for i in range(e):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    
v1,v2 = map(int,sys.stdin.readline().strip().split())


def dijkstra(start):
    for i in range(n):
        minlst[i] = INF
        
    minlst[start] = 0
    heap = [(0,start)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if dist > minlst[now]:
            continue
        else:
            for endPoint,w in graph[now]:
                if dist + w < minlst[endPoint]:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))

ans1 = [0,0,0]
ans2 = [0,0,0]

dijkstra(0)
ans1[0] = minlst[v1-1]
ans2[0] = minlst[v2-1]

dijkstra(v1-1)
ans1[1] = minlst[v2-1]
ans2[1] = minlst[v2-1]

dijkstra(n-1)
ans1[2] = minlst[v2-1]
ans2[2] = minlst[v1-1]

if INF in ans1 and INF in ans2:
    print(-1)
elif INF in ans1:
    print(sum(ans2))
elif INF in ans2:
    print(sum(ans1))
else:
    print(min(sum(ans1),sum(ans2)))

다익스트라 알고리즘을 3번 사용하면 풀리는 문제였다.

정점간의 간선에 방향이 존재하지 않을 시

두 정점간의 최단거리는 출발지와 도착지가 바뀌어도 차이가 없다는 사실을 기억하자