파란색가운의 개발 블로그

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 N,M = map(int,sys.stdin.readline().split()) graph = [[INF] *(N+1) for _ in range(N+1)] for _ in range(M): a,b = map(int,sys.stdin.readline().split()) graph[a][b] = 1 graph[b][a] =..

사용되는 경우: 모든 지점에서 다른 모든 지점까지의 최단 경로 다익스트라 알고리즘과의 차이점: 다익스트라 : 시작점이 정해져 있다 . 그리디 알고리즘 사용 / 시간복잡도 O(ElogV) 플로이드 워셜 알고리즘: 시작점 정해지지 않음. 다이나믹 프로그래밍과 유사 / 시간복잡도 O(N^3) import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 n = int(input()) m..

한번 개념 공부하고 문제도 풀었었지만 여전히 까먹는다 까먹지 않도록 장기기억으로 가져가도록 하자 기본 코드는 정말정말 기본이 되어야 하므로 이걸 올리고도 한번 더 해봐야겠다는 생각이 들었다 한줄 한줄 이게 왜 존재해야 하는 코드인지 다시 생각해봐야겠다. 시간복잡도 : O(ElogV) import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 def djikstra(start):..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 20..

https://www.acmicpc.net/problem/1932 문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며,..

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 def findMax(element): arr = [[0 for _ in range(m)] for _ in range(n)] index = 0 maxarray =[] for i in range(n): for j in range(m): arr[i][j] = (element[index]) index +=1 print(arr..

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 N,M = map(int,sys.stdin.readline().split()) d = [10001] * (M+1) coin = [0] for _ in range(N): value = int(sys.stdin.readline().rstrip()) coin.append(value) d[value] = 1 for i in r..

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 N = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3,N+1): d[i] = d[i-1] + (2 * d[i-2]) % 796796 print(d[N]) 하아 어렵다..... 보텀업 방식으로 푸는 만큼 d[i]와 이전 항들의 관계를 잘 생각해야 하니까 d..

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 N = int(input()) d = [0] * (N) arr = list(map(int,sys.stdin.readline().split())) d[0] = arr[0] d[1] = arr[1] for i in range(2,N): d[i] = max(d[i-1],d[i-2]+arr[i]) print(d[N-1]) 보텀..

import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 X = int(input()) d = [0] * 30001 index = 1 for i in range(2,X+1): d[i] = d[i-1] + 1 if i%2 == 0: d[i] = min(d[i],d[i//2] + 1) elif i%3 == 0: d[i] = min(d[i],d[i//3] + 1) elif i%5 ..