시나위

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 우선순위큐를 사용해서 해결할수 있었다. # import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(N): visit = [[False for _ in range(N)] for _ in range(N)] h = [(0, 0, 0)] # cost, r, c d = [(0, 1), (1, 0), (-1..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 원형배열에서 동적계획법을 사용하는 문제이다. 첫번째집에 색깔을 고정시켜놓고 구했다. import sys; input = sys.stdin.readline N = int(input()) INF = 2_000_000 rgb = [list(map(int, input().split())) for _ in range(N)] memo = [[0 for _ in range(3)] ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 언제 풀었는지 모르는 문제지만 새롭게 풀었다. 푸는 방식은 deque같은 자료구조를 사용하지 않고 배열로만 접근해서 풀었는데, start와 end 인덱스, 순회방향을 변수로 R일땐 순회 방향만 바꾸고, D일땐 순회 방향에 맞는 맨 앞에있는 원소를 제거했다. 그외엔 어려운게 없었고 입출력은 C++이라 조금 귀찮은 작업이었다. 파이썬이라면 입출력이 조금 쉬웠을것이다. #include #include // stoi, to_string using namespa..

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/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 동적 계획법을 사용한 문제인데 어떻게 짜야할지 막막했다. 그래서 구글링으로 LCS에 대해서 찾아보았고, 도움받은 것을 바탕으로 코드를 작성했다. 맨 아래 참고 블로그를 확인하자 a, b = input(), input() c, r = len(a), len(b) t = [[0 for _ in range(c + 1)] for _ in range(r + 1)]..

www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 어제 완전 탐색으로 만드는 조합을 공부하다가 비트마스크를 까먹고 있었다는 것을 깨달았다. 그래서 비트마스크 관련 문제를 풀어보기로 마음먹었다. 백준 동적 계획법 3에서 제일 쉬운 문제인데 이전에 풀었던 문제였다. 하지만 7개월이 지나기도 했고, 문제도 생각이 안났기때문에 바로 풀었다. 더보기 https://sinawi.tistory.com/284 [백준] 11723 집합 C www.acmicpc.net/problem/11723 11723번: 집합..

https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 재료 중 몇개를 선택해서 영양분 각각 일정 이상이 되어야 하고 비용이 최소가 되어야한다. N의 최대값이 15이므로 2^15 = 32768 이므로 완전탐색으로 모든 조합을 만들기로 판단했다.매번 리스트에 추가해서 내려보내는 방식으로 구현했다. import sys; input = sys.stdin.readline def list_chk(lst, goal, foods): # 최저 영양소 기준을 만족하..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 그냥 대충 보면 완전탐색인것처럼 보이지만 N=100000이므로 DP 문제이다. 2행의 배열이 주어졌을때 구할수 있는 최대값을 찾는 문제이다. T = int(input()) for tc in range(T): N = int(input()) sticker = [list(map(int, input().split())) for _ in range(2)] memo = [[0 for _ in ra..