시나위

https://www.acmicpc.net/problem/13902 13902번: 개업 2 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 문제 자체는 어렵진 않으나 시간초과의 벽이 조금 있었다. 이 문제를 풀기위해서 동적계획법을 사용해야한다. 최대 두개의 웍을 사용해서 처리할 수 있는 양을 구해야하는데 set이라는 자료구조를 사용했다. 두개로 처리할수 있는 양을 동적 계획하여 0부터 N번째 양까지 계산하면 된다. import sys; input = sys.stdin.readline N, M = map(int, input().split())..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동적 계획법은 볼때마다 새롭다. 요즘 계속 풀던 문제가 완전 탐색이었기 때문에 조금 더 오래 걸린 듯하다. 1, 5, 10 등 흔히 사용하는 동전만 나온다면 그리디 알고리즘으로 하는게 낫지만, 그렇지 않은 경우 동적 계획법을 사용해서 풀어야한다. 예를 들면 동전이 1, 4, 5이 있고 12원을 만들어야하는 경우 그리디 알고리즘으로 풀면 4개의 동전(5*2 + 1*2)이 필요하다. ..

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/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/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)]..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr def solution(triangle): dp = [[0] * i for i in range(1, len(triangle) + 1)] dp[0][0] = triangle[0][0] for i in range(1, len(dp)): for j in range(len(dp[i])): if j == 0: dp[i][j] = triangle[i][j] + dp[i - 1][j] elif j == len(dp[i]) - 1: dp[i][j] = triangl..

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net import sys input = sys.stdin.readline n, m = map(int, input().split()) n_list = list(map(int, input().split())) m_list = [] for _ in range(m): m_list.append(tuple(map(int, input().split()))) for m_tmp in m_list: print(..