KBW's cosmos

사실 이 문제를 볼 때 부분 수열을 만들 때 기존 수열의 순서를 그대로 따라야하는지가 헷갈렸다. 하지만 그렇다면 그냥 set으로 중복을 제거하고 수를 구하면 될 것이다... 그래서 아마 이것은 아니겠지 하고 풀었다. 처음에는 완전 탐색으로 풀 생각을 했다.. """ 1. 아이디어 - 가장 작은 수 하나를 구한다 - 이후 뒤 수열을 for문으로 돌며 큰 수를 찾는다. 2. 시간 복잡도 - 두개의 포인터 : O(N) - 전체 조회 : O(N^2) = 1,000,000 -> 가능 3. 변수 - N : int - A : int[] """ import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) max_len..

처음에는 백트래킹으로 풀 생각을 했다.. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline N = int(input()) cnt = 0 def backTracking(depth): if depth == N: global cnt cnt += 1 return elif num[-1] == 0: num.append(1) backTracking(depth + 1) num.pop() elif num[-1] == 9: num.append(8) backTracking(depth + 1) num.pop() else: for i in (num[-1] - 1, num[-1] + 1): num.append(i) backTracking(depth + 1)..

1. 아이디어 재귀 호출로 인한 시간복잡도를 줄여줄 수 있는 DP를 이용해야한다. 3차원 배열로 memoization을 만들면 되지 않을까..? 20 * 20 * 20의 공간만 있으면 된다. 2. 시간복잡도 - O(n^3) : 20 * 20 * 20 = 8000 -> 가능 3. 자료구조 a, b, c: int; dp: int[][][]; 전체코드 ↓ import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def w(a, b, c): if a 20: return w(20, 20, 20) elif dp[a][b][c]: return dp[a][b][c] elif a < b < c: dp[a][b][c] = w(a, b, c-1) + w(a,..

지금까지 푼 문제 중에는 가장 까다로웠다.. 다이나믹 프로그래밍을 통해 푸는 문제다. 먼저 Bottom-Up 방식으로 dp의 1번 인덱스부터 차근차근 생각해보겠다. 편의상 Pi 카드팩을 i번 카드팩이라고 부르겠다. dp[1] = 1을 만드는 방법 : 1번 카드팩 1개 dp[2] = 2를 만드는 방법 : 2번 카드팩 1개 or 1번 카드팩 2개 중 큰 것 dp[3] = 3을 만드는 방법 : 3번 카드팩 1개 or 1번 카드팩 1개 + dp[2] 중 큰 것 (여기서 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우는 dp[2]에서 처리가 끝난 것이다.) ... dp[n] = n을 만드는 방법 : n번 카드팩 1개 or 1번 카드팩 1개 + dp[n-1] or dp[2] + dp[n-2] or .. ..

다이나믹 프로그래밍(동적 계획법)이란 무엇일까? 다이나믹 프로그래밍(동적 계획법)은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 일반적인 분할 정복 기법(ex. 일반적 재귀로 구현한 피보나치 수열 함수)의 경우 동일한 문제를 다시 푼다는 단점을 가지고 있다. 이러한 경우에 하나의 문제를 단 한 번만 풀게해 더 효율적으로 만드는 것이 다이나믹 프로그래밍이다. 다이나믹 프로그래밍은 아래와 같은 가정 하에 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 이 가정중 두번째가 가장 핵심적인 것이다. 작은 문제에서 구한 정답이 큰 문제에서의 문제와 동일하기 때문에 작은 문제에서 구한 정답을 잠시 배열에 저장을 해놓고 나중..