기록하고 까먹지 말기

날짜 : 2023. 10. 03 사용 언어 : python 문제 코드 def solution(tri): r = len(tri) res = [[0] * i for i in range(1, len(tri) + 1)] res[0] = tri[0] for i in range(len(tri)-1): for j in range(i + 1): now = res[i][j] left = tri[i+1][j] # 왼쪽 아래의 수 res[i+1][j] = max(now + left, res[i+1][j]) right = tri[i+1][j+1] # 오른쪽 아래의 수 res[i+1][j+1] = max(now + right, res[i+1][j+1]) # for i in res: # print(i) return max(res..

날짜 : 2023. 06. 23 사용 언어 : python 문제 코드 정답(DP 사용) import sys n = int(sys.stdin.readline()) graph = list() for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split()))) dp = [[[0] * n for _ in range(n)] for _ in range(3)] dp[0][0][1] = 1 # 방향, r, c for i in range(2, n): if graph[0][i] == 0: dp[0][0][i] = dp[0][0][i-1] # 가로 이동 for i in range(1, n): for j in range(1, n): # 현재 위치가 대각선..

날짜 : 2023. 06. 11 사용 언어 : python 문제 코드 import sys n = int(sys.stdin.readline()) con = [] for _ in range(n): con.append(list(map(int, sys.stdin.readline().split()))) # 입력 dp = [0] * (n + 1) for i in range(n-1, -1, -1): # 역순으로 진행 dp[i] = dp[i + 1] # 값 미리 받아옴 if con[i][0] + i > n: continue # 일자 초과 if dp[i + 1] < dp[i + con[i][0]] + con[i][1]: # 해당 날짜 상담 했을 때와 안했을 때 비교 dp[i] = dp[i + con[i][0]] + co..

날짜 : 2023. 06. 09 사용 언어 : python 문제 코드 import sys n = int(sys.stdin.readline()) line = list() for _ in range(n): a, b = map(int, sys.stdin.readline().split()) # 전깃줄 입력 line.append([a, b]) line.sort() # a 기준으로 정렬 # print(line) dp = [1] * n for i in range(1, n): for j in range(i): if line[i][1] > line[j][1] and dp[i] b2인 경우에 발생한다. - 그렇기 때문에 반대로 전깃줄들을 a에 대하여 오름차순으로 정렬한 후, b에 대하여 메모이제이션을 실행한다. - 즉, ..

백준 1. 가장 긴 감소하는 부분수열 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 2. 가장 긴 바이토닉 부분수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1..

날짜 : 2023. 05. 09 사용 언어 : python 문제 코드 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) # 수열 입력 up = [0] * n down = [0] * n total = [0] * n for i in range(n): # 기준 for j in range(i): # 기준값보다 작은 수 + 그 수의 인덱스의 오름차순수열 개수 최신화 if a[i] > a[j] and up[i] < up[j]: up[i] = up[j] up[i] += 1 #print(up) for i in range(n-1, -1, -1): # 기준값(역순으로 진행) for j in range(n-1, i..

날짜 : 2023. 05. 05 사용 언어 : python 문제 코드 import sys n, k = map(int, sys.stdin.readline().split()) # 동전 종류, 가치의 합 dp = [0] * (k+1) dp[0] = 1 coin = list() for _ in range(n): coin.append(int(sys.stdin.readline())) coin.sort() # 동전 정렬 for i in range(n): # 각 동전에 대하여 체크 if i == 0: for j in range(coin[0], len(dp), coin[0]): dp[j] = 1 else: for j in range(coin[i], len(dp)): dp[j] += dp[j - coin[i]] #prin..

날짜 : 2023. 04. 25 사용 언어 : python 문제 코드 import sys import itertools a = sys.stdin.readline().rstrip() b = sys.stdin.readline().rstrip() p = len(a) q = len(b) dp = [[0] * (q + 1) for _ in range(p + 1)] for i in range(1, p + 1): for j in range(1, q + 1): if a[i-1] == b[j-1]: # 같다면 dp[i][j] = dp[i-1][j-1] + 1 # 부분수열 추가= else: dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) """for i in dp: print(i)""" pri..