분류 전체보기354

• 

  [Python] 백준 11053번: 가장 긴 증가하는 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [1] * n for i in range(1,n): for j in range(i): if A[i] > A[j]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) DP를 이용하면 나름 쉽게 풀 수 있는 문제이다. 주어진 수열이 있을 때 예) 1 100 2 3 4 200 300 400 500 6 가장 긴 부분 수열을 찾으면 된다. 이중 for문을 이용해 j는 0~i-1까지 돌면서 A[i] 랑 A[j] 를 비교하는 것이다. 즉, i보다 앞에 있는 수 중에 A[i] 보다 작다면, dp값을 비교한다. 만약 지금 i가 200에 있다고 하자. dp[4] = 1 2 3 4 로 .. 알고리즘/동적프로그래밍(DP) 2021. 1. 23.

• 

  [Python] 백준 2156번: 포도주 시식 풀이 소스코드 n = int(input()) wine = [] dp = [[0] * 3 for _ in range(n)] for i in range(n): wine.append(int(input())) dp[0][1] = wine[0] for i in range(1,n): dp[i][0] = max(dp[i-1]) dp[i][1] = dp[i-1][0] + wine[i] dp[i][2] = dp[i-1][1] + wine[i] print(max(dp[n-1])) n 이 1일때를 고려해주지 않아 계속 런타임 에러가 난 문제... 휴! 연속으로 와인 3잔을 먹지 못하는 것을 힌트로 문제를 풀어나가면 된다. dp[i][j] 는 i번째 와인을 먹을 때, 최대로 마실 수 있는 포도주의 양을 저장한 것이다. i는 0부터.. 알고리즘/동적프로그래밍(DP) 2021. 1. 22.

• 

  [Python] 백준 9465번: 스티커 풀이 소스코드 T = int(input()) for _ in range(T): n = int(input()) dp = [list(map(int, input().split())) for _ in range(2)] dp[0][1] += dp[1][0] dp[1][1] += dp[0][0] for i in range(2,n): dp[0][i] += max(dp[1][i-1], dp[1][i-2]) dp[1][i] += max(dp[0][i-1], dp[0][i-2]) print(max(dp[0][n-1], dp[1][n-1])) 그림으로 예를 들겠다. dp[0][3] 이 최대가 되려면 dp[1][2] 를 선택하거나 dp[1][1] 을 선택해야 한다. dp[1][1] 을 선택시 그 오른쪽옆인 dp[1][2] 는 당연.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 2193번: 이친수 풀이 소스코드 n = int(input()) # dp 초기화 #dp[i][j] 에서 i는 자리수, j는 끝에 오는 수 dp = [[0]*2 for _ in range(n+1)] dp[1][1] = 1 for i in range(2, n+1): dp[i][0] = sum(dp[i-1]) dp[i][1] = dp[i-1][0] print(sum(dp[n])) 1자리 -> 1 (1가지) 2자리 -> 10 (1가지) 3자리 -> 101, 100 (2가지) 이번 문제도 마찬가지로 수의 끝자리에 따라 케이스를 나눌 수 있다. dp[i][0] 은 i자리수에서 0으로 끝나는 이친수의 개수이다. dp[i][1] 은 i자리수에서 1로 끝나는 이친수의 개수이다. dp[i] 는 dp[i][0] + dp[i][1] 로 정의할 수 있.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 11057번: 오르막 수 풀이 소스코드 n = int(input()) # dp 초기화 (최소 1개는 있으므로) #dp[i][j] 에서 i는 자리수, j는 끝에 오는 수 dp = [[0]*10 for _ in range(n+1)] dp[1] = [1]*10 for i in range (1, n+1): for j in range (0, 10): for k in range (0, j+1): dp[i][j] += dp[i-1][k] print(sum(dp[n]) % 10007) 저번 문제와 마찬가지로 자리수에 따른 끝 자리 숫자로 규칙을 유추하였다. 1자리 일 때는 당연히 모든 숫자가 1가지 방법을 가진다. (0도 숫자 첫번째에 올 수 있음) 2자리 일 때는 _0 은 1개, _1은 2개, _2는 3개, ...._9는 10개를 가진다. 3자리.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 10844번: 쉬운 계단 수 풀이 소스코드 n = int(input()) # dp 초기화 (최소 1개는 있으므로) dp = [[1]*10 for _ in range(n+1)] # dp[i][j] 에서 i은 자리수, j는 수의 마지막 숫자 # 1자리 수는 0이 끝에 올 수 없으므로 0개로 저장 dp[1][0] = 0 if n!= 1 : for i in range(2, n+1): for j in range(0, 10): if j==0 : dp[i][j] = dp[i-1][1] elif j==9 : dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[n]) % 1000000000) dp채우기/ dp[i][j] / i는 자리수, j는 수의 끝에 오는 숫자.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 9095번: 1, 2, 3 더하기 풀이 소스코드 T = int(input()) for i in range(T): dp = [0,1,2,4] n = int(input()) for j in range(4,n+1): dp.append(dp[j-3] + dp[j-2] + dp[j-1]) print(dp[n]) 0 -> 0개 1 = 1 -> 1개 2 = 1 +1 -> 2개 = 2 3 = 1 + 2 -> 4개 = 2 + 1 = 3 = 1 + 1 + 1 까지는 쉽게 구할 수 있다. 그렇다면 4는? 크게 세 가지 방법으로 1 + 3 / 2 + 2 / 3 + 1 이 있다. 왜냐면 1,2,3의 합으로 표시를 하는 것이므로 항상 1 + (n-1) / 2 + (n-2) / 3 + (n-3) 으로 구할 수 있는 것이다!! 그렇다면 밑줄 친 3, 2, 1 을 또 여러.. 알고리즘/동적프로그래밍(DP) 2021. 1. 21.

