아이테킨의 끄적끄적

DP문제로 이 문제는 뒤에서부터 생각해야 풀 수 있다. 뒤에서 풀어보려고 계속 노력하다가 결국엔 다른 사람의 블로그를 참고해서 풀었다. 참고 블로그 https://pacific-ocean.tistory.com/199 # 14501번: 퇴사 n = int(input()) t_list = [] p_list = [] for _ in range(n): t,p = map(int,input().split()) t_list.append(t) p_list.append(p) dp = [0]*(n+1) for i in range(n-1,-1,-1): if t_list[i] + i > n: dp[i] = dp[i+1] else: dp[i] = max(dp[i+1],p_list[i] + dp[i + t_list[i]]) pr..

DP문제다 DP문제의 가장 큰 특징은 중복되는 서브문제(overlapping subproblem)와 최적 부분 구조(optimal substructure)로 이런 유형의 문제에 접근하기 위해서는 하나의 문제를 작은 그러나 같은 방법으로 풀 수 있는 문제로 쪼개야한다. 이번 문제에서는 원하는 카드의 개수를 만드는 최대값을 구해야한다. 카드 1개 샀을때 최대값 카드 2개 샀을때 최대값 카드 3개 샀을때 최대값 카드 4개 샀을때 최대값 이런식으로 생각을 해보면 카드 1개 -> P[1] (=1개 카드 값) 카드 2개 -> max(P[1]+P[1] , P[2]) 카드 3개 -> max(P[1]+P[1]+P[1] , P[1]+P[2] , P[3]) ... 이런식으로 모두 따져봐야 하는 문제다. #11052번: 카드..

앞서 풀었던 타일 문제에 정사각형 타일이 하나 추가된 문제이다. 정사각형 모양의 타일이 하나 추가되었기 때문에 n-2번째 타일에서 가로 직사각형 두개 붙이는 경우와 정사각형 붙이는 경우, 총 두가지 방법으로 늘어났다. m(n) = m(n-1) + (2 × m(n-2)) # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] print(m[n]%10007)

LIS(Longest Increasing Subsequence)라는 유명한 DP 문제라고 한다. 처음봤다. 아이디어는 배열에 있는 숫자들을 각각 비교하면서 큰 숫자가 나올때마다 1을 더해주는 방법이다. 배열의 순서에 상관없이 증가하는 가장 긴 부분수열의 길이를 찾을 수 있다. (배열의 최대값이 답이다) # 11053번: 가장 긴 증가하는 부분 수열 # LIS(Longest Increasing Subsequence)라는 유명한 DP문제 N = int(input()) A = list(map(int,input().split())) dp = [1] * N for i in range(N): for j in range(i): if A[j] < A [i]: dp[i] = max(d[i],dp[j]+1) print(m..

예전에 공부할때 봤었던 이코테라는 책에 이 문제와 비슷한 유형이 있어서 쉽게 풀 수 있었다. 타일을 채우는 방법의 수를 구하는 문제인데 m(n) = m(n-1) + m(n-2)로 결국 피보나치 수열과 같다. 피보나치 수열은 DP의 대표적인 문제로 재귀와 반복문 둘다 풀이가 가능하고 둘다 알아놓으면 좋을 듯 하다. 이번에는 바텀업 방식으로 풀어보았다. 마지막에 10007로 나눈 나머지를 출력하는 것을 까먹으면 안된다 ㅠㅠ 이걸 놓쳐서 10분동안 "어.. 왜 안되지...??" 를 반복했다.ㅠㅠ # 11726번: 2xn 타일링 n = int(input()) m = [0]*1001 m[0] = 0 m[1] = 1 m[2] = 2 for i in range(3,n+1): m[i] = m[i-1] + m[i-2] ..

