본문 바로가기

dev22

[ 백준 12865번 ] 아주 평범한 배낭 파이썬 [백준 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 논리 배낭의 한계 무게에서 가질 수 있는 물건들의 가치의 최대값 각 무게마다의 최대 가치를 가지는 table을 만든다(table[i]: i무게에서 가질 수 있는 최대값) 각 물건마다 table[i]에 들어가는 경우를 생각해보고 가치의 최댓값을 갱신한다 ex) 한 물건으 무게가 w, 가치가 v라고 할 때, table[i]에서 이 물건을 고려해보자 --> i무게에서 w만큼.. 2021. 9. 1.
[ 백준 11049번 ] 행렬 곱셈 순서 파이썬 [백준 11049번 바로가기] 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 손글씨로 설명을 대체합니다 논리 점화식 동작 순서 예시 코드 import sys def minimum_matrix_operation(): # inputs N = int(sys.stdin.readline()) matrices = [None] * N for i in range(N): matrices[i] = list(map(int, sys.stdin.readline().split())) # table[i][j]: i-th-M.. 2021. 9. 1.
[ 백준 9251번 ] LCS 파이썬 [백준 9251번 바로가기] 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 논리 두 문자열 s1, s2의 끝자리가 같다면 lcs(s1, s2)는 lcs(s1[:-1], s2[:-1]) + 1과 같다 (마지막 문자가 같으므로 이를 제외한 것들의 lcs에서 1을 더함) 두 문자열 sl, s2의 끝자리가 다르다면 lcs(s1, s2)는 lcs(s1, s2[:-1])과 lcs(s1[:-1], s2) 중 큰 값을 취한다 공통 문자열을 확인하고 싶다면 lcs_table을 거.. 2021. 9. 1.
[ 백준 11053번 ] 가장 긴 증가하는 부분 수열(LIS) 파이썬 [백준 11053번 바로가기] 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 논리 주어진 문자열을 seq라고 할 때 seq[i]까지의 lis[i]를 기록해놓는다 i < j 인 seq[j]로 끝나는 lis 길이를 알기 위해 이전까지의 lis[i](i < j)를 참고한다 이때, seq[i] < seq[j]라면 lis[j] = max(lis[j], lis[i]+1)로 계속 갱신한다 코드 import sys def LIS(): # inpu.. 2021. 9. 1.

티스토리툴바