전체 글

[백준12865&파이썬] 0-1 냅색문제(배낭문제)

# 문제 백준 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 # 코드 import sys def print2D(arr) : for i in arr : print(i) return N,K = map(int,sys.stdin.readline().split()) arr = list() for _ in range(N) : weight, value = map(int,sys.stdin.readline().split())..

[백준11054&파이썬] dp를 두번 이용하여 문제를 해결하자

# 문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net # 코드 import sys n = int(sys.stdin.readline().strip()) arr = list(map(int,sys.stdin.readline().split())) # print(arr) # 왼쪽부터 증가하는 수열을 구한다. dpL = [1] * n for pivot in range(n) : for i in range(pivot) : if arr[i] < arr[pivot] : dpL[pivot] = max(dpL[pivot], dpL[i] + 1) #..

[Object Oriented S/E] Chapter 10 - Object Interaction Modeling

# 범위 251 page ~ # 내용 ## 10.1 WHAT ARE DESIG PATTERNS? [10.1 디자인 패턴은 자주 만나게 되는 설계 문제에 대한 해결책의 추상화이다] 디자인 패턴을 통해서 비슷한 디자인 문제를 해결할 수 있다. ## 10.2 WHY DESIGN PATTERNS? 패턴은 재사용 가능한 요소이다. 패턴을 결합하여 크고 복잡한 디자인 문제를 해결 할 수 있다. 패턴은 팀 구성원간의 의사소통을 향상시킨다. 패턴은 소프트웨어 시스템의 동작과 구조를 증가시킨다. 결과적으로 패턴은 소프트웨어의 생산성과 퀄리티를 향성시키며, COST와 TIME을 감소시킨다. ## 10.3 SITUATION-SPECIFIC AND RESPONSIBILITY-ASSIGNMENT PATTERNS 두개이상의 패턴..

[백준11053&파이썬] DP를 이용하여 반복문을 하나 줄일 수 있다.

# 문제 백준11053 가장 긴 증가하는 부분 수열 파이썬 풀이 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net # 코드 ''' - 수열의 크기 N이 최대 1,000이기 때문에 O(N^2)을 이용한 완전탐색을 하더라도 1,000,000 ( 약 백만 ) 안에 구할 수 있기 때문에 1초안에 구할 수 있을 것으로 보인다. ''' import sys N = int(sys.stdin.readline().strip()) arr = list(ma..

[백준2096&파이썬] DP와 슬라이딩 윈도우를 이용하기

# 문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 코드 import sys N = int(sys.stdin.readline().strip()) mmin = [0,0,0] mmax = [0,0,0] for _ in range(N): cur = list(map(int, sys.stdin.readline().split())) mmin = [cur[0] + min(mmin[:2]) , cur[1] + min(mmin), cur[2] + min(mmin[1:])] mmax = [cur[0] + max(mmax[:2]) ,..