XII 주요 알고리즘 문제 풀이 _ DP, Graph

 

1) 사이클 문제

https://www.acmicpc.net/problem/20040

 

import sys

input = sys.stdin.readline

n, e = map(int, input().split(' '))
parent = [-1 for _ in range(n)]

def find_parent(x):
    if parent[x] < 0:
        return x
    else:
        y = find_parent(parent[x])
        parent[x] = y
        return y

def union(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x == y:
        return True
    if parent[x] < parent[y]:
        parent[x] += parent[y]
        parent[y] = x
    else:
        parent[y] += parent[x]
        parent[x] = y
    return False

ans = 0    
for i in range(e):
    node1, node2 = map(int, input().split(' '))

    isCycle = union(node1, node2)
    if isCycle:
        ans = i+1
        break

print(ans)        

 

 

 

2) 특정한 최단경로

https://www.acmicpc.net/problem/1504

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

v, e = map(int, input().split())
graph = [[] for _ in range(v + 1)]

# 방향성 없는 그래프이므로 x, y일 때와 y, x일 때 모두 추가
for _ in range(e):
    x, y, cost = map(int, input().split())
    graph[x].append((y, cost))
    graph[y].append((x, cost))


def dijkstra(start):
    distance = [INF] * (v + 1)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]

            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    # 반환값은 최단 거리 배열
    return distance


v1, v2 = map(int, input().split())

# 출발점이 각각 1, v1, v2일 때의 최단 거리 배열
original_distance = dijkstra(1)
v1_distance = dijkstra(v1)
v2_distance = dijkstra(v2)

v1_path = original_distance[v1] + v1_distance[v2] + v2_distance[v]
v2_path = original_distance[v2] + v2_distance[v1] + v1_distance[v]

result = min(v1_path, v2_path)
print(result if result < INF else -1)

 

 

3) 정수 삼각형

def solution(triangle):
    # 삼각형의 높이
    height = len(triangle)

    # DP를 위한 2차원 배열 생성 및 초기화
    dp = [[0] * i for i in range(1, height + 1)]
    dp[0][0] = triangle[0][0]  # 첫 번째 숫자는 바로 대입

    # 삼각형의 각 위치마다 최댓값을 계산하여 저장
    for i in range(1, height):
        for j in range(i + 1):
            # 왼쪽 대각선 위에서 내려오는 경우
            if j == 0:
                dp[i][j] = dp[i - 1][j] + triangle[i][j]
            # 오른쪽 대각선 위에서 내려오는 경우
            elif j == i:
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
            # 두 대각선 중 최댓값 선택
            else:
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

    # 최종 결과는 삼각형의 가장 아래층에 위치한 값 중 최댓값
    answer = max(dp[height - 1])
    return answer

# 예시 입력
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
print(solution(triangle))  # 출력: 30

 

 

 

 

4) 가장 긴 증가하는 부분 수열 2 (12015)

import sys
input = sys.stdin.readline

#이분탐색의 중요한 특징. 여러 후보들(개수가 많음) 중에서 최적값을 선택해야 한다.
n=int(input())
l=list(map(int,input().split()))

lis=[l[0]]

def find(x):
#더 작은 값을 만났다면 이분탐색하여 l[i]보다 큰 최초의 lis값 찾아주기
    start=0
    end=len(lis)-1
    ans=0 #마지막에 안되는 값으로 끝날 수 있으므로 값 담아두기
    while True:
        if start>end:
            return ans
        mid=(start+end)//2 #lis에 들어갈 lis의 index값
 
        if lis[mid]>=x:
            ans=mid 
            end=mid-1
        else:
             start=mid+1
             
for i in range(1,n):
    if l[i]>lis[-1]: #lis의 맨마지막보다 큰값이면 그냥 넣어주고
        lis.append(l[i])
    elif l[i]==lis[-1]: #같으면 pass
        None
    else:
        lis[find(l[i])]=l[i]
    #print(lis)
print(len(lis))