백준 2056 작업
위상정렬과 dp앞에서 선행 작업의 합을 누적해서 더해준다(그 중 가장 큰 것)처음에 선행작업이 0개인 작업이 항상 1개인줄 알고 이렇게 했는데 다시 보니까 반드시 하나 이상 존재한다고 그랬다
백준 12865 평범한 배낭
dp + 이차원 리스트i : 번째 배낭까지 탐색j : 총 무게놓고 탐색하며 di 값을 업데이트한다.무게가 같은 것이 다른 조합으로 이미 있을 수 있으니 max를 썼다.처음에는 이런 식으로 짜서 갱신된 값은 업데이트가 안되는 문제가 있었다.(설명이 잘 안됨)88% 에서
백준 15989 1,2,3 더하기 4
dp + 2차원 리스트1차시도 : 시간 초과를 생각을 안함 2차시도 : ...정답 : n의 범위가 10000밖에 안되는데 한번에 계산하는게 빠르다복습 + 시간복잡도 계산
백준 13398 연속합 2 (re)
하나를 빼고 연속합을 모두 구하기엔 시간 초과 각 인덱스마다 그 수로 시작하는 연속합과 그 수로 끝나는 연속합을
백준 2133 타일 채우기
dp -> 작은 문제들이 많은 경우가 있다이 문제는 n이 짝수일 때 마다(2 제외) 가운데 걸쳐있는 경우가 2가지씩 생겨서 이것을 모두 포함해주어야 한다.
백준 11054 가장 긴 바이토닉 부분 수열
앞에서부터 증가하는 가장 긴 수열 2. 뒤에서부터 증가하는 가장 긴 수열두가지 배열을 만들어서 브루트포스로 각 인덱스를 기준으로 두 값의 합이 가장 큰거 구함(인덱스까지 증가 + 감소 = 바이토닉)처음에는 인덱스 기준 앞은 증가하는, 뒤는 감소하는 가장 긴 수열을 인덱
백준 2156 포도주 시식
dp + 이차원리스트 : 예외처리(ex. n = 1 등등) 조심포도주를 시식하는 3가지 경우의 수 : 0번째로 먹기(=먹지 않음), 1번째로 먹기, 2번째로 먹기를 이차원 리스트의 행(또는 열)로 나눠서 푼다
백준 15988 1, 2, 3 더하기 3
메모리 초과 코드 : 나누기를 안함시간 초과 코드 : 매번 d를 다시 계산하면 시간 너무 많이 걸림시간 초과 코드 : 나름 머리를 써봄. 계산횟수를 줄였는데 그다지 줄여지지 않은듯먼저 d를 다 구하고 구함
백준 1699 제곱수의 합 (re)
pypy 제출 : 파이썬으로 시간 내에 풀기ans = 0 \* (n + 1)for i in range(1, n + 1): j = 1 while True: if j j >= i: ansi = ans\[i - (jj)] + 1
백준 1912 연속합
단순하게 생각하면 각 숫자마다 두가지 경우의 연속합이 생길 수 있다.1\. 그 숫자로 시작하는 연속합2\. 그 숫자로 끝나는 연속합index의 값을 차례대로 비교하면서 max를 찾는다
백준 11053 가장 긴 증가하는 부분 수열
하나짜리 수열도 증가하는 수열인지 몰랐어서 예외처리해야 하나 하고 헤맸음..처음 짠 코드는 너무 쉽게 생각함반례 : 10 20 10 10000 20 30 40 50 60 70