오뚝이개발자

문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 이전에 포스팅 했던 N과 M (3)과 비교했을 때 중복선택을 허락하는 것은 동일하지만 순열이 아닌 조합이라는 점이 다르다. 깨달은 점 파이썬 itertools에는 이를 지원하는, 즉 중복선택을 허락하는 조합을 구하는 combinations_with_replacement라는 함수가 있다. 코드 from itertools import combinations_with_rep..

문제 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 중복선택이 가능하다는 점을 유념해야 한다. 깨달은 점 파이썬 itertools에 product라는 함수가 있다. product(arr, repeat=M)과 같이 첫번째 인자는 리스트, 두번째 인자는 반복 횟수이다. 예컨대, arr = [1,2,3], M=2라면 (1,1)과 같이 두 개를 뽑는데 중복해서 뽑는 경우를 포함한다. 코드 from itertools import..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 간단한 문제이므로 아래의 코드로 설명을 대신하겠다. 코드 from itertools import combinations N, M = map(int, input().split()) arr = list(range(1,N+1)) for case in combinations(arr, M): print(' '.join(map(str, case)))

문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 생각의 흐름 리스트에 1부터 N까지의 수를 넣어 이들을 permutations(list, M)하면 끝! 코드 from itertools import permutations N, M = map(int, input().split()) arr = list(range(1, N+1)) for case in permutations(arr, M): print(' '.join(map(str, c..

문제 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 생각의 흐름 문제가 꽤나 직관적이다. 그냥 시키는 대로 분기를 시켜 짜면 된다. 출제의도는 아마 set을 사용하는 방법을 익히도록 하려던 것 같다. 깨달은 점 set에는 list와는 다른 점들이 몇 가지 존재한다. 코드 상에서 사용된 부분들에 대해서만 소개하고자 한다. set에는 중복이 없다. 즉, temp = [1,2,3,3]이라는 list를 temp = set(temp)를 하고나면 [1,2,3]이 된다. 하지만 순서도 없다..

문제 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 www.acmicpc.net 생각의 흐름 이전에 포스팅한 연산자 끼워넣기와의 차이점은 연산자의 갯수가 많아졌다는 점이다. 동일한 방법으로 짜도..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 생각의 흐름 무려 삼성SW역량테스트 기출문제이시다.... DP를 이용하는 문제라는 건 감을 잡았는데 알고리즘을 어떻게 적용해야 할지 떠오르지 않아 다른 분의 코드를 참고하고 이해하였다.(출처는 코드 밑단에 추가해두었다) 비용을 계산해야 하니 비용을 담을 dp list를 만든다. 그 다음 애초에 불가능한 상담들(퇴사 일자 이후까지 상담이 진행되어야 하는 경우)을 분별해내야 하는데 이는 소요일수를 담은 t list의 값을 참조해 해당 일수 만큼 상담을 진행했을 시 퇴사하는 날을 넘어버리는지를 검사한다. dp에 마지막으로 0을 app..

문제 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())) ..