RUBY

출처:: 2018 E기업 알고리즘 대회 분류:: 그리디 1. 문제 이해 및 해결과정 1. DFS 풀이 - DFS N-1로 연산 하는 경우 N/K로 연산하는 경우 로 두가지 가지 중 최소값을 생각했다 - 단 , 이 방법은 n이 100000이라면 overflow가 난다. 2. 그리디 풀이 - k로 최대한 많이 나누는 것이 최적의 해를 보장하는 것 2. 풀이방법 1. DFS(n이 작을 때만 가능한 풀이) #1이 될 때까지 # import sys sys.stdin = open("input.txt","r") n,k=map(int,input().split()) sys.setrecursionlimit(10**6) candi=[] def DFS(x,cnt): if x==1: candi.append(cnt) return..

출처:: 2019 국가 교육기관 코딩 테스크 분류:: 그리디 1. 문제 이해 및 해결과정 - 행마다 가장작은 수 뽑고 그 중에서 제일 큰 수 찾기 - 입력1 3 3 3 1 2 4 1 4 2 2 2 - 출력1 2 - 입력2 2 4 7 3 1 8 3 3 3 4 - 출력2 3 2. 풀이방법 1. 2중 for문 #숫자 카드 게임 # import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) li=[map(int,input().split()) for _ in range(n)] candi=[] for x in li: small = 2147000000 for k in x: small=min(k,small) candi.append(small) p..

출처:: 2019년 국가 교육기관 코딩테스트 분류:: 그리디 1. 문제 이해 및 해결과정 1번 풀이 - 가장 큰 수와 그 다음 큰 수 저장해놓고 - k가 될때까지는 큰 수 더하고 그 다음 큰 수 더하고를 반복한다 2번 풀이. 반복되는 수열에 대해서 파악하기 - ex) 5 8 3 /n 2 4 5 4 6일때 6 6 6 5 / 6 6 6 5 반복 - m//(k+1) 8//4 => 2, 2는 수열의 반복 횟수 2*k= 전체에서 가장큰 수가 몇번 나오는지 - m%(k+1) => 수열이 딱 안나누어 떨어질 경우 추가 되는 가장 큰 수의 개수 => sum = m//(k+1)*k + m%(k+1) 2. 풀이방법 - 1. 그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 import sys sys.stdin =..

출처:: https://www.acmicpc.net/problem/15990 1. 문제 이해 및 해결과정 - dp 2차원 배열로 풀어야 한다. # 1은 하나 작은 수에서 2로 끝나는 것과 3으로 끝나는 것에 붙일 수 있음 dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % d # 2는 둘 작은 수에서 1로 끝나는 것과 3으로 끝나는 것에 붙일 수 있음 dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % d # 3는 셋 작은 수에서 1로 끝나는 것과 2으로 끝나는 것에 붙일 수 있음 dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % d 2. 풀이방법 1. DP #1, 2, 3 더하기 5 #https://www.acmicpc.net..

출처:: https://www.acmicpc.net/problem/15988 1. 문제 이해 및 해결과정 - 1,2,3 더하기 에서 범위가 바뀐 문제이다. - 중간에 %100000~9 를 안해주면 메모리 초과가 난다. 2. 풀이방법 1. DP #1, 2, 3 더하기 3 #https://www.acmicpc.net/problem/15988 import sys t=int(input()) for _ in range(t): n=int(input()) dp=[0]*1000002 dp[1] = 1 dp[2] = 2 dp[3] = 4 if n>=4: for i in range(4,n+1): dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000009 print(dp[n]%1000000009) 2. D..

출처:: https://www.acmicpc.net/problem/11727 분류:: dp 1. 문제 이해 및 해결과정 2. 풀이방법 1.DP #2×n 타일링 2 #https://www.acmicpc.net/problem/11727 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*1001 dp[1]=1 dp[2]=3 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2]*2 print(dp[n]%10007) 3. 오답원인 4. 알게된 점

출처:: https://www.acmicpc.net/problem/11726 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP #2×n 타일링 #https://www.acmicpc.net/problem/11726 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*1001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]%10007) 3. 오답원인 4. 알게된 점

출처:: https://www.acmicpc.net/problem/9095 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP #1, 2, 3 더하기 #https://www.acmicpc.net/problem/9095 import sys sys.stdin = open("input.txt","r") t=int(input()) for _ in range(t): n=int(input()) #dp=[0]*(n+1) ->에러원인 dp=[0]*12 dp[1]=1 dp[2]=2 dp[3]=4 if n>=4: for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2]+dp[i-3] print(dp[n]) 2. DP 리팩토링 #1, 2, 3 더하기 #https://www.acmicpc.net/pr..