본문 바로가기

알고리즘

[백준 알고리즘/Python] 140023 가장 긴 증가하는 부분 수열4
알고리즘/백준알고리즘 2022. 2. 7. [백준 알고리즘/Python] 140023 가장 긴 증가하는 부분 수열4 문제 문제이해 가장 긴 증가하는 부분 수열과 비슷하빈다. 이번에는 가장 긴 증가하는 부분 수열을 찾아야합니다. 우리는 dp 배열에 각 자리의 수열개수가 들어있다는 것을 압니다. 그러면 주어진 수열을 거꾸로 돌면서 최고 수열 개수인 수를 찾으면 됩니다. 그러니 최고 수열 개수를 1개 찾으면 1을 줄여줘서 다음 수를 찾아 봐야 합니다. 코드 test_case = int(input()) nums = list(map(int,input().split())) dp = [1] * test_case for i in range(1, test_case): for j in range(i): # 자리수 맨 왼쪽부터 들어온다. if(nums[i] > nums[j]): # 자리수 왼쪽부터 체크 dp[i] = max(dp[j]+ ..
[백준 알고리즘/Python] 11053 가장 긴 증가하는 부분 수열
알고리즘/백준알고리즘 2022. 2. 6. [백준 알고리즘/Python] 11053 가장 긴 증가하는 부분 수열 문제 문제이해 수열이 주어지면 각 자리수마다 따로 생각해봅니다. 왼쪽으로 더 적은 수가 들어오면 그것이 수열이 됩니다. 처음에 이해가 되지 않아 https://bitwise.tistory.com/215 블로그를 참고했습니다. 코드 test_case = int(input()) nums = list(map(int,input().split())) dp = [1] * test_case for i in range(1, test_case): for j in range(i): # 자리수 맨 왼쪽부터 들어온다. if(nums[i] > nums[j]): # 자리수 왼쪽부터 체크 dp[i] = max(dp[j]+ 1 , dp[i]) # 바뀐 것, 더 큰것 체크 print(max(dp)) # 꼭 끝쪽에 최대 길이 배열이 없..
[백준 알고리즘/Python] 2193 이친수
알고리즘/백준알고리즘 2022. 2. 5. [백준 알고리즘/Python] 2193 이친수 문제 문제이해 N=1일 때는 1만 있으니 맨 끝자리는 1 N=2일 때는 10, 만 있으니 맨끝자리는 0 ... 이렇게 맨 끝자리를 보면됩니다. 끝자리가 0인 경우 끝자리가 1인 경우 N=1 0 1 N=2 1 0 N=3 1 1 N=4 2 1 N=5 3 2 N=6 5 3 끝자리가 0일 때 0,1 이 들어갈 수 있고 끝자리가 1일 때는 0만 들어갈 수 있습니다. 코드 num=int(input()) d = [[0] * 2 for _ in range(91)] d[1]=[0,1] d[2]=[1,0] for i in range(3,91): d[i][0] = (d[i-1][0]+d[i-1][1]) d[i][1] = (d[i-1][0]) print((sum(d[num])) )
[백준 알고리즘/Python] 10844 쉬운 계단 수
알고리즘/백준알고리즘 2022. 2. 4. [백준 알고리즘/Python] 10844 쉬운 계단 수 문제 문제 이해 0을 제외한 모든 숫자는 앞에 올 수 있다. 이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1). 하지만 9 뒤엔 오직 숫자 8만이 올 수 있다. dp테이블은 이차원 리스트이며 dp[자리 수][앞에 오는 숫자]=경우의 수입니다. 앞에 오는 숫자 = 0 ) dp[자리 수][0] = dp[자리 수 - 1][1] ※ dp[1][0] = 0이기 때문에 어차피 결과엔 영향을 미치지 않는다. ex) 0, 01, 012 -> 안 셈! 앞에 오는 숫자 = 1~8 ) dp[자리 수][앞에 오는 숫자] = dp[자리 수 - 1][앞에 오는 숫자 -1] + dp[자리 수 - 1][앞에 오는 숫자 + 1] dp[n][i] = dp[n][i-1] + dp 앞에 오는 숫자 =9 ) dp[자리 수][9..
[백준 알고리즘/Python] 15990 1,2,3 더하기 5
알고리즘/백준알고리즘 2022. 2. 3. [백준 알고리즘/Python] 15990 1,2,3 더하기 5 문제 문제이해 dp[1] 1 1개 dp[2] 2 2개 1+1 dp[3] 3 4개 1+2 2+1 1+1+1 dp[2]에 1 더해주기 dp[4] 1+3 3+1 1+2+1 2+1+1 1+1+1+1 dp[3]에 1 더해주기 7개 2+2 1+1+2 dp[2]에 2 더해주기 dp[5] 1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2 dp[4]에 1 더해주기 13개 3+2 1+2+2 2+1+2 1+1+1+2 dp[3]에 2 더해주기 2+3 1+1+3 dp[2]에 3 더해주기 여기에서 중복을 제외해야 합니다. 5를 예를 들면 dp[4]에서 마지막 값이 1인 것은 제외해야합니다. dp[3]에서 마지막 값이 2인 것은 제외해야합니다. dp[2]에서 마지막 값이 3인 것은 제외해야합..
[백준 알고리즘/Python] 16194 카드 구매하기2
알고리즘/백준알고리즘 2022. 2. 2. [백준 알고리즘/Python] 16194 카드 구매하기2 문제 문제이해 카드의 개수(N)를 구해야 합니다. 1부터 순서대로 카드팩안에 카드들이 있습니다. 동일한 개수인데 가장 적은 금액을 내야한다고 합니다. 일단 카드의 개수 안에서 낼 수 있는 금액들을 추려봅니다. 그 다음 최소값을 구하면 됩니다. ex) 카드 4개를 사야하고 카드팩1 = 1원, 카드팩2 = 5원, 카드팩3 = 6원, 카드팩4 = 7원 인 상황입니다. 카드 1개를 샀을 때 카드팩1 1개이니 1원이 최소값입니다. 카드 2개를 사야할 때 (카드팩1) * 2, (카드팩2) 2개의 상황이 주어지는데 카드팩 2의 금액이 작으니 (카드팩1) * 2를 골라줍니다. 카드 3개를 사야할 때 (카드팩1) * 3, (카드팩2 + 카드팩1), (카드팩3) 3개의 상황이 주어지는데 (카드팩1) * 3이 가장 큰 금액..
[백준 알고리즘/Python] 11052 카드 구매하기
알고리즘/백준알고리즘 2022. 1. 31. [백준 알고리즘/Python] 11052 카드 구매하기 문제 문제 이해 카드의 개수(N)를 구해야 합니다. 1부터 순서대로 카드팩안에 카드들이 있습니다. 동일한 개수인데 가장 많은 금액을 내야한다고 합니다. 일단 카드의 개수 안에서 낼 수 있는 금액들을 추려봅니다. 그 다음 최대값을 구하면 됩니다. ex) 카드 4개를 사야하고 카드팩1 = 1원, 카드팩2 = 5원, 카드팩3 = 6원, 카드팩4 = 7원 인 상황입니다. 카드 1개를 샀을 때 카드팩1 1개이니 1원이 최대값입니다. 카드 2개를 사야할 때 (카드팩1) * 2, (카드팩2) 2개의 상황이 주어지는데 카드팩 2의 금액이 크니 카드팩2를 골라줍니다. 카드 3개를 사야할 때 (카드팩1) * 3, (카드팩2 + 카드팩1), (카드팩3) 3개의 상황이 주어지는데 6원이 가장 큰 금액이니 골라줍시다. 카드 4..
[백준 알고리즘/Python] 9095 1,2,3더하기
알고리즘/백준알고리즘 2022. 1. 30. [백준 알고리즘/Python] 9095 1,2,3더하기 문제 문제이해 1 => 1 )=>1개 2 => 1+1, 2 )=>2개 3 => 1+1+1 , 1+2, 2+1, 3 )=>4개 만약 4를 1,2,3으로만 표현하려면 1+3, 2+2이 됩니다. 즉 1로 나타내는수, 2로 나태는수, 3으로 나태내는수를 모두 더하면 됩니다. 1로 나타내는수, 2로 나태는수, 3으로 나태내는수 1 + 2 + 4 =7개로 이 됩니다. dp[1] 1 1개 dp[2] 2 2개 1+1 dp[3] 3 4개 1+2 2+1 1+1+1 dp[2]에 1 더해주기 dp[4] 1+3 3+1 1+2+1 2+1+1 1+1+1+1 dp[3]에 1 더해주기 7개 2+2 1+1+2 dp[2]에 2 더해주기 dp[5] 1+3+1 3+1+1 1+2+1+1 2+1+1+1 1+1+1+1+1 2+2+1 1+1+2 d..
[백준 알고리즘/Python] 11727 2×n 타일링2
알고리즘/백준알고리즘 2022. 1. 29. [백준 알고리즘/Python] 11727 2×n 타일링2 문제 문제이해 11726에서 풀었떤 계념을 다시 이용하면 됩니다. 위 모양을 만들어야 하는데 2x1, 2x2 2개를 써야하니 dp[n-2]를 2번 사용하는 것이 포인트 입니다. n의 개수에 따라 나오는 타일의 수 입니다. 코드 num = int(input()) d = [0] * (1001) d[1] = 1 d[2] = 3 for i in range(3,num+1): d[i] = d[i-1] + (d[i-2]*2) print(d[num] % 10007)

티스토리툴바