제목 미정
15649 N과 M
자연수 N과 M이 주어졌을 때 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 고르는 문제
-
풀이
순열 개념을 익히기 위한 기초 문제입니다.
백트래킹 방식을 활용하여 풀거나, 내장함수인 순열을 이용할 수 있습니다. -
내장함수를 이용한 풀이
from itertools import permutations
import sys
input = sys.stdin.readline
a = []
n, m = map(int, input().split())
result = map(lambda x: ' '.join(map(str, x)), permutation(range(1, n + 1), m))
for x in result:
print(x)- 백트래킹(재귀)
import sys
input = sys.stdin.readline
def back_trk():
if m == len(a):
print(" ".join(map(str, a)))
return
for i in range(1, n + 1):
if i no in a:
a.append(i)
back_trk()
a.pop()
a = []
n, m = map(int, input().split())
back_trk()lambda 함수를 활용해서 result값을 저장하는 방식과 join 함수를 활용하지 못했습니다.
2309 일곱 난쟁이
아홉 개의 난쟁이 키가 주어질 때, 일곱 난쟁이의 합이 100이 되는 난쟁이들의 키를 오름차순으로 출력하는 문제
- 세 가지 풀이가 있습니다.
- 전체의 합에서 두 난쟁이의 합을 제외한 값이 100인 경우를 이중 반복문을 통해 찾아내는 방법입니다.
- 내장함수인 조합(combinations) 함수를 사용하는 방법
- 백트래킹을 이용하는 방법이 있습니다.
- 이중 반복문
arr = []
for _ in range(9):
dwf = int(input())
arr.append(dwf)
arr.sort()
sum = sum(arr)
fake = []
for i in range(9):
for j in range(i+1, 9):
if(len(fake) == 2):
break
if sum - arr[i] - arr[j] == 100:
fake.append(arr[i])
fake.append(arr[j])
for i in arr:
if i in fake:
continue
print(i)- 조합을 활용하는 방법
from itertools import combinations
arr = []
for _ in range(9):
dwf = int(input())
arr.append(dwf)
arr.sort()
for i in combinations(arr, 7):
if sum(i) == 100:
for j in sorted(i):
print(j)
break- 백트래킹(재귀)를 활용한 방법
dwf = [int(input()) for _ in range(9)]
seven = []
def dfs(depth, start):
if depth == 7:
if sum(seven) == 100:
for j in sorted(seven):
print(j)
exit()
else:
return
for i in range(start, len(dwf)):
seven.append(dwf[i])
dfs(depth + 1, i + 1)
seven.pop()
dfs(0, 0)전형적인 조합 문제이다.
풀이 1.처럼 일곱 난쟁이 중 합이 100이 되는 난쟁이를 고르기보다, 전체에서 두 난쟁이의 합을 빼는 방식처럼 거꾸로 생각하는 것이 참신했습니다.
풀이 3.의 재귀방식은 아직 익숙하지 않습니다. 그러나 이 방식은 순열의 기본적인 아이디어라서, 관련된 문제 하나 더 추가하겠습니다.
10974 모든 순열
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 문제
- 순열을 구현한 그 자체입니다. 오리지널이랄까..
list = [1,2,3,4,5]
used = [0] * len(list)
def perm(arr, n):
if n == len(list):
print(arr)
return
for i in range(len(list)):
if not used[i]:
used[i] = 1
arr.append(list[i])
perm(arr, n+1)
arr.pop()
used[i] = 0
perm([], 0)1181 단어 정렬
알파벳 소문자로 이루어진 N개의 단어가 입력됐을 때
1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 3. 중복된 단어는 하나만 남기고 제거하여 출력하는 문제입니다.
중복을 허용하지 않는 세트의 특성을 이용해 중복을 제거할 수 있으며, sort()함수의 key값을 길이로 설정하여 풉니다.
n = int(input())
words = [str(input()) for i in range(n)]
words = list(set(words))
words.sort()
words.sort(key=len)
for i in words:
print(i)1182 부분수열의 합
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제
- 변수 arr는 맵핑하여 리스트로 저장합니다. combinations()함수를 이용하면 객체를 반환하는데, 이 객체는 iter이기 때문에 리스트나 튜플로 변환하거나 for문으로 추출하여 원소를 사용할 수 있습니다. sum(x)로 합을 구하여 그 합과 더한 값이 같으면 count를 셉니다. 여기서 cnt는 지역변수이기 때문에, cnt를 배열로 선언해서 0번째 요소에 1씩 더하는 식으로 카운트 값을 올려줍니다.
문법 정리
sort()와 sorted() 함수
리스트를 제자리에서 수정합니다. list.sort() 메서드는 리스트에게만 정의되지만, sorted() 함수는 모든 이터러블을 받아들입니다.
sorted([5,2,3,1,4]) [1, 2, 3, 4, 5] a = [5,2,3,1,4] a.sort() a [1, 2, 3, 4, 5] sorted({1: 'D', 2: 'B', 3: 'B', 4:'E'}) [1, 2, 3, 4]
list.sort()와 sorted()는 모두 비교하기 전에 각 리스트 요소에 대해 호출할 함수를 지정하는 key 매개 변수를 가지고 있습니다. key 매개 변수의 값은 단일 인자를 취하고 정렬 목적으로 사용할 키를 반환하는 함수(또는 다른 callable)이어야 합니다. 키 함수가 각 입력레코드에 대해 정확히 한 번 호출되기 때문에 이 기법은 빠릅니다.
sorted(student_tuple, key=lambda student: student[2]) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] sorted(student_tuple, reverse=True) [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
class Student:
def init(self, name, grade, age):
self.name = name
self.grade = grade
self.age = age
def repr(self):
return repr((self.name, self.grade, self.age))
student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
sorted(student_objects, key = lambda student: student.age)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
list.sort()와 sorted()는 모두 불리언 값을 갖는 reverse 매개 변수를 받아들입니다. 이러한 정렬은 안정적임이 보장됩니다. 여러 레코드가 같은 키를 가질 때, 원래의 순서가 유지됩니다.
이 멋진 속성은 일련의 정렬 단계로 복잡한 정렬을 만들 수 있도록합니다!
필드와 순서의 튜플 리스트를 받을 수 있는 래퍼 함수로 추상화 할수도 있습니다.
> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
> s = sorted(student_objects, key=attrgetter('age'))
> sorted(s, key=attrgetter('grade'), reverse=True)
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
def multisort(xs, specs):
for key, reverse in reversed(specs):
xs.sort(key=attrgetter(key), reverse=reverse)
return xs
> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]permutations(), combinations() 함수
permutations() 함수는 iterable에서 요소의 연속된 길이 r 순열을 반환합니다. r이 지정되지 않았거나 None이면, r의 기본값은 iterable의 길이이며 가능한 모든 최대 길이 순열이 생성됩니다.
반환되는 항목 수는 0 <= r <= n일 때는 n! / (n - r)!이고 r > n일 때는 0입니다.
combinations()는 입력 iterable에서 요소의 길이 r 서브 시퀀스를 반환합니다. 반환되는 항목 수는 0 <= r <= n일 때는 n! / r! / (n-r)!이고 r > n일 때는 0입니다.
lambda 함수
lambda 키워드를 사용해서 작고 이름없는 함수를 만들 수 있습니다. 이 함수는 두 인자의 합을 돌려줍니다. lambda a, b: a+b. 함수 객체가 있어야 하는 곳이면 어디나 람다 함수가 사용될 수 있습니다. 문법적으로는 하나의 표현식으로 제한됩니다. 의미적으로는, 일반적인 함수 정의의 편의 문법일 뿐입니다. 중첩된 함수 정의처럼, 람다 함수는 둘러싸는 스코프에 있는 변수들을 참조할 수 있습니다.. 또 다른 용도는 작은 함수를 인자로 전달합니다.
> def make_incrementor(n):
return lambda x: x + n
> f = make_incrementor(42)
> f(0)
42
> f(1)
43
> pairs = [(1, 'one'), (2, 'two'), (3, 'three'), (4, 'four')]
> pairs.sort(key=lambda pair: pair[1])
> pairs
[(4, 'four'), (1, 'one'), (3, 'three'), (2, 'two')]set 구조체
집합은 중복되는 요소가 없는 순서 없는 컬렉션입니다. 기본적인 용도는 멤버십 검사와 중복 엔트리 제거입니다. 집합 객체는 합집합, 교집합, 차집합과 같은 수학적인 연산들도 지원합니다.
집합을 만들 때는 중괄호나 set() 함수를 사용할 수 있습니다. (주의) 빈 집합을 만드려면 set()을 사용해야 합니다.a = set('abracadabra') b = set('alacazam') a {'r', 'd', 'c', 'a', 'b'} a - b {'b', 'd', 'r'} a | b {'l', 'r', 'z', 'b', 'c', 'm', 'a', 'd'} a & b {'a', 'c'} a ^ b # letters in a or b but not both {'l', 'z', 'r', 'm', 'b', 'd'} a = {x for x in 'abracadabra' if x not in 'abc'} a {'d', 'r'}
