냅색(Knapsack)알고리즘(배낭 문제)
1. 분할 가능한 배낭 문제 도둑이 열린 상자에 든 금괴를 훔쳐가려고 한다 도둑이 가지고 있는 배낭에 담을 수 있는 총무게가 15kg이고 금괴가 든 상자는 a상자가 12kg, b상자가 1kg, c상자가 4kg, d상자가 1kg, e상자가 2kg이 있다 a, b, c, d 상자의 가치가 각각 $4, $2, $1, $10, $2라고 할 때 도둑이 배낭에 담을 수 있는 최적의 조합은 a 7kg, c 4kg, b 1kg, e 2kg, d 1kg이 된다 - 그리디로 해결 def knapsack1(W, w, p): n = len(w) - 1 # 아이템 개수 K = [0] * (n + 1) # 최대 가치를 저장할 배열 weight = 0 # 현재 무게 for i in range(1, n + 1): weight += ..
2023. 6. 14.
백준 14225 - 부분수열의 합
문제 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 접근 - 입력된 수열을 정렬한 후에 순서대로 처리 - 변수 a는 현재까지의 부분합 - 반복문을 통해 수열을 순회하면서 a에 현재 수를 더하기 - 만약, 현재까지의 부분합에 1을 더한 값보다 현재 수가 크면 반복문을 중단 - 이때, 중단되는 시점에서의 a값은 부분합 중 가장 작은 자연수 - a + 1을 출력하여 문제의 답 출력 코드 # 입력 받기 input() a = 0 # 부분합을 저장할 변..
2023. 6. 13.
프로그래머스 - 카운트 다운 파이썬
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 정리 용어 정리 - 카운트 다운 = 무작위로 정해진 점수를 다트로 깎아서 0점을 만드는 게임 - 점수 설명 싱글 - 해당 수 만큼 점수 얻음(1,2,3....20까지의 점수) 더블 - 해당 수 두 배 만큼 점수 얻음(2,4,6...40까지의 점수) 트리플 - 해당 수 세 배 만큼 점수 얻음(3,6,9....60까지의 점수) 불, 아우터 불 - 50점 얻음 경기 정리 - 한줄 정리: 빨리 0점 만들기, 같으면 '싱글', '불' 최대한 많이 던지기 - 한 게임에는 두 선수 참가 - 교대로 한 번씩 던지..
2023. 5. 17.
