일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 딥러닝
- 프로그래머스
- 프로그래밍
- 운영체제
- 알고리즘
- 코딩
- 순열
- 킥스타트
- linux
- 네트워크
- 브루트포스
- 백준
- kick start
- 그래프
- 파이썬
- 코딩 테스트
- 구글 킥스타트
- OS
- dp
- 리눅스
- nlp
- google coding competition
- PYTHON
- AI
- BFS
- DFS
- 코딩테스트
- CSS
- 동적 프로그래밍
- 동적프로그래밍
- Today
- Total
목록동적프로그래밍 (15)
오뚝이개발자
문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 생각의 흐름 예컨대, 세 자리 수를 구할 때 끝자리가 2라면 앞의 두자리에 올 수 있는 수는 2보다 작거나 같은 수들 뿐이다. 이러한 생각에 착안하여 앞자리는 두 자리 수 중 끝자리가 2인수+1인수+0인수임을 알 수 있다. 이것이 바로 동적프로그래밍을..
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 생각의 흐름 동적프로그래밍의 핵심 1) 전체 과정 중 반복되는 작은 단계 찾기 2) 해당 단계에서의 최대 혹은 최소값 찾기 3) 갱신..
문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 생각의 흐름 동적 프로그래밍을 사용하여 dp[i]에 2xi를 채우는 경우의 수를 계산하여 넣으면 된다. 점화식은 dp[i]=dp[i-2]*2+dp[i-1]이 되는데 이유는 다음과 같다. (i-1) 개 2x1 (i-2)개 2x1 2x1 (i-2)개 1x2 1x2 (i-2)개 2x2 위의 그림과 같은 경우가 있는데, 이 중 두번째 경우는 첫번째 경우에 포함이 될 수 있다. 따라서 dp[i-2]*3이 아닌 dp[i-2]*2가 ..
문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 생각의 흐름 그리 길지않기 때문에 코드로 설명을 대신한다. 코드 # 백준 11722 N = int(input()) arr = list(map(int, input().split())) dp = [1]*N for i in range(N): for j in range(i): if arr[i]
문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 생각의 흐름 이전에 포스팅한 카드 구매하기 2와 반대로 생각하면 된다. 좀 더 쉽게 말해 그 때 min을 찾았던 것을 max로 수정해주면 된다. 코드 # 백준 11052 N = int(input()) card = [0] card += list(map(int, input().split())) # dp[i]의 값은 i개의 카드를 구매하는데 필요한 최대비용 dp = [0] * (N+1) dp[1] = c..
문제 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 생각의 흐름 단순한 동적프로그래밍 문제이다. dp[i]에 담긴 값이 카드 i개를 고르기 위해 필요한 최소비용이라 하고 계산을 점진적으로 해나아간 뒤 마지막 dp[N]을 출력하면 된다. 깨달은 점 가끔씩 list의 인덱스가 0부터 시작하여 값과의 매칭이 어려운 경우가 있다. 예컨대, 이 문제의 경우 card[0]에는 카드 1개를 고를 때의 값이 담겨 있다. 이런 경우 인덱스를 고려하여 계산하기가 ..
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 생각의 흐름 무려 삼성SW역량테스트 기출문제이시다.... DP를 이용하는 문제라는 건 감을 잡았는데 알고리즘을 어떻게 적용해야 할지 떠오르지 않아 다른 분의 코드를 참고하고 이해하였다.(출처는 코드 밑단에 추가해두었다) 비용을 계산해야 하니 비용을 담을 dp list를 만든다. 그 다음 애초에 불가능한 상담들(퇴사 일자 이후까지 상담이 진행되어야 하는 경우)을 분별해내야 하는데 이는 소요일수를 담은 t list의 값을 참조해 해당 일수 만큼 상담을 진행했을 시 퇴사하는 날을 넘어버리는지를 검사한다. dp에 마지막으로 0을 app..