시나위

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 비트마스크를 사용한 조합문제이다. dp를 사용하지 않았고 비트마스크를 사용해서 모든 부분 수열의 합을 구했다. def main(): N, S = map(int, input().split()) seq = list(map(int, input().split())) answer = 0 for select in range(1, 1

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크와 동적 계획법을 사용해서 최소비용을 구하는 문제이다. 2차원 배열을 사용해서 푸는데, 상태는 지금까지 선택한 것들을 넣으면 되지만 row 값을 고르는게 오래걸렸다. 이전 값을 넣어야할지 현재 값을 넣어야할지 막막해서 결국 찾아보았고 현재 방문한 도시 번호를 넣는 걸로 하게 되었다. (이건 다른 문제를 더 많이 풀어보면서 감을 익혀야할거같다.) 알고리..

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 어제와 이어서 비트마스크를 사용한 동적 계획법을 공부했다. 문제만 보면 모든 조합 만들어서 최솟값을 찾으면 된다. 그러면 완전탐색이나 백트래킹을 사용해서 탐색을 하면 모든 조합을 찾을수있다. 하지만 N의 최댓값이 20이므로 20^20 이나 20!은 매우 큰 숫자이므로 다른 방법을 찾아야한다. 완전 탐색을 하다보면 항상 겹치는 부분이 생기게 되는데 이때의 값들을 저장하고 일반적인 값을..

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net import sys; input = sys.stdin.readline n = int(input()) coin = [[False] * n for _ in range(n)] cnt = 401 # 최대값이 20*20 /2 인데 그냥 계산하기 편하게 400 + 1 # head: 0, tail: 1 for i in range(n): tmp = input() for j in range(n): if tmp..