CEO

문제 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 문제 풀이 집합이 주어지면 로또의 경우 6개의 수를 뽑기 때문에 6개의 수를 선택할 수 있는 경우의 수를 선택하는 문제이다. 예제 출력을 보면, 6개를 선택할 수 있는 조합을 찾는다는 것을 알 수 있다. 앞서 다룬 N과 M 시리즈와 동일한 방식으로 조합을 구하면 된다. 코드 DFS를 사용한 문제 풀이 from sys import stdin def dfs(idx, depth): global answer if depth == 6: answer..

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 풀이 앞의 10974 모든 순열에서 특정 수가 주어지는 경우로 변경된 문제이다. 이 역시 DFS를 통해 순열을 구하는 법을 알고 있다면 쉽게 풀 수 있다. 입력되는 값들은 정렬된 상태가 아니므로, DFS를 통해 경우의 수를 구하기 전에 정렬이 필요하다. 코드 DFS를 사용한 문제 풀이 from sys import stdin def dfs(depth): global answer if depth == n: answer.append([nums[i] for i in chec..

문제 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 N이 주어지면 1부터 N까지의 수 중에 N의 길이에 해당하는 순열을 찾는 문제이다. 앞서 푼 N과 M 시리즈를 통해 순열을 구하는 법을 알고 있으므로 이 문제는 쉽게 풀 수 있다. 코드 from sys import stdin def dfs(depth): global answer if depth == n: answer.append([num for num in check]) else: for i in range(n): if i + 1 in check: continue check[depth] = i + 1 dfs(depth + 1) check..

문제 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 앞서 푼 10972 다음 순열에 대한 로직을 이해하고 있다면, 부등호 방향만 바꿔주면 쉽게 해결 할 수 있다는 것을 알 수 있다. 코드 from sys import stdin def prev_permutation(lst): length = len(lst) - 1 i, j, k = [length for _ in range(3)] while i > 0 and lst[i - 1]

문제 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 이 문제는 특정 순열이 주어 질 때 다음 순열을 찾는 문제이다. c++의 경우 stl에 next permuation이 있기에 쉽게 풀 수 있지만, 파이썬의 경우 직접 구현하여야 한다. 따라서 파이썬으로 풀게 되면 단순히 라이브러리를 사용하는 것이 아닌 어떤식으로 동작하는지 알 수 있다. 예시의 경우 주어진 순열은 1, 2, 3, 4로 해당 순열의 다음 순열은 1, 2, 4, 3이다. 모든 순열을 나열하고 다음 순열을 찾는것은 비효율적이다. 따라서 그림과 같은 방식을 통해 보다 효율적으로 다음 순열을 찾을 수..

N과 M 시리즈 원소가 1에서 N인 경우 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 원소가 주어지는 경우 N과 M (5 ~ 8) N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다. 중복 원소가 존재하는 경우 15663 N과 M (9) N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다. 문제 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 N과 M (1 - 8)의 문제들은 원소가..

N과 M 시리즈 원소가 1에서 N인 경우 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 원소가 주어지는 경우 N과 M (5 ~ 8) N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다. 중복 원소가 존재하는 경우 15663 N과 M (9) N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다. 문제 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 앞서 푼 문제 중 15650 N과 M (..

N과 M 시리즈 원소가 1에서 N인 경우 15649 N과 M (1) 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 원소가 주어지는 경우 N과 M (5 ~ 8) N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다. 중복 원소가 존재하는 경우 15663 N과 M (9) N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다. 문제 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 앞서 풀이 한 15649 N과 M (1)..