[Algorithm] 이코테 만들 수 없는 금액 | 파이썬 (그리디)
[문제]동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. [입력 조건]첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1≤N≤1,000)둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다..
2024. 6. 24.
[Algorithm] 파이썬 정렬, lambda 사용
우선 파이썬에서 sort()와 sorted() 함수를 통해 정렬을 할 수 있다.sort() 원본 자체를 정렬시켜 준다.a = [1,5,2,7]a.sort() print(a)#a = [1,2,5,7] sorted() 원본을 변형시키지 않고 새로운 list를 반환한다.a = [1,5,2,7]b = sorted(a)print(a)print(b)#a = [1,5,2,7]#b = [1,2,5,7] reverse 정렬 기능은 기본적으로 오름차순으로 제공한다. 내림차순으로 정렬하고 싶은 경우, reverse 파라미터를 통해 정렬할 수 있다.a = [1,5,2,7]a.sort(reverse=True)print(a)#a = [7,5,2,1] key 정렬 조건을 설정할 함수를 넣을 수 있다.a = ['love','i','..
2024. 6. 20.
[Algorithm] Backtracking(백트래킹) 순열 및 조합 구현하기 itertools
우선 순열과 조합의 차이를 알아보자. 순열 : 원소들의 순서를 고려하여 나열하는 것 (원소의 순서가 다르면 다른 순열로 취급) 조합 : 원소들의 순서를 고려하지 않고 나열하는 것 (선택된 원소의 순서는 고려되지 않음) 파이썬 라이브러리 중 하나인 itertools를 사용하면 조합과 순열을 쉽게 구할 수 있다. from itertools import permutations, combinations arr = [1,2,3] k = 2 npr = list(permutations(arr, 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] ncr = list(combinations(arr, 2)) # [(1, 2), (1, 3), (2, 3)] 그러나.. 라이브러리..
2024. 4. 13.
