백준 알고리즘 - 피보나치 함수(1003번)[Python]

문제 문제 상황 - 재귀를 사용하여 해당 fibo를 호출할 때마다 카운팅을 하면 중복이 발생하여 연산이 너무 느리고 시간초과가 된다. 캐쉬를 사용하여 dp를 쓰면 counting을 할 수 없다. 해결 전략 - 0과 1을 분리하여 보면 이 사용 횟수도 부분적으로 피보나치를 따른다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 t = int(input()) # testcase num tc = [] # testcase for _ in range(t): tc.append(int(input())) def fibo(n): cache = [[0, 0] for _ in range(n+1)] if n == 0 : return [1, 0] cache[0] = [1, 0] cache[1] = ..
알고리즘 학습/백준 알고리즘 2020. 4. 30. 15:43
백준 알고리즘 - 평범한 배낭(12865번)[Python]

문제 문제 이미지 넣기 문제 상황 - 여러가지의 선택지가 있고 어떤 선택이 다른 선택에 영향을 주어 최선의 결과를 찾을 때 DP를 사용한다. 해결 전략 - 어떤 선택이 다른 선택에 영향을 주기 때문에 dp 사용 코드 1 2 3 4 5 6 7 8 9 10 11 12 n, k = map(int, input().split()) # 물품의 수, 버틸 수 있는 무게 입력 cache = [[0]*(k+1) for _ in range(n+1)] # cache 가 for문 안에 들어가면 안된다. # 리스트 컴프리핸션 숙지 for i in range(1, n+1): w, v = map(int, input().split()) # weight, value for j in range(1, k+1): if w > j: cach..
알고리즘 학습/백준 알고리즘 2020. 4. 29. 12:56
백준 알고리즘 - 가장 긴 증가하는 부분수열(11053번)[Python]

문제 문제 상황 - 부분 집합 중 증가하면서 길이가 가장 긴 수열을 찾는다 해결 전략 - 단순히 어떤 위치에서 대소비교를 통해 길이를 추가하면 여러가지 경우의 수 중 연속적으로 최대의 경우를 찾는게 아니라 정해진 위치보다 작은 수들의 집합을 찾게 된다. 즉, 연속된 증가하는 수열이 아니라 어떤 수보다 작은 수들의 집합을 찾게된다. 그래서 dp를 사용해야 한다. 잘못된 코드 1 2 3 4 5 6 7 n, seq = int(input()), list(map(int, input().split())) dp = [1 for _ in range(n)] # 최소 길이가 1이므로 for i in range(1, n): for j in range(i): if seq[i] > seq[j] : dp[i] += 1 print..
알고리즘 학습/백준 알고리즘 2020. 4. 29. 10:33
백준 알고리즘 - RGB 거리 (1149번)[Python]

문제 문제 상황 - 선택에 일종의 무게(가격)이 존재한다. - 선택지가 여러가지이고 선택마다 대소가 바뀌어 최선의 선택을 해야한다. 해결 전략 - DP를 이용해 해결하는데 가격이 최대가 아니라 최소이므로 min을 이용하여 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 n = int(input()) RGB = [[] for _ in range(n+1)] for i in range(1,n+1): r,g,b = map(int, input().split()) RGB[i] = [r,g,b] for i in range(2, n+1): RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[i][0] # red RGB[i][1] = min(RGB[i-1][0], RGB[i-1][..
알고리즘 학습/백준 알고리즘 2020. 4. 28. 15:48
백준 알고리즘 - 1, 2, 3 더하기 (9095번) [Python]

문제 문제 상황 - 더하는 순서에 따라 같은 숫자의 조합이여도 다르게 인식된다. - itertools 의 permutation을 하기엔 케이스가 너무 커진다. 해결 전략 - 피보나치의 점화식이 되므로 동적프로그래밍을 이용해 Bottom - up으로 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 11 t = int(input()) # testcase tc = [] def p123(n): dp = [0,1,2,4] for i in range(4,n+1): dp.append(dp[i-1]+dp[i-2]+dp[i-3]) return dp[n] for _ in range(t): tc.append(int(input())) for i in range(t): print(p123(tc[i])) cs 해설 새로 학..
알고리즘 학습/백준 알고리즘 2020. 4. 28. 13:54
백준 알고리즘 - 1로 만들기 (1463번) [Python]

동적 계획법의 첫번째 예제로 조건은 세가지이다. 문제 상황 - 경우의 수가 여러가지이고 그 중 최소가 되는 경우가 무엇인지 찾을 수가 없다. - 모든 경우의 수를 무조건 검색하기에는 연산이 너무 많다. 해결 전략 - 동적계획법을 써야한다는 사실은 알지만 적용 방법이 어려웠다. - 검색을 통해 여러가지 코드를 참고하였고 그 중 Bottom-up 방식을 사용하는 것이 그나마 이해가 되었다. 코드 1 2 3 4 5 6 7 8 9 n = int(input()) # 숫자 입력 dp = [0,0,1,1] # 0과 1은 0번으로, 2와 3은 1번의 연산으로 1 가능 for i in range(4, n+1): dp.append(dp[i-1]+1) if i%2 ==0 : dp[i] = min(dp[i], dp[(i//2..
알고리즘 학습/백준 알고리즘 2020. 4. 28. 11:13
1 ··· 5 6 7 8