본문 바로가기

전체23

[ 백준 1700번 ] 멀티탭 스케줄링 파이썬 [백준 1700번 바로가기] 논리 주어진 콘센트의 개수만큼 가전기기의 종류를 채운다 다 찼을 때, 새로 들어온 것이 멀티탭 안에 없는 종류라면 어떤 것을 뽑을 지 결정 이후에 나오는 가전기기 중 가장 마지막에 등장하는 것을 뽑는다 그 가전기기를 멀티탭에서 제거하고 새로운 것을 채운다 코드 import sys from copy import copy def 멀티탭스케줄링(): # inputs N, M = map(int, sys.stdin.readline().split()) appliances = list(map(int, sys.stdin.readline().split())) curr = set() cnt = 0 for i in range(M): if len(curr) < N: curr.add(applianc.. 2021. 9. 1.
[ 백준 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.

티스토리툴바