CEO

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 이 문제는 각 도시에 대해 가중치가 주어질 때 모든 도시를 순회하되, 최소 값으로 순회하는 경우의 수를 찾는 문제이다. 보통 이러한 문제는 DFS를 통해 방문한 경로를 기록해두고, 가능한 경로를 모두 탐색하는 방식으로 푼다. 다른 방법으로는 1 - 2 - 4 - 3 - 1과 같은 방문 순서를 순열로 구한 후에 계산하는 방식도 있을 수 있다. 하지만 순열을 계산하고 처리하는 것은 익숙하지 않아, DFS로 ..

작년에 git action이 등장한 이후로 재미있는 프로젝트들이 등장하였다. 그중 하나는 action을 사용하여, 나의 commit 정보의 시간대를 파악하여 갱신시켜주는 I'm an early 🐤라는 프로젝트이다. I'm an early 🐤? 일찍 일어나는 습관을 가지는 사람을 의미하는 말로, 적용하고자 하는 프로젝트 말고도 다양한 곳에서 널리 사용되고 있는 말이다. git의 productive-box를 fork하고 gist 생성 후 action을 지정하는 것으로 적용할 수 있다. 적용하게 되면 위의 그림과 같이 하루에 한 번 cron을 통해 주기적으로 나의 commit 정보와 시간대를 가져와 갱신해주게 되며, 이를 pinned 한다면 나의 git profile에서 바로 만날 수 있다. 적용 방법 적용 ..

문제 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)의 문제들은 원소가..