jae_coding

문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 구현 0의 개수: fib(n-1)의 값과 동일 1의 개수: fib(n)과 동일 코드 import sys input = sys.stdin.readline def fib(num, memo): if num == 0: return 0 elif num == 1: return 1 else: if num not in memo: memo[num] = fib(num-1, memo) + fib(num-2, memo) return memo[num] else: return memo[num] t = int(in..

문제 문제 링크 문제 접근 a에 들어갈 수 있는 범위 (1

문제 문제 링크 문제 접근 DP를 이용하여 제곱수가 N보다 작은 자연수보다 작거나 같게하여 최소한의 제곱수를 사용한다. 코드 import sys N = int(sys.stdin.readline()) dp = [i for i in range(N+1)] for i in range(1, N+1): for j in range(1, i): if pow(j, 2) > i: break if dp[i] > dp[i - pow(j, 2)] + 1: dp[i] = dp[i - pow(j, 2)] + 1 print(dp[N]) 느낀점 루프 안에 조건 문을 합쳐서 깔끔하게 만들어 보려고 했으나 그것은 실해했다. break로 루프를 빠져 나가야 시간 초과가 뜨지 않는다. 이 부분에 대하여 아시는 분 계시다면 댓글 남겨주시면 감..

문제 문제 링크 문제 접근 이분 탐색과 dp를 이용하여 문제를 풀어야 한다. 이분 탐색은 bi_sects를 구현하는 것을 이용한다. dp를 tuple을 통하여 value와 idx로 넣어서 이용한다. start가 dp의 길이보다 작을 경우에 dp의 이전 idx값을 temp에 추가한다. (이전 idx를 추적하기 위함) 코드 시간 초과 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [[-1000000001] for _ in range(N)] count = 0 for i in range(N): start = 0 end = len(dp[count]) - 1 while start = ..

문제 문제 링크 문제 접근 이전에 가장 긴 증가하는 수열과 문제 유형이 비슷하지만 dp의 개수만이 아닌 dp의 최대 길이와 dp 내용물을 출력하는 것이다. dp를 우선 구해준 후 dp를 역배열한 후, dp의 최대값을 저장하고 1씩 줄여가면서 같은 값이 있을 때 새로운 리스트에 저장을 해준다. 그리고 리스트를 문자열로 출력해준다. 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] = max(dp[i], dp[j] + 1) count = max(dp) r..

문제 문제 링크 문제 접근 백준 12015번 과 다른 점은 배열의 값의 범위이다. -1,000,000,000 ~ 1,000,000,000 따라서 dp[0]의 초기 값을 -1,000,000,001로 지정해주어야 한다. 시간복잡도 O(N logN)인 binary search를 사용해야 한다. 코드 import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [-1000000001] for i in range(N): start = 0 end = len(dp) - 1 while start = len(dp): dp.append(seq[i]) else: dp[start] = seq[i] print(len..

문제 문제 링크 문제 접근 백준 11055번 과 다른 점은 N의 range이다. 이점을 잘 생각해야 한다. 1,000 -> 1,000,000 시간복잡도 O(N logN)인 binary search를 사용해야 한다. 코드 시간 초과 코드 (시간 복잡도: O(N^2)) import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] = max(dp[i], dp[j] + 1) print(dp) 통과 코드 ( 시간복잡도: O(NlogN) import sys N = int(sys..

문제 문제 링크 문제 접근 이 문제는 dp에 대한 개념을 정리하기에 좋은 문제인 듯하다. step1: N과 수열 받아온다. step2: dp의 list를 모두 1로 초기화한다. step3: i번째 수열의 이전 값이 i번째 수열 값보다 크면 dp의 i번째를 dp의 i번째와 이전의 dp보다 큰 값이 있다면 그 값에 +1한 것과 비교하여 높은 것을 dp의 i번째에 넣는다. step4: dp리스트에서 가장 높은 값을 출력한다. 코드 import sys N = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if array[i] <..

문제 문제 링크 문제 접근 N가지 종류의 동전 -> 가치의 합 K원이 되도록해야한다. 각각의 동전은 몇개라도 사용할 수 있다. 출력: 경우의 수 동전의 종류를 몇가지 사용하는지에 따라 분류한다. (예를들어 3가지면 1가지만 사용했을 경우, 2가지만 사용했을 경우, 3가지를 사용했을 경우를 더한 값이 모든 경우의 수가 된다.) 2차원배열을 사용하면 좋겠지만 메모리 문제로 인하여 1차원 배열을 사용하자 점화식: dp[j] += dp[j-coins[j]] 코드 import sys N, K = map(int, sys.stdin.readline().split()) coins = list() for _ in range(N): coins.append(int(sys.stdin.readline())) coins.sort..

문제 문제 링크 문제 접근 LCS: 최장 공통 부분 수열 ex)ACAYKP, CAPCAK -> ACAK output: LCS의 길이 예제로 문제를 접근해 보았다. x, y 축의 첫 항의 값은 모두 0으로 고정이다. (margin을 주기 위함) x, y 축에 cross하여 같은 것이 있으면 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값에 + 1해주는 식의 알고리즘이다. 그렇지 않으면, 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값 중 높은 값을 입력하면 된다. 잘 이해가 되지 않으니 그림으로 설명하겠다. 그림1 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 A 0 1 Y 0 1 K 0 1 P 0 1 그림2 0 C A ..