오뚝이개발자

문제 https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 N과 M (10)과 유사하지만 중복선택을 허락하는 조합을 구하는 문제 코드 from itertools import combinations_with_replacement N,M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() result = [] result = set(result..

문제 https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 N과 M (9)과 유사하지만 중복선택을 허락하는 순열을 구하는 문제 코드 from itertools import product N,M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() result = [] result = set(result) for case in product(a..

문제 https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 N과 M (9)와 유사하지만 조합을 구한다는 점이 다르다. 코드 from itertools import combinations N,M = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() result = [] result = set(result) for case in combinati..

문제 https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 좀 많이 헤멨던 문제이다...에러 원인을 찾지 못해서... 일단 문제를 분석해보자면 리스트의 원소들을 입력으로 받아 순열을 구하는 문제인데 까다로운 부분은 원소 중에 중복되는 것들이 있다는 점이다. 다시 말해 [1,9,3,9]과 같은 리스트인데 순열을 구할 때 두 개의 9를 서로 다른 원소로 생각해 (9,9)가 두 번 나오게 되는 경우가 발생한다. 이를 해결해야 한다...

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 생각의 흐름 말 그대로 combinations를 이용해 부분수열(사실 조합이다)을 구해서 각 case마다 합을 구하고 이를 주어진 target과 비교해보면 된다. 코드 from itertools import combinations N, S = map(int, input().split()) arr = list(map(int, input().split())) ..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 생각의 흐름 구해야 하는 것이 조합임을 파악 사전순으로 출력하기 위해 정렬 최소 한 개의 모음과 두 개의 자음을 포함하는지 조건 검사해서 출력 코드 from itertools import combinations L, C = map(int, input().split()) alphabet = list(map(str, input().split())) alphabet.sort() moeum_list = ..

문제 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 생각의 흐름 처음에 리스트를 1부터 넣어 초기화해주고 이전에 포스팅했던 다음 순열의 알고리즘을 사용하면 된다 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] > arr[i]: i -= 1 if i == 0: return -1 j = i-1 diff = 10000 position_to_switch = 0 for k in range(i, n+1): if arr[k]-arr[j] > ..

문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 생각의 흐름 다음 순열을 어떻게 찾아낼까? (규칙성) 일의 자리부터 시작하여 바로 앞의 수보다 큰지 작은지를 비교하여 판별한다. 깨달은 점 사실 파이썬에는 이러한 기능을 구현해주는 permutations라는 아주 편리한 라이브러리가 있다...하지만, 구현을 해보는 데에 의의가 있으니^^ 코드 def next_permutation(arr): n = len(arr)-1 if n==0: return -1 i = n while arr[i-1] > arr[i]..