note

가장 빠르게 도달하는 방법 - '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우' - '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' - 최단 경로 문제는 보통 그래프를 이용해 표현 ㄴ 각 지점은 그래프에서 '노드'로 표현되고, ㄴ 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 다익스트라 최단 경로 알고리즘 - 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작 - 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류 - 알고리즘 1) 출발 노드 설정 2) 최단 거리 테이블 초기화 3)..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net n, k = map(int, input().split()) d = [[0 for _ in range(k+1)] for _ in range(n)] for i in range(n): w, v = map(int, input().split()) for j in range(1, k+1): if j < w: d[i][j] = d[i-1][j]..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n = int(input()) a = list(map(int, input().split())) d = [-1000] * n d[0] = a[0] for i in range(1, n): d[i] = max(d[i-1] + a[i], a[i]) print(max(d))

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 예제) n=6, A=[10, 20, 10, 30, 20, 50] -> 길이 4 처음에 리스트 초기화 d=[1, 1, 1, 1, 1, 1] for문을 돌면서 차례대로 각 인덱스까지의 입력받은 배열 값을 비교해서 더 크면 최댓값 +1 1. 10 20 10 30 20 50 1 1 1 1 1 1 2. 10 < 20 이므로 d[..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net n = int(input()) a = [0] for _ in range(n): a.append(int(input())) d = [0] * (n+1) d[1] = a[1] if n >= 2: d[2] = a[1] + a[2] for i in range(3, n+1): d[i] = max(d[i-1], d[i-2] + a[i], d[i-3] + a[i-1] + a[i]) print(d[n])

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n = int(input()) stair = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] for _ in range(n+1)] stair[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n+1): for j in range(10): if j == 0: stair[i][0] = stair[i-1][1] elif j == 9: stair[i][9] = stair[i-1][8] else: stair[i][j] = stair[i-1][j-1] + stair[..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 채점하는데 2분 걸려서 좀 쫄았다 ㅋ 인덱스 에러 방지를 위해 배열을 n의 수만큼 설정해줌. n = int(input()) d = [0] * 1000001 d[2] = 1 d[3] = 1 for i in range(4, n+1): d[i] = d[i-1] + 1 if i % 3 == 0: d[i] = min(d[i//3] + 1, d[i]) if i % 2 == 0: d[i] = min(d[i//2] + 1, d[i]) print(d[n])

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 어차피 마지막칸은 무조건 밟아야 하기 때문에 현재 칸을 밟는 경우의 최댓값을 계산해준다 인덱스 에러가 나지 않기 위해 리스트 인덱스0에 0을 추가했다 n = int(input()) arr = [0] for _ in range(n): arr.append(int(input())) d = [0] * (n+1) d[1] = arr[1] if n >= 2: d[2] = arr[1] + arr[2] for i in ra..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 삼각형을 리스트로 차례대로 입력받은 다음, 인덱스 에러가 나지 않게 거꾸로 for문을 돌려주었다 현재값+최댓값 해서 리스트에 저장해주고 제일 마지막 계산 부분(첫번째 줄)에는 값이 하나밖에 없으니 d[0][0] 출력하면 된다! n = int(input()) d = [list(map(int, input().split())) for _ in range(n)] for i in range(n-2, -1, -1): for j in range(i+1): d[i][j] += max..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net n = int(input()) d =[list(map(int, input().split())) for _ in range(n)] for i in range(1, n): d[i][0] += min(d[i-1][1], d[i-1][2]) d[i][1] += min(d[i-1][0], d[i-1][2]) d[i][2] += min(d[i-1][0], d[i-1][1]) print(..