kwan's note

난이도: 골드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..

난이도: 실버2 번호:9633번 그래프의 DFS BFS탐색에 관한 문제이다. DFS와 BFS의 정의를 알고 구현할 수 있으면 쉽게 풀 수 있는데 bfs를 처음 풀어봐서 왜 queue를 이용해야 하는지 몰라서 오래걸렸다. from sys import stdin import time as t s=t.time() def dfs(node): print(node, end=' ') visitdfs[node] = 1 for i in range(1,N+1): if visitdfs[i] == 0 and matrixmap[node][i] == 1: dfs(i) def bfs(node): tovisit =[node] visitbfs[node]=1 while tovisit: node=tovisit[0] print(tovisi..

난이도: 골드5 번호:9633번 백트래킹문제로 python3는 시간을 만족시키지 못해 pypy3로 제출하여 통과하였다. row를 기준으로 한줄씩 내려가면서 모든 column에 숫자를 넣을 수 있는지 체크하면서 풀어내려갔다. from sys import stdin def queendfs(row): global count if (row==N): count +=1 return for j in range(N): checkpoint = True for n in range(len(queenlist)): if queenlist[n][1] == j or abs(queenlist[n][0] - row) - abs(queenlist[n][1] - j) == 0: checkpoint=False break if checkpo..

문제번호:15651 난이도: 실버3 간단한 dfs 백트래킹 문제이다. 1번의 쉬운버전(check 필요 없음)이다. checklist를 제거하고 동일하게 작성하였다 from sys import stdin def dfs(cnt): if(cnt==M): print(*answer) return for i in range(N): checklist[i]=True answer.append(numlist[i]) dfs(cnt+1) answer.pop() if __name__ == '__main__': N,M= map(int,stdin.readline().split()) numlist = [i+1 for i in range(N)] answer=[] dfs(0)

문제번호:15650 난이도: 실버3 기존 1번문제에서 reminder-by-kwan.tistory.com/47 길이가 이전숫자보다 새로 들어오는 숫자가 커야한다는 조건을 추가하였다 백준-15649번 N과 M (1) 파이썬 (python code) 문제번호:15649 난이도: 실버3 간단한 dfs 백트래킹 문제이다. 삼성 sds 동계알고리즘 특강을 들으며 dfs문제 이해가 오래걸려 기본문제부터 풀어보게 되었다. from sys import stdin def dfs(cnt): if(cnt==M):.. reminder-by-kwan.tistory.com from sys import stdin def dfs(cnt): if cnt == M: print(*answer) return for i in range(N)..