목록파이썬 (92)

시작이 반

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

처음에 무작위로 뽑았을때 만들수 있는 집합중 공통된 가장 긴 것을 찾는줄 알았다.. 풀이 만약 s1[i] == s2[j]라면 ( 추가한 문자가 같을때 ) dp[i][j] = dp[i - 1][j - 1] + 1 ( 추가되기전 값 + 1) 다르면 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) (추가되기 전 값들 중 가장 큰 값) dp[i]j] C A P C A K 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 2 3 4 P 0 1 2 3 3 3 4 s1 = ' '+input() s2 = ' '+input() dp = [[0] * len(s2) for _ in rang..
알고리즘/백준 2021. 2. 26. 17:22
[백준] 2565번(python 파이썬)

전깃줄을 입력을 받아서 list(tuple)형태로 만들고 key = tuple[0]값으로 역으로 정렬시킨다. ex) 첫번쨰 원소의 [0] 값+1의 크기만큼 list를 생성한다. dp = [1] * (link[0][0] + 1) 1 ~ 해당 전깃줄 갯수만큼 반복문을 돌린다. for i in range(1, n): 정렬된 원소를 보면서 a = link[i][0] b = link[i][1] 이전 값들중 b 값보다 큰 값들중 생성한 list의 최대값을 구한다. for j in range(i): if b < link[j][1]: max_value = max(max_value, dp[link[j][0]]) list[i]에 max값을 더해준다. dp[a] += max_value n = int(input()) link..
알고리즘/백준 2021. 2. 25. 02:12
[백준] 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
이전 Prev 1 ··· 6 7 8 9 10 11 12 Next 다음