kwan's note

난이도: 실버2 번호: 1931번 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이중배열도 키를 지정해서 sort할 수 있는지 몰라서 직접sorting을 해야하는줄 알고 조금 헤맸는데 sort(key= lambda x:x[n])으로 n번째 index에 대해 sort할 수 있어서 이를 사용했다. 또한 파이썬의 sort함수는 안정성을 만족하므로 table.sort(key=lambda a: a[0]) table.sort(key=lambda a: a[1]) 를 이용하면 idx 1을 기준으로 오름차순 정렬하되 같으면 ..

난이도: 골드5 번호: 9251번 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 글자의 부분수열이 되는 가장 긴 수열을 찾는 문제이다. 예시는 다음과 같다. 예시1) ACAYKP CAPCAK -------- ACAK 예시2) ABCDE CKA ------- C 예시3) AAAAABCCO FABORITE ------------ ABO DP로 문제를..

난이도: 실버2 번호: 11053번 이번 문제는 가장 긴 증가하는 부분수열 LIS를 계산하는 문제이다. www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 부분수열은 수열중에서 오름차순으로 뽑을 수 있는 수열중 최대 길이를 갖는 수열으로 예시1) 10 20 10 30 20 50 에서 10 20 30 50으로 4 예시2) 10 30 20 30 40 50 80 60 70에서 10..

난이도: 실버1 번호: 1149번 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 문제인데 이것도 그리디한 방식으로 접근했다가 다시 돌아왔다. 다이나믹프로그래밍이 아직 익숙하지 않은것같다. 각 줄에 대해 최소합으로 최신화시키면서 나아가고 마지막에 min을 취해 결과값을 얻었다. from sys import stdin N = int(stdin.readline().rstrip()) paint=[0]*N for i in range(0,N..

난이도: 골드5 번호: 12865번 가장 평범한 dp 문제중 하나인 냅색 knapsack 문제이다. 그리디하게 풀려다가 안돼서 찾아보니 점화식을 이용한 다이나믹프로그래밍 문제인걸 알게되었다. 그래서 금방 풀줄 알았는데 너무 오래걸렸다. 중간에 작성한 오답코드 from sys import stdin N, K = map(int,stdin.readline().split()) WV=[0]*(N+1) for i in range(1,N+1): WV[i] = list(map(int,stdin.readline().split())) knapsack=[[0]*(K+1)]*(N+1) for i in range(1,N+1): for j in range(1,K+1): knapsack[i][j]=max(knapsack[i-1][..

난이도: 실버3 번호: 1003번 동적할당을 통해 피보나치수열을 빠르게 계산하는 문제이다. 시간이 0.25초로 매우 짧아서 실제 이론적 피보나치 수열을 구현하면 시간초과에 걸린다. 시간초과 코드: (피보나치 준 구현) from sys import stdin def check(num): global answer0, answer1 if num==0: answer0 +=1 return elif num==1: answer1 +=1 return else: check(num-1) check(num-2) T = int(stdin.readline().rstrip()) case=[int(stdin.readline().rstrip()) for _ in range(T)] for i in range(T): answer0, a..

난이도: 실버1 번호: 11047번 그리디알고리즘 문제라기 보단 가벼운 수학문제에 가까운 문제였다. K원을 만드는 최소동전에 관한 문제였는데 각 동전이 배수관계여서 고려할 요소가 많지 않았다. 처음에는 그냥 naive하게 하나씩 뺐는데 python3는 통과못하고 pypy3만 통과해서 나눗셈으로 풀었더니 시간이 많이 단축됐다. www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 처음풀이(pypy3만 ..

난이도: 실버1 번호: 7576번 처음에는 매번 모든 행과열의 데이터를 확인해서 1이면 확장하는 방식으로 만들었는데 시간초과가 발생했다. 초기작성코드(시간초과) from sys import stdin from copy import deepcopy def tomato(): day = 0 prev= [0] while( any(0 in tomatobox[i] for i in range(M)) and prev != tomatobox): prev = deepcopy(tomatobox) q=[] for m in range(M): for n in range(N): if tomatobox[m][n]== 1: if m < M - 1 and tomatobox[m + 1][n] == 0: q.append([m+1,n]) i..