목록알고리즘/백준 (90)

시작이 반

[백준] 11053번(python 파이썬)

수열중 가장 긴 증가하는 부분 수열을 구하는 문제 dp[i] = (a[i] > a[0:i-1]보다 작은 값들 중) max( dp[0 : i-1] ) + 1 n = int(input()) a = list(map(int, input().split())) dp = [0] * n def longIncSequence(): dp[0] = 1 for i in range(1, n): max_value = 0 for j in range(i): if a[i] > a[j]: max_value = max(max_value, dp[j]) dp[i] = max_value + 1 longIncSequence() print(max(dp))
알고리즘/백준 2021. 2. 24. 18:56
[백준] 11054번(python 파이썬)

dp1 리스트 A의 i : 0 ~ n-1 에서의 증가하는 수열의 값을 구한다. dp2 리스트 A의 i : n-1 ~ 0 에서의 증가하는 수열의 값을 구한다. ex) dp3 dp3[0] = dp2[0] dp3[n-1] = dp1[n-1] 리스트 A의 i :1 ~ n-2 에서 1. 리스트 A의 j : 1 ~ i 부분에서 a[i] 보다 작은 값중에서 최대값 dp1[j] 을 찾는다. 2. 리스트 A의 j : i ~ n-2 부분에서 a[i] 보다 작은 값중에서 최대값 dp2[j] 을 찾는다. dp3[i] = 1번과 2번을 더한후 1을 더해준다. n = int(input()) a = list(map(int, input().split())) reverse_a = list(reversed(a)) inc_dp = [0]..
알고리즘/백준 2021. 2. 9. 21:07
[백준] 11055번(python 파이썬)

현재 값(A[i]에서 이전 값들(A[0] ~ A[i-1])을 보면서 현재값보다 작으면서 dp(이전에 구한값)값이 가장 큰 값을 찾는다. n = int(input()) a = list(map(int, input().split())) dp = [0] * n def sequence(): dp[0] = a[0] for i in range(1, n): max_value = 0 for j in range(i): if a[i] > a[j]: if abs(a[i] - a[j]) != 0: max_value = max(max_value, dp[j]) max_index = dp.index(max_value) dp[i] = dp[max_index] + a[i] sequence() print(max(dp))
알고리즘/백준 2021. 2. 9. 17:01
[백준] 2156번(python 파이썬)

*연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 처음에는 계단오르기와 같은 방식으로 풀었지만 계단오르기는 1칸 뛰어서 올라갈수 있는데 이문제는 몇칸이든 뛰어서 시음을 할 수있다. 이는 n잔 주워졌을떄 n-1잔 뛰어서 시음을 할 수 있다. 때문에 배열을 n+1 x n 개 만들어서 풀었지만 메모리 초과가 나왔다. 메모리 제한이 128MB이다 입력 제한이 10000인데 10001 x 10000 개 만들어버리면 당연히 메모리 초과가 나온다. 다시 생각했을때 최대 2잔까지 건너뛰어서 마셔도 최대값을 구할수 있다고 생각했다. 6 1000 1000 1 1 1000 1000 이렇게 있을때 1, 2, 5, 6을 마시는게 최대값이다. 7 1000 1000 1 1 1 1000 1000 이렇게 있다면 1, 2, 4, 6,..
알고리즘/백준 2021. 2. 9. 15:50
[백준] 1463번(python 파이썬)

dp[] 리스트의 크기를 n+1개 만들고 10^6으로 초기화 한다. dp[n] 부터 시작한다. dp[10] : 시작 연산 횟수는 0으로 초기화 이제 갈수 있는 정수가 3가지 있다. 1. 3으로 나누어 떨어지면, 3으로 나눈값 2. 2로 나누어 떨어지면, 2로 나눈값 3. 1을 뺀값 10에서는 9, 5 로 갈 수 있다. 연산된 값에 있는 숫자와 (처음 나온 숫자면 10^6이 있을 것이고, 이전에 연산된 숫자면 연산 횟수가 있을 것이다) 이전 연산횟수 +1 중 작은 값을 저장한다. x = int(input()) dp = [1e6] * (x + 1) dp[x] = 0 def make_one(): for i in range(x, 0, -1): if i % 2 == 0: dp[i // 2] = min(dp[i] ..
알고리즘/백준 2021. 2. 8. 21:34
[백준] 2579번(python 파이썬)

현재 계단으로 온 경우는 2가지이다. 1. 1단계전 계단에서 온경우 2. 2단계전 계단에서 온경우 1번일 경우 연속으로 계단을 올라갈 수 없으므로 이전에 2단계전 계단에서 올라온 경우에 현재 계단의 비용을 더한다. 2번일 경우 2단계전 계단에서 온경우의 최대값과 현재 계단의 비용을 더한다. cost[0][0]. cost[0][1] 은 0단계 임으로 0이다 i, j 0 : 연속으로 계단을 1칸씩 올라온경우 ex) 1->2 1 : 2단계씩 계단을 오른 경우 1 cost[1] cost[1] 2 dp[1][1] + cost[2] max(dp[0][0], dp[0][1]) + cost[2] 3 dp[2][1] + cost[3] max(dp[1][0], dp[1][1]) + cost[3] 4 dp[3][1] + c..
알고리즘/백준 2021. 2. 8. 20:13
[백준] 1932번(python 파이썬)

트리형태.. 이런형태의 리스트로 만들 수 있다. triangle[i][j] j i 0 1 2 3 4 0 7 1 3 8 2 8 1 0 3 2 7 4 4 4 4 5 2 6 5 dp[i][j] j i 0 1 2 3 4 0 triangle[i][j] 1 dp[i-1][ j ] + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 2 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ] dp[i-1][ j ] + triangle[ i ][ j ] 3 dp[i-1][ j ] + triangle[ i ][ j ] MAX(dp[i-1][j-1], dp[i-1][ j ]) +..
알고리즘/백준 2021. 2. 8. 01:25
[백준] 9461번(python 파이썬)

현재 선택한 색에 따라 나뉘어 지는 경우의 수가 2가지씩 존재한다. 마찬가지로 다음 상태는 이전상태에서 올 수 있는 경우의 수가 2가지 존재한다. 때문에 다음 상태는 이전 상태(2가지)중 작은 값을 찾아서 더해주면 된다. -> 2차원 배열로 dp를 만들어준다. 첫번째 행은 첫번째 집들의 비용을 넣으면 된다. import copy n = int(input()) cost = [list(map(int, input().split())) for _ in range(n)] dp = [[10001] * 3 for _ in range(n)] def RGB(): for i in range(n): for j in range(3): if i == 0: dp[i][j] = cost[i][j] else: if j == 0: d..
알고리즘/백준 2021. 2. 6. 23:26
이전 Prev 1 ··· 5 6 7 8 9 10 11 12 Next 다음