목록전체 글 (139)

jae_coding

(백준 알고리즘 문제풀이) 14003번 가장 긴 증가하는 부분 수열 5

문제 문제 링크 문제 접근 이분 탐색과 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 = ..
알고리즘 문제/백준 2022. 7. 7. 22:42
(백준 알고리즘 문제풀이) 14002번 가장 긴 증가하는 부분 수열 4

문제 문제 링크 문제 접근 이전에 가장 긴 증가하는 수열과 문제 유형이 비슷하지만 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..
알고리즘 문제/백준 2022. 7. 7. 18:00
(백준 알고리즘 문제풀이) 12738번 가장 긴 증가하는 부분 수열 3

문제 문제 링크 문제 접근 백준 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..
알고리즘 문제/백준 2022. 7. 7. 16:54
Prev 1 ··· 38 39 40 41 42 43 44 ··· 47 Next