[Python/파이썬] 백준 14002번: 가장 긴 증가하는 부분 수열 4

문제 풀이 수열의 최대 크기가 1000이므로 N2 으로 풀면 된다. dp 값을 갱신하는 방법과 동일하게 dp 수열도 갱신해주면 된다. (아래 코드 참고) 코드 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dpMax = [0] * n dpArr = [[] for _ in range(n)] dpArr[0] = [arr[0]] maxIdx = 0 for i in range(1, n): for j in range(i - 1, -1, -1): if arr[i] > arr[j]: if dpMax[j] + 1 > dpMax[i]: dpMax[i] = dpMax[j] + 1 dpArr[i] = dp..

[Python/파이썬] 백준 2263번: 트리의 순회

문제 풀이 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 후위 순회는 최상위 루트를 맨 마지막에 방문하며, 중위 순회는 왼쪽 서브 트리, 루트, 오른쪽 서브 트리 순으로 방문한다. 따라서, 후위 순회의 맨 마지막 원소는 최상위 루트이며 이를 기준으로 중위 순회를 나누면, 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리임을 알 수 있다. 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이때 중위 순회에서 왼쪽 서브 트리의 범위는 시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1) 중위 순회에서 오른쪽 서브 트리의 범위는 (끝 인덱스 - 오..

[Python/파이썬] 백준 9372번: 상근이의 여행

문제 풀이 문제에서 주어진 정보를 잘 활용해야 한다. 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 따라서 아무 노드나 선택해도 그 노드에서 모든 노드로 갈 수 있음을 의미한다. (아래 그림 참고) 또한 연결 그래프를 유지하기 위한 간선의 최소 개수는 (노드의 수 - 1)이다. 이를 신장 트리라 한다. https://terms.naver.com/entry.naver?docId=837730&cid=42344&categoryId=42344 신장 트리 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리. 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. terms.naver.com 즉, 비행기의 종류 = 간선 수 여행 갈 나라의 수 = 노드의 수 간선의 최소..

[Python/파이썬] 백준 5639번: 이진 검색 트리

문제 풀이 전위 순회한 결과 50 30 24 5 28 45 98 52 60 첫 번째 원소가 루트 노드 (전위 순회의 성질에 의해) 왼쪽 서브 트리 = 루트 노드보다 작은 원소인 경우 오른쪽 서브 트리 = 루트 노드보다 큰 원소의 경우 전위 순회를 했으므로 루트 노드보다 큰 원소가 나오는 지점이 왼쪽 서브 트리와 오른쪽 서브 트리를 나누는 지점과 같다. 50 30 24 5 28 45 98 52 60 초록 = 루트 노드, 빨강 = 왼쪽 서브 트리, 파랑 = 오른쪽 서브 트리 위 결과를 활용해 후위 순회를 해주면 된다. 코드 import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline pre = [] while True: try: pre.appen..

[Python/파이썬] 백준 1417번: 국회의원 선거

문제 풀이 기호 1번을 제외한 나머지 표를 최대 힙에 넣는다. 힙을 pop()했을 때 나온 후보의 표가 기호 1번의 표보다 많다면, 그 후보를 한명 매수하고 다시 힙에 넣는다. 위 과정을 기호 1번의 표가 제일 많을 때까지 반복한다. 코드 import sys, heapq input = sys.stdin.readline n = int(input()) win = int(input()) nums = [] for _ in range(n - 1): num = int(input()) heapq.heappush(nums, (-num, num)) cnt = 0 while nums: num = heapq.heappop(nums)[1] if num >= win: num -= 1 win += 1 cnt += 1 heapq...

[Python/파이썬] 백준 11779번: 최소비용 구하기 2

문제 풀이 다익스트라 알고리즘을 사용하되, 최단경로 값이 갱신될 때 그때의 노드 값도 함께 기록한다. 시작 노드가 1번 일 때, 1. 초기값 distance : 1번 노드에서 다른 노드로 갈 수 있는 최단 경로 1 2 3 4 5 6 0 4 2 INF INF INF nearnest 값 : 방문한 노드({1}) 중에서 가장 가까운 노드 1 2 3 4 5 6 1 1 1 1 1 1 2. 갱신 distance : 1번 노드에서 n번 노드로 가는 비용보다 1~3, 3~n으로 가는 비용이 더 작으면 갱신 1 2 3 4 5 6 0 4 2 INF 6 (갱신) INF nearnest 값 : 방문한 노드({1, 3}) 중에서 가장 가까운 노드 1 2 3 4 5 6 1 1 1 1 3 (갱신) 1 3. 2번 반복 문제에서 주어..

[Python/파이썬] 백준 1865번: 웜홀

문제 풀이 벨만 포드 알고리즘을 사용해서 풀면 된다. 단, 일반적인 벨만 포드 알고리즘이 아닌 "음의 간선 사이클"이 존재하는지 여부만 구하면 된다. 또한 "도로"는 양방향이고 "웜홀"은 단방향임을 주의해서 입력받아야 한다. https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13 코드 from sys import stdin input = stdin.readline def bf(): for i in range(n): for j in range(len(edges)): cur, next, cost = edges[j] if dist[next] > dist[cur] + cost: dist[next] = ..

[Python/파이썬] 백준 5014번: 스타트링크

문제 풀이 전형적인 너비우선 탐색 문제, heap을 이용해 풀어보았다. 코드 from sys import stdin import heapq input = stdin.readline f, s, g, u, d = map(int, input().split()) visited = [False] * (f + 1) q = [(0, s)] visited[s] = True ans = "use the stairs" while q: cnt, now = heapq.heappop(q) if now == g: ans = cnt break if now - d > 0: if not visited[now - d]: visited[now - d] = True heapq.heappush(q, (cnt + 1, now - d)) if n..

[Python/파이썬] 백준 1238번: 파티

문제 풀이 다익스트라 알고리즘을 사용하면 된다. 단, 학생들이 마을로 돌아가는 경우도 구해야 하는데, 이때의 간선은 주어진 입력의 시작점과 끝점을 서로 바꾸면 된다. 코드 from sys import stdin import heapq input = stdin.readline n, m, x = map(int, input().split()) toX = [[] for _ in range(n + 1)] #집에서 파티 마을로 가는 최단 경로 toHome = [[] for _ in range(n + 1)] #파티 마을에서 집으로 가는 최단 경로 for _ in range(m): a, b, t = map(int, input().split()) toX[a].append((b, t)) toHome[b].append((a..

[Python/파이썬] 백준 14938번: 서강그라운드

문제 풀이 다익스트라 방법과 플로이드-와샬 방법이 있는데, 노드의 개수가 적어서 플로이드-와샬 방법으로 풀었다. 플로이드-와샬 알고리즘을 안다면 쉽게 풀 수 있는 문제이므로 풀이는 생략함. 코드 from sys import stdin input = stdin.readline n, m, r = map(int, input().split()) items = list(map(int, input().split())) graph = [[1e9] * (n + 1) for _ in range(n + 1)] for _ in range(r): a, b, l = map(int, input().split()) graph[a][b] = l graph[b][a] = l for i in range(n + 1): for j in r..