일반적인 DP문제다. 오랜만에 문제를 풀어서 그런지(코딩 자체가 굉장히 오랜만이다...ㅠㅠ) 문제를 해결하는데 생각보다 오랜 시간이 들었던거 같다. 다이나믹 프로그래밍 문제는 기본적으로 문제를 작게 잘 쪼개는것이 가장 중요하다고 생각한다. 재귀를 이용해서 풀던(탑다운), 반복문을 이용해서 풀던(바텀업) 자기가 생각하기 편한 방식대로 풀면 된다. [DP조건] 중복되는 서브문제(overlapping subproblems) - 문제해결관점 : 큰 문제를 작은 문제로 쪼갤 수 있고, 큰문제와 작은문제를 같은 방법으로 풀 수 있다. => 메모이제이션 최적 부분 구조(optimal substructure) - 문제의 구조관점 : 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다. 이 문제는 주어진 수의 3번째..

그리디 문제인만큼 어떤 딱 떠오르는 아이디어를 찾으려고 하기보다는 생각나는대로 생각을 이어가보았다..!! 우선 양수와 음수를 따로 리스트로 변수설정을 해줬다. 양수 리스트에서는 큰 수 끼리 곱해서 더해줄 떄 가장 큰 값을 가지므로 내림차순, 음수 리스트는 작은수 끼리 곱해서 더해줄 때 (음수 * 음수 = 양수)가 되므로 오름차순으로 정렬했다. 그리고 큐 자료구조를 이용해서 양수,음수 리스트에서 하나하나 빼가면서 나중에 한꺼번에 곱해줄 리스트(ans)에 추가해줬다(append) 이후 조건에 대한 자세한 설정은 문제에 나와있는 예제들을 하나하나 만족시켜가면서 만들어 본 것이다. 운좋게 한번에 통과가 되었다. 역시 그리디 문제는 겁먹지 말고 조금 지저분한데 싶더라도 일단 해보는게 가장 좋은 전략인듯 싶다! #..

중간의 뒤집는 숫자의 개수가 얼마나 많던지 상관없이 숫자가 얼마나 바뀌는지만 잘 계산하면 풀리는 문제다. 0 -> 0번 바뀜 -> 0번 뒤집음 01 -> 1번 바뀜 -> 1번 뒤집음 010 -> 2번 바뀜 -> 1번 뒤집음 0101 -> 3번 바뀜 -> 2번 뒤집음 01010 -> 4번 바뀜 -> 2번 뒤집음 010101 -> 5번 바뀜 -> 3번 뒤집음 0101010 -> 6번 바뀜 -> 3번 뒤집음 이렇게 계산되므로 규칙을 생각해보면 바뀌는 수(count) 에 1을 더한 수를 2로 나눈 나머지가 뒤집는 횟수가 된다. num = input() count = 0 for i in range(len(num)-1): if num[i] != num[i+1]: count += 1 print((count+1)//2)

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다. 처음에 이 문제를 풀 때 '힙(heap)'이라는 자료구조를 생각해내지 못해서 한참을 헤맸다. 이 문제를 풀때 가장 중요한 아이디어는 힙(heap)이라는 생각이다. 알고리즘은 이러하다. 0) 총 비교한 횟수(answer)를 0으로 둔다. 1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다. 2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수 3) 두 개를 더한 값을 총 비교한 횟수(answer)에 더해준다. 4) 두 개를 더한 값을 다시 카드 더미(card_deck) 안에 넣는다. 5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다. (참고. https://claude-u.tistory.com/341) ..

30의 배수 중 가장 큰 수를 찾아서 출력해내는 문제이다. 위키피디아에 배수 판정법이라는 것을 알게되었다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95 배수 판정법 - 위키백과, 우리 모두의 백과사전 배수 판정법은 배수인지 확인하려는 수의 배수가 맞는지 간단히 확인하는 것이다. 배수인지 확인하려는 수가 클 때에는 나눗셈을 이용하여 계산하는데 시간도 오래 걸리고 틀린 답이 나올 수 ko.wikipedia.org 결국 문제는 30의 배수인지 확인하는 것이기 때문에 위키피디아에서 나온 개념을 적용하면 될 것 같다. 3의 배수는 각 자리 숫자의 합이 3의 배수인 수이다. 30의 배수는 3의 배수이면서 일의 자리가 0인 ..