아이테킨의 끄적끄적

이항계수를 구하는 구하는 알고리즘을 짜면 되는 문제이다. 1. 이항계수의 정의를 이용하여 그대로 구현! 이항계수를 구하는 공식은 고등학교때 당연히 배웠지만 까먹었다 해도 문제는 없다. 우리에겐 구글이 있기 때문에...!! 구글에 이항계수만 검색해도 친절하게 설명해주는 블로그와 사이트들이 많이 있다. 자신이 보기 편한 것을 보고 이해하고 그 공식을 구현하면 쉽게 풀리는 문제이다. 사실 이미 알고있는 공식을 구현하기만 되는 것이라 따로 머리를 크게 쓰고 아이디어를 짜낼 필요도 없다. 아래의 첫번째 코드가 이항계수의 공식을 가장 충실히 따라 알고리즘을 구현한 코드이다. python에는 math라이브러리에 펙토리얼을 구할 수 있는 기능들이 있지만 연습도 할 겸, 코드량도 많지 않으니 팩토리얼 함수를 구현하여 이..

n = int(input()) li = list(map(int,input().split())) #증가하는 수열 - LIS dp = li[:] for i in range(n): for j in range(i): if li[i] > li[j]: dp[i] = max(dp[i],dp[j]+li[i]) print(max(dp)) 11054번에서 만든 증가하는 부분수열 구하는 알고리즘에서 부분수열의 개수를 구하는 것이 아니라 부분수열의 합을 구해서 dp리스트에 업데이트를 해주면 된다. 아래 코드는 증가하는 부분수열의 개수를 구하는 알고리즘이다. 비교를 해보면 위의 dp[j]+li[i]는 부분수열의 합을 구하기 위한 계산이고 dp[j]+1은 부분수열의 개수를 구하기 위한 계산이다. n = int(input()) l..

# 11054번 : 가장 긴 바이토닉 부분 n = int(input()) li = list(map(int,input().split())) #증가하는 수열 - LIS dp_inc = [1 for i in range(n)] for i in range(n): for j in range(i): if li[i] > li[j]: dp_inc[i] = max(dp_inc[i],dp_inc[j]+1) li.reverse() #감소하는 수열 - DIS dp_desc = [1 for i in range(n)] for i in range(n): for j in range(i): if li[i] > li[j]: dp_desc[i] = max(dp_desc[i],dp_desc[j]+1) dp_desc.reverse() ans ..

# 11507 번 : 오르막 수 n = int(input()) dp = [[0]*10 for i in range(n+1)] dp[1] = [1] * 10 for i in range(2,n+1): for j in range(0,10): for k in range(j,10): dp[i][j] += dp[i-1][k] print(sum(dp[n])%10007) dp문제는 점화식을 구하는 것이 가장 중요하다. 그리고 점화식을 구하려면 손으로 써가면서 규칙을 찾는 방법이 제일 좋은 것 같다 n = 1일때 0,1,2,3,4,5,6,7,8,9 로 총 10개의 오르막 수 가 있다. n = 2일때 00~09 :10개 11~19 : 9개 22~29 : 8개 ... 99 : 1개 로 10+9+8+7+6+5+4+3+2+1 =..

# 2293번 : 동전1 n,k = map(int,input().split()) coins=[] for _ in range(n): coins.append(int(input())) dp = [0 for i in range(k+1)] dp[0] = 1 for i in coins: for j in range(1, k + 1): if j - i >= 0: dp[j] += dp[j - i] print(dp[k]) 동적계획법(Dynamic Programming)알고리즘을 풀 때에는 항상 아래의 내용을 확인하면서 풀어야 한다. 중복되는 서브문제(overlapping subproblem) : 큰 문제를 작은 문제로 쪼갤 수 있어야한다. 즉 전체의 문제를 같은 방법이지만 부분문제로 나누어야 하며 이를 통해 나오는 부분문..

# 9465번 : 스티커 t = int(input()) for _ in range(t): n = int(input()) dp = [list(map(int,input().split())),list(map(int,input().split()))] for i in range(1,n): if i == 1: dp[0][i] += dp[1][i-1] dp[1][i] += dp[0][i-1] else: dp[0][i] += max(dp[1][i-1], dp[1][i-2]) dp[1][i] += max(dp[0][i-1], dp[0][i-2]) print(max(dp[0][n-1],dp[1][n-1])) 총 세가지 케이스로 나눠서 생각해 볼 수 있다. 1) n == 1인 경우 제일 쉬운 케이스이다. 아래의 그림처럼 두..

LCS는 임의의 두 문자열에서 가장 긴 subsequence의 길이를 구하는 문제다. 처음 접해보는 개념이라 2시간정도 혼자서 고민하다가 다른 사람의 정리된 블로그를 보면서 이해하였다. 이미 만들어 놓은 결과위에 새로운 문제들을 이어서 푼다는 DP의 특징을 기억하고 있을 필요가 있다. 위의 표에서 (2,3), (2,6), (3,2), (3,5), (4,3), (4,6), (6,7)은 모두 행과 열의 문자가 같다. 이렇게 행과 열의 문자가 같은 셀의 값은 왼쪽 대각선 위에 있는 수에서 1을 더한 값이 되는 규칙을 찾을 수 있다. 1. 각각의 문자열에서 가장 최근에 추가된 문자가 같을 경우 왼쪽 대각선 위의 셀에서 각각 같은 문자열이 추가되었으므로 +1을 해준다. 예) (3,5)셀 : CAP와 A에서 C가 ..

조합 공식을 이용해서 풀 수 있는 문제였다. 고등학교때 이후로 머리속에서 꺼내보지 않았던 개념이라 인터넷으로 다시 조합공식을 찾아보기도 했다....하핳 펙토리얼(fac)함수를 정의하고 정의한 함수를 이용해서 조합 공식을 만들어서 풀었다. # 1010번 : 다리놓기 # 조합(Combination)공식을 이용해서 쉽게 풀 수 있다. t = int(input()) def fac(n): num = 1 for i in range(1,n+1): num *= i return num for _ in range(t): m,n = map(int,input().split()) bridge = fac(n) // (fac(m)*fac(n-m)) print(bridge)

# 2193번 : 이친수 # 재귀방법으로 피보나치 수열을 만들면 시간복잡도가 크기 때문에 시간초과가 난다. # tablatoin 방법으로 만들면 시간면에서 훨 효율적이다. n = int(input()) table = [0]*91 table[1] = 1 table[2] = 1 for i in range(3,n+1): table[i] = table[i-1] + table[i-2] print(table[n]) n=1 : 1 n=2 : 1 n=3 : 2 n=4 : 3 n=5 : 5 n=6 : 8 ... 처음엔 그냥 숫자들을 적어보다 보니 규칙을 발견할 수 있었다. 피보나치 수열과 같은 규칙이었다. 재귀방법으로 문제를 풀게 되면 시간복잡도가 커지고 시간초과가 난다 tablation방법으로 피보나치 수열을 구현하면..

# 2774번 부녀회장이 될 테야 T = int(input()) for _ in range(T): k = int(input()) n = int(input()) f0 = [x for x in range(1,n+1)] for _ in range(k): for i in range(1,n): f0[i] += f0[i-1] print(f0[-1])