코딩 공부소

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이 문제는 dp를 이용한 문제입니다. 풀이법 이 문제는 전단계의 값들과 자신의 값을 더한 것중 최댓값과 최솟값을 찾으며 비교하는 문제입니다. 푸는 방법은 다음과 같습니다. 1.1번쨰 자리에서 시작할 경우 전단계의 1번째자리와 2번째자리의 값중 최댓값과 최솟값을 찾는다 2.2번째 자리에서 시작할 경우 전단계의 1번째 자리와 2번째 자리, 그리고 3번째 자리중 최댓값 최솟값을 찾는다. 3. 3번째 자리에서 시작할 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 실버 3으로 동적 계획을 사용하는 문제입니다. 풀이 이 문제는 LIS라는 유명한 문제입니다. 왜 동적 배열을 이용하는지, 살펴 봅시다 i 0 1 2 3 4 5 6 A 0 10 20 10 30 20 50 DP 0 이런 표가 있다고 해봅시다 보기 쉽게 i=0일때 경우를 추가해봤습니다. LIS 문제를 푸는 키워드는..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 실버 3이며, 동적할당을 이용해서 푸는 문제입니다 풀이 만약 n이 주어진다면 저 n을 1,2,3의 합으로 나타내는 경우를 모두 구해 주면 됩니다. 처음 생각해보면 꽤 시간이 많이 걸릴것 같지만 푸는 방법만 알면 어렵지 않습니다 동적 계획은 이전에 저장 되어있는 값을 이용해 누적해서 계산해주는 방법입니다. 때문에, 만약 n이 1..3.까지 라고 했을때, dp[1] =1, dp[2]=2, dp[3]= 4입니다. dp[0]은 0으로 둡시다. 0원을 만드는 경우의 수는 없으니까요 그러면 만약 n=4일때..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 실버 1 문제인 오르막 수 입니다. 풀이 1인 경우는 0, 1,2,3,4,5,6,7,8,9로 총 10가지입니다. 이것도 표로 구현해보겠습니다 i)길이가 1인 경우 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 ii)길이가 2인 경우 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1 iii)길이가 3인 경우 0 1 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP(동적계획) 은 점화식이 중요하다. 그렇기 때문에 해당 문제의 규칙을 찾아서 점화식을 세우고 그걸 기반으로 코드를 짜야한다. 예를 들어보자 최대 3종류 사용가능하며 10을 만들어야한다. 그렇다면 먼저 1원을 사용해서 만들수 있는 가치를 살펴보자 i) 1원으로 조합 가능한 경우 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 ii) 1,2원으로 조합 가능한 경우 1 ..