오뚝이개발자

문제 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/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 생각의 흐름 +,-,*,//에 각각 1,2,3,4를 넘버링하여 각 연산자의 갯수만큼 리스트에 채운다. 이들의 순열을 이용하여 가능한 모든 연산의 경우의 수를 구한다. 비교하며 최솟값, 최댓값을 찾는다. 코드 from itertools import permutations N = int(input..

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2 www.acmicpc.net 생각의 흐름 주어진 수열에서 6개의 수를 고르는 것이므로 "조합"임을 파악 itertools의 combinations 메소드를 이용해 ..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 생각의 흐름 n개의 도시들을 1부터 n까지 넘버링하여 리스트에 삽입한다. 도시 리스트를 next_permutation() 함수를 이용해 가능한 모든 순열마다 input으로 주어진 weight 정보를 이용해 cost를 계산해 비교한다.(브루트포스) 이 때, weight가 ..

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 생각의 흐름 이전에 포스팅했던 모든순열의 로직을 이용해 가능한 모든 순열에 대해 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|의 값을 구한다. 주의할 점은 중복된 원소(즉, 같은 수)가 있을 수 있으므로 비교 시에 등호를 넣어주어야 한다. 위 식의 최댓값을 찾는다. 코드 def next_permutation(arr): n = len(arr)-1 i = ..

문제 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/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 생각의 흐름 다음 순열 문제의 대소비교 부분을 반대로 생각하면 된다. 코드 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] < 0:..

문제 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]..