전체 글355 [Python] 백준 2751번 : 수 정렬하기 2 소스코드 n = int(input()) arr = [[0] for _ in range(n)] for k in range(n) : arr[k] = int(input()) arr.sort() for i in range(n): print(arr[i]) 하핫.... 방학 때 신나게 논다고 약 40일 만에 컴백한 나 ... 혼나야된다.. 개강도 하고 이제 진짜 3학년이다. 고학년이란 말이야...!!!!!! 오늘부터 하루에 최소 1문제는 풀기로 약속 !!!! 첫 문제는 간단하게 오름차순 정렬 문제이다. sort() 를 이용하면 간단하게 해결할 수 있다. sort 와 sorted 의 차이점을 간단하게 말하자면, list.sort() 는 원래의 리스트를 정렬한 후 반환하는 것, 즉 원래의 list 가 변하는 것이다. .. 알고리즘/이것저것 2021. 3. 8. [Python] 백준 11052번: 카드 구매하기 풀이 소스코드 n = int(input()) p = list(map(int, input().split())) p.insert(0,0) dp = [0 for _ in range(n+1)] for i in range(1, n+1): for j in range(1,i+1): dp[i] = max(dp[i], p[j] + dp[i-j]) print(dp[n]) 문제가 길어서 지레 겁먹었지만, 사실상 그리 어렵지 않은 문제이다. 여느 dp문제처럼 작은 문제 부터 풀어나가면 된다. 즉 1부터 n까지 각각의 카드수를 위한 금액의 최댓값을 구해나가는 것이다. 4 3 5 15 16 을 예시로 들자. dp[1] 은 언제나 p[1] 과 동일할 것이므로 3 일 것이다. dp[2] 는 dp[1] + p[1] 또는 p[2] 둘 중 큰.. 알고리즘/동적프로그래밍(DP) 2021. 2. 4. [Python] 백준 2011번: 암호코드 풀이 소스코드 n = list(map(int,input())) l = len(n) dp = [0 for _ in range(l+1)] if (n[0] == 0) : print("0") else : n = [0] + n dp[0]=dp[1]=1 for i in range(2, l+1): if n[i] > 0: dp[i] += dp[i-1] temp = n[i-1] * 10 + n[i] if temp >= 10 and temp 이전 dp 값을 더한다. ( 이전 dp 가 가지는 방법들 뒤에 한 자리수로 추가하기만 하면 되므로 이전 dp값을 default로 가질 수 있다. ) 예) 2 5 1 1 4 에서 빨강색까지는 이미 구했다고 하자. 2 5 1 1 / 25 1 1 / 2 5 11 / 25 11 이렇게 4가지의 방.. 알고리즘/동적프로그래밍(DP) 2021. 2. 4. [Python] 백준 2225번: 합분해 풀이 소스코드 n, k = map(int,input().split()) dp = [[0] * (k+1) for _ in range(n+1)] dp[0][0] = 1 for i in range(0, n+1): for j in range(1, k+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][k] % 1000000000) 만약 n=20, k=5 라면 20을 5개로 나눈 것은 [0+(20을 4개로 나눈것)] + [1+(19를 4개로 나눈것)] + ... + [19+(1을 4개로 나눈것)] + [20+(0을 4개로 나눈것)] 일 것이다. 즉 점화식으로 표현한다면, dp[n][k] = dp[0][k-1] + dp[1][k-1] + ... dp[n-1][k-1] + dp[n].. 알고리즘/동적프로그래밍(DP) 2021. 2. 3. [증권] 美선 공매도세력 개미에 밀려…게임스톱 하루새 134% 폭등 www.mk.co.kr/news/stock/view/2021/01/94451/ 美선 공매도세력 개미에 밀려…게임스톱 하루새 134% 폭등 공매도 투자자 191억弗 손실 "개인투자자 이젠 월가 견제" "합리성 사라진 도박꾼의 나라" 게임스톱 사태 두고 평가 상반 www.mk.co.kr 미국 주식을 하는 사람이라면 이 사건을 모를 수가 없을 것이다. 개인 투자자들이 대형 헤지펀드의 공매도에 대항해 게임스탑 주식을 대량으로 매수하며 주가를 폭등시킨 사건이다. 공매도 란? 쉽게 말해 주식을 먼저 빌려서 팔고, 나중에 주가가 떨어지면 주식을 싸게 사서 되갚아 이윤을 얻는 방식이다. 즉, 이번 사건 처럼 기존의 주식 보유자들이 절대로 주식을 팔지 않으려 하고, 물량이 나오더라도 잽싸게 사재기 한다면 주식의 씨가 마.. 시사이슈 2021. 2. 3. [Python] 백준 9461번: 파도반 수열 풀이 소스코드 T = int(input()) P = [0 for i in range(101)] P[1] = 1 P[2] = 1 P[3] = 1 P[4] = 2 P[5] = 2 for i in range(T) : n = int(input()) for j in range(6,n+1) : P[j] = P[j-1] + P[j-5] print(P[n]) 주어진 그림을 보면, 3 = 2 + 1 4 = 3 + 1 5 = 4 + 1 7 = 5 + 2 9 = 7 + 2 임을 알 수 있다. 즉, P[6]번 째부터 P[n] = P[n-1] + P[n-5] 가 성립함을 알 수 있다. 알고리즘/동적프로그래밍(DP) 2021. 2. 3. [Python] 백준 2133번: 타일 채우기 풀이 소스코드 n = int(input()) dp = [0 for _ in range(31)] dp[2] = 3 for i in range(4,n+1) : if i%2 == 0 : dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2 else : dp[i] = 0 print(dp[n]) 이전에 풀었던 타일 문제보다 어려워서 꽤 고생한 문제이다. 풀이는 위와 같다. 1) n에 대해서 n-2 까지의 dp 값에 가로길이 2 짜리 타일로 만들수 있는 3가지 경우를 곱한 경우 -> dp[n-2] * 3 2) n에 대해서 0 ~ n-4 까지의 타일 뒤에 자신을 붙혀서 만들 수 있는 2가지 경우를 곱한 경우 -> ( dp[0] + dp[2] + ... dp[n-4] ) * 2 3) n에 대해서 가.. 알고리즘/동적프로그래밍(DP) 2021. 1. 26. [Python] 백준 1699번: 제곱수의 합 풀이 소스코드 n = int(input()) dp = [x for x in range (n+1)] for i in range(1,n+1): for j in range(1,i): if j*j > i : break if dp[i] > dp[i-j*j] + 1 : dp[i] = dp[i-j*j] + 1 print(dp[n]) dp값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다. i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다. dp[i] > dp[i-j*j] + 1 이 수식은 제곱수로 표현할 때 가장 항의 개수가 작은 j 를 찾는 것이다. *즉, 예를 들어 dp[6] = dp[6 - 2*2] + 1 = dp[2].. 알고리즘/동적프로그래밍(DP) 2021. 1. 26. [Python] 백준 2579번: 계단 오르기 풀이 소스코드 1 n = int(input()) A = [[0] for _ in range(n)] dp = [[0]* 3 for _ in range (n)] for k in range(n): A[k] = int(input()) dp[0][1] = A[0] for i in range(1,n) : dp[i][0] = max(dp[i-1][1],dp[i-1][2]) dp[i][1] = dp[i-1][0] + A[i] dp[i][2] = dp[i-1][1] + A[i] print(max(dp[n-1][1], dp[n-1][2])) 저번에 풀었던 와인 문제와 비슷한 원리이다. 각 계단에 대해서 연속으로 0번 밟았을 때, 연속 1번 밟았을 때, 연속 2번 밟았을 때 총 3가지 경우로 나눠보았다. 이렇게 2차원 배열을 이.. 알고리즘/동적프로그래밍(DP) 2021. 1. 25. [Python] 백준 1912번: 연속합 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [x for x in A] for i in range(1,n): dp[i] = max(dp[i-1] + A[i], dp[i]) print(max(dp)) 처음에는 이중 for 문으로 풀었는데, 시간 초과가 나와서 '아 이렇게 푸는게 아니구나' 하는 생각에 싹 갈아엎었다. 다시 생각해보니 매우 간단했다. 그냥 한 칸 이전의 dp값이랑 자신의 수랑 더하는게 큰지, 그냥 안더하고 놔두는게 큰지 비교하기만 하면 된다. 그래서 시간복잡도가 O(n) 으로 매우 간단하다. 알고리즘/동적프로그래밍(DP) 2021. 1. 25. [Python] 백준 11054번: 가장 긴 바이토닉 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) increase = [1] * n decrease = [1] * n result = [0] * n #increase for i in range(n): for j in range(i): if A[i] > A[j] : increase[i] = max(increase[i], increase[j]+1) #decrease for i in range(n-1,-1, -1): for j in range(i+1,n): if A[i] > A[j] : decrease[i] = max(decrease[i], decrease[j]+1) result[i] = increase[i] + decrease[i] - 1 print(ma.. 알고리즘/동적프로그래밍(DP) 2021. 1. 25. [Python] 백준 11722번: 가장 긴 감소하는 부분 수열 풀이 소스코드 n = int(input()) A = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(i): if A[i] < A[j] : dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) 가장 긴 증가하는 수열과 같은 논리의 문제라서 쉽게 풀었다. dp는 1로 초기화해놓고, 이중 for문을 이용해 i번째(현재 위치) 수와 0부터 i-1까지의 수(j) 를 비교하면서 만약 앞에 있는 수가 i보다 더 클 때, 그 때의 dp값은 j의 dp보다 1 큰 값이 될 수 있다. 알고리즘/동적프로그래밍(DP) 2021. 1. 25. 이전 1 ··· 23 24 25 26 27 28 29 30 다음