아이테킨의 끄적끄적

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번째..

이진탐색(binary search)를 통해서 풀 수 있는 문제다. 이진탐색을 사용할 수 있는 조건은 배열이 정렬이 된 상태에서 사용할 수 있다. 또한 이진탐색은 순차적으로 탐색하는 방법보다 훨씬 빠르게 원하는 값을 찾아낼 수 있다. 시간복잡도 -> O(logN) 탐색해야하는 숫자의 수가 절반씩 줄어들기 때문에! 이진탐색은 반복문 말고도 재귀를 사용하여 구현할 수 있다. 두가지 모두 알아두고 구현해낼 수 있도록 연습해야겠다. # 1920 수 찾기 n = int(input()) list_n = list(map(int, input().split())) list_n.sort() m = int(input()) list_m = list(map(int, input().split())) # 반복문을 이용한 이진탐색 d..

그리디 문제인만큼 어떤 딱 떠오르는 아이디어를 찾으려고 하기보다는 생각나는대로 생각을 이어가보았다..!! 우선 양수와 음수를 따로 리스트로 변수설정을 해줬다. 양수 리스트에서는 큰 수 끼리 곱해서 더해줄 떄 가장 큰 값을 가지므로 내림차순, 음수 리스트는 작은수 끼리 곱해서 더해줄 때 (음수 * 음수 = 양수)가 되므로 오름차순으로 정렬했다. 그리고 큐 자료구조를 이용해서 양수,음수 리스트에서 하나하나 빼가면서 나중에 한꺼번에 곱해줄 리스트(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)

이 문제를 풀때의 아이디어는 나머지의 크기에 따라서 답이 달라진다는 것이다. 나머지가 연속으로 사용할 수 있는 기간(L)과 비교해서 큰 경우와 작은경우 케이스별로 처리하면 된다. 사실, 그냥 생각나는대로 풀어보았는데 운좋게 한번에 맞았다. 어떻게 이렇게 풀게 되었는지 설명하기가 애매한 듯 싶다. 이게 그리디 문제의 특징이 아닌가 싶다...? 라는 개인적인 생각.. 크흠... # 4796 캠핑 case = 0 while True: case += 1 L, P, V = map(int, input().split()) if (L + P + V) == 0: break remainder = V%P if V%P

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다. 처음에 이 문제를 풀 때 '힙(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인 ..

오랜만에 코딩테스트 문제를 다시 풀어보았다. 곱셈의 값들이 각각 가장 작게 되도록 만드는 방법을 생각하는 것이었다. 가장 큰 값에 가장 작게 곱셈을 해줄때 최종 합이 가장 작을것이라는 아이디어로 풀어보았다. 각 리스트를 정방향, 역방향으로 정렬한 후에 excel에서 쓴 sumproduct를 구현해보았다. [x*y for (x,y) in zip(list_1,list_2)] 이 부분이 sumproduct인데 알아두면 두고두고 유용하게 써먹을 코드가 될 것 같다. # 1026 보물 n = int(input()) # 각 데이터를 공백으로 구분하여 입력값을 받는다. list_1 = list(map(int, input().split())) list_2 = list(map(int, input().split())) l..