동적계획법
[동적계획법] 가장 긴 바이토닉 부분 수열
가장 긴 증가하는 부분 수열의 응용버전이다. 이전 문제를 풀었다면 어렵지는 않은 문제일 것 같다. 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net from sys import stdin N, A = int(stdin.readline()), list(map(int, stdin.readline().split(" "))) T_L, T_R = [1] * N, [1] * N def get_table_left(ind: int): m = 0 for i in range(ind, -1, -1): if A[ind] > A[i] and m < T_L..
[동적 계획법] 1로 만들기
다른 사람들의 풀이를 보니, 메모이제이션으로 쉽게 풀 수 있는걸 너무 복잡하게 생각한 것 같다. 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net from sys import stdin N = int(stdin.readline()) m = {1: 0} def check(no): global m if no
[동적 계획법] 정수 삼각형
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 저번 문제와 마찬가지로 DP 테이블을 이용해서 쉽게 풀 수 있었다. from sys import stdin N = int(stdin.readline()) L = [] while True: line = list(map(int, stdin.readline().split())) if len(L) == 0: L.append(line) else: prev = L[len(L) - 1] next_line = [] for i, v in enumerate(line): if i == 0: next_line.append(v + prev[0]) elif ..
[동적 계획법] 신나는 함수 실행
동적 계획법의 핵심은 return 값의 재사용. 재사용 할 값을 어떻게 효율적으로 저장 및 탐색할 수 있는지에 대한 고민과 그에 따른 자료구조 선택이 중요한 것 같다. 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net from sys import stdin w_dict = {} input_abc_arr = [] while True: [a, b, c] = map(int, stdin.readline().split()) if a == -1 and b == -1 and c == -1: break else: input_ab..
[동적 계획법] 피보나치 함수
백 트래킹이 마무리가 되고 동적 계획법으로 넘어왔다. 동적 계획법 자체는 거창한 내용은 없었고, 값을 재활용한다는 핵심 개념만 알고 가면 될 것 같다. 값을 저장하고 꺼내오는 과정에서의 최적화에 대한 고민이 중요할 것 같다. 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net from sys import stdin T = int(stdin.readline()) f_arr = [-1] * 41 f_arr[0] = [1, 0] f_arr[1] = [0, 1] def f(n: int): global f_arr if f_arr[n] != -1: return f_arr[n] else: [z1, o1] = f(n - 1..