jae_coding

문제 문제 링크 문제 접근 이분 탐색과 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..

문제 문제 링크 문제 접근 case1: N이 0 또는 1인경우는 0! 또는 1!이므로 1을 출력한다. case2: N 팩토리얼의 수를 구한 후 string타입으로 변경 후 마지막 문자부터 첫번째 문자 순서대로 "0" 인경우 count를 올려준다. 만약 "0"이 아니라면 for문을 빠져나온다. 출력은 count를 하면된다. 코드 import sys N = int(sys.stdin.readline()) num = 1 if N == 0 or N == 1: print(0) else: for i in range(1, N+1): num *= i st = str(num) count = 0 for i in range(len(st)): if st[len(st)-i-1] == "0": count += 1 else: bre..

문제 문제 링크 문제 접근 이 문제는 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 ..

문제 문제 링크 문제 접근 스티커 2n개 구매 -> 2행 N열로 배치 스티커 1장을 떼면 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용불가 (상하좌우 스티커 사용 불가) 모든 스티커가 붙일 수 없는 상황이 되었을때, 각 스티커의 점수 최대의 합을 구하는 프로그램 모든 스티커가 찢어지기 위해서는 좌표 (0, 0)에서는 (1, 1) 또는 (2, 1)으로 가야한다. 그러므로 y 좌표가 0이라면 (x, 0) -> (x+1, 1) or (x+2, 1) 그리고 y 좌표가 1이라면 (x, 1) -> (x+1, 0) or (x+2, 0)으로 이동해야한다. 코드 import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readli..

문제 문제 링크 문제 접근 가지고 다닐 배낭에 최대한 가치 있게 싸려고 한다. 여행자가 필요한 N개의 물건 (무게 W, 가치 V, 최대 K무게를 가질 수 있다.) 출력: 여행자가 배낭에 넣을 수 있는 최대 가치의 합 dp matrix: 행(K+1), 열(N+1) case1. 배낭의 허용 무게보다 넣을 무게가 크다면 i번째와 i+1번째의 넣은 무게를 같게한다. case2. 만약 허용 무게보다 작다면, 넣을 무게만큼 뺀 dp확인 후 현재 무게와 더하여 최대 값을 dp의 i번째에 저장한다. 코드 import sys # N: 물품의 수, K: 여행자가 버틸 수 있는 무게 N, K = map(int, sys.stdin.readline().split()) # W: 물건의 무게, V: 물건의 가치 elements =..