• 

  [Python] 백준 11727: 2xn 타일링 2 풀이 소스코드 n = int(input()) dp = [0,1,3] for i in range(3,n+1): dp.append(2 * dp[i-2] + dp[i-1]) print(dp[n] % 10007) 저번 문제와 동일한 구조이다. 이번에는 2x2 타일이 추가되었으므로, dp[n-2] 에서 dp[n] 이 되기 위해선 1x2 타일 2개를 놓는 방법, 2x2 타일 1개를 놓는 방법 -> 2 * dp[n-2] 의 횟수와 동일 + dp[n-1] 에서 dp[n] 이 되기 위해서 2x1 타일 1개를 놓는 방법 -> dp[n-1] 의 횟수를 더해주면 된다. 즉, dp[n] = 2 * dp[n-2] + dp[n-1] 로직이 거의 동일하여 더 이상의 설명은 생략하겠다. 자세한 설명은 11276 참고! 알고리즘/동적프로그래밍(DP) 2021. 1. 20.

• 

  [Python] 백준 11726번: 2xn 타일링 풀이 소스코드 n = int(input()) dp = [0,1,2] for i in range(3,n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n] % 10007) 처음에는 감을 못 잡았는데 n의 갯수를 1부터 5까지 늘려가면서 규칙을 파악했다. n=1 -> 1 n=2 -> 2 n=3 -> 3 n=4 -> 5 n=5 -> 8 즉, 피보나치와 같은 관계식을 이끌어 낼 수 있다. dp[n] = dp[n-2] + dp[n-1] 어거지로 규칙을 알아냈긴 했는데, 왜 이렇게 되는지 생각을 해보자. 1) 2*(n-1) 에서 2xn 개로 늘리려면, 2x1 개의 타일밖에 사용하지 못한다. -> 언제나 저 방법밖에 존재하지 않으므로 이 경우에는 dp[n-1] 의 방법 개수와 같다. 즉, 검정.. 알고리즘/동적프로그래밍(DP) 2021. 1. 20.

• 

  [Python] 백준 1463: 1로 만들기 풀이 소스코드 n = int(input()) #인덱스와 일치하는 정수를 1로 만들기 위한 횟수의 최솟값 dp = [0,0,1,1] for i in range(4,n+1): # 1을 만들기까지 최대 횟수로 초기 dp.append(i-1) # 1을 뺄 때의 최솟값 dp[i] = dp[i-1] + 1 # 2로 나누어 떨어질 때 if i % 2 == 0 : # 1을 뺄 때와 2로 나눌 때 더 작은 횟수인 것을 저장 dp[i] = min(dp[i], dp[i//2] + 1) if i % 3 == 0 : # 앞에서 구한 arr[i]과 3으로 나눌 때 더 작은 횟수인 것을 저장 dp[i] = min(dp[i], dp[i//3] + 1) print(dp[n]) 처음 풀어보는 DP 문제라 조금 당황하긴 했다. 그래서 처음엔 .. 알고리즘/동적프로그래밍(DP) 2021. 1. 20.

• 

  [Python] 백준 10992번: 별 찍기 - 17 풀이 소스코드1 n = int(input()) print(" "*(n-1) + "*") if(n!=1): for i in range(1,n-1): print(" " * (n-1-i) + "*" + " " * (2*i-1) + "*") print("*" * (2*n-1)) 첫째줄과 마지막줄에 별 1개와 별 2n-1 개를 따로 출력해주고, 반복문안에서 나머지 별을 처리하는 코드이다. 그러나 비효율적이다. 소스코드2 n = int(input()) for i in range(1, n+1): if(i==1 or i==n): print(" " * (n-i) + "*" * (2*i-1)) else: print(" " * (n-i) + "*" + " " * (2*(i-1)-1) + "*") 반복문 하나에서 조건문을 추가해 .. 알고리즘/입출력 2021. 1. 20.

• 

  [Python] 백준 10991번: 별 찍기 - 16 풀이 소스코드 n = int(input()) for i in range(1,n+1): print(" " * (n-i) + "* " * (i-1) + "*") 자세히 보면 규칙이 보이는 간단한 문제이다. for문에서 i는 1부터 n까지 증가한다. 먼저, (n-i) 개의 공백을 찍고 난 후 "* "을 한 세트로(별과 공백) (i-1) 번 출력한다. 그리고 마지막 별은 공백 없이 별만 따로 추가해주면 된다. 알고리즘/입출력 2021. 1. 20.