아이테킨의 끄적끄적

# 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가 ..

점수가 큰 과제를 뒤에서부터 채워나가는 방법으로 과제를 해결하도록 계획을 세워야 한다. (처음엔 점수가 큰 과제부터 한다거나 마감일이 빠른 과제부터 끝내는 방법을 생각해보았지만 답은 아니었다.) 마감일 | 점수 4 | 60 4 | 40 1 | 20 2 | 50 3 | 30 4 | 10 6 | 5 이렇게 과제와 마감일이 주어져있을 때 가장 점수가 높은 과제부터 마감일부터 뒤로 계획을 세워준다. 60점 과제는 4일째 50점 과제는 2일째 40점 과제는 4일째에 이미 60점짜리를 해야하므로 3일째 30점 과제는 3일째, 2일째 이미 다른 과제가 있으므로 1일째 20점,10점 과제는 남은 기간이 없으므로 패스 5점 과제는 6일째 이런 식으로 이런 알고리즘을 구현하는 데엔 heap 자료구조를 사용하는 것이 유용하..

구글링에서 본 것중 가장 직관적이고 쉬운 풀이를 가져왔다. names = input() name_cnt = [0 for _ in range(26)] for name in names: name_cnt[ord(name)-65] += 1 odd = 0 odd_alpha = '' alpha = '' for i in range(26): if name_cnt[i] % 2 == 1: odd += 1 odd_alpha += chr(i+65) alpha += chr(i+65) * (name_cnt[i] // 2) if odd > 1: print("I'm Sorry Hansoo") else: print(alpha+odd_alpha+alpha[::-1]) # 참고 : https://alpyrithm.tistory.com/1..

우선 입력할 때 input으로 하니 시간초과가 떳다. -> sys라이브러리의 stdin.readline사용. 로직 1. 강의시간을 시작시간으로 정렬. 2. 맨 처음 강의시간의 종료시간과 두번째 강의의 시작시간을 비교 - 시작시간보다 종료시간이 느리면 새로운 강의실 배정 -> room에 heapq.heappush로 추가. - 시작시간보다 종료시간이 빠르면 기존 강의실의 종료시간 수정 -> room에 heapq.heappop 으로 기존 강의실 종료시 간을 제거하고 heapq.heappush로 새로운 종료시간 추가 굳이 heap자료구조를 사용해야 하나 생각을 해보았다. 우선 heap 자료구조가 시간복잡도 측면에서 list보다 효율적이고 heap을 사용하면 최소힙을 계속 유지해주기도 한다. # 11000번: 강..

1. 다 자라는데 가장 오랜 기간이 걸리는 나무를 첫 날 심어줘야 하기 때문에 나무를 내림차순 정렬 2. 심는데 1일, 다 자라고 나서 1일 총 2일 필요 + 심는 날짜 별로 일수 추가 3. 제일 늦게 완성되는 날짜 일수 출력. 예 - [2,3,4,3]의 나무가 있는 경우 1. 나무 [4,3,3,2]로 정렬 2. 각 나무 완성에 필요한 일수 계산 -> [2,3,4,5]를 각각 자리별로 더해줌. 3. 더해진 리스트에서 최대값 출력 # 9237번 : 이장님 초대 n = int(input()) li = list(map(int,input().split())) li.sort(reverse=True) li2 = [i+2 for i in range(n)] ans = [x+y for x,y in zip(li,li2)]..

1. 먼저 '.' 을 기준으로 입력값을 구분할 수 있도록 split함수를 사용하였다. 2. 구분된 리스트의 각 값들의 길이가 홀수이면 -1을 출력할 수 있도록 해준다. 이 때, flag변수를 설정해서 구분하였다. 3. 먼저 'AAAA'를 4로 나눈 몫만큼 곱해주고 나머지에 2로 나눈 몫만큼 'BB'에 곱해준다. 사실 지금 생각해보니 2로 나눈 몫은 항상 1이 될 수 밖에 없다. (결과는 같다.) 참고 print함수를 사용해서 list를 차례대로 출력하려고 할 때 *를 리스트 앞에 붙여주면 띄어쓰지 않고 출력해준다. 이 때 sep, end같은 print내부 옵션도 당연히 사용 가능하다. # 1343번 : 폴리오미노 li = input().split('.') ans = [] flag = 0 for i in ..

입력값만큼 키가 큰 사람을 앞에 두고 줄을 세우는 문제이다. 왼쪽부터 숫자 0의 개수를 기준으로 위치를 찾아 줄을 세우면 된다. 예를 들어 2,1,1,0 이면 [0,0,1,0] -> 0을 2개 지나친 이후 1 위치 [0,2,1,0] -> 0을 1개 지나친 이후 2 위치 [0,2,1,3] -> 0을 1개 지나친 이후 3 위치 [4,2,1,3] -> 0을 0개 지나친 이후 4 위치 # 1138번 : 한 줄로 서기 n = int(input()) li = list(map(int,input().split())) ans = [ 0 for i in range(n)] for i in range(n): cnt = 0 for j in range(n): if cnt == li[i] and ans[j] == 0: ans[j]..