dev study-log

한동안 여행을 다녀와서 문제를 풀지 못해 업로드 하지 못했다.. 이번 문제는 다이나믹 프로그래밍 연습 겸 해서 풀어봤다. 상당히 쉬운 문제였다. https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 해석: 이번 문제는 동전 1과 비슷한 문제이지만 최소로 사용되는 동전의 수를 구하면 되는 문제이다. 최소로 동전을 사용하여 어 떤 값을 만들려면 최솟값에 최솟값을 더하여 만들면 자연스레 최솟값이 될 것이다. 이러한 관점..

이 문제는 오랜만에 푼 실버 문제이다. 동적계획법 연습겸해서 풀어봤다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해석: 이 문제는 계단 수의 갯수를 구하는 문제이다. 계단 수란 각각의 자리에서 인접한 수가 1씩만 차이가 나는 수를 말한다. 이 말인 즉, 인접한 수는 +1 혹은 -1을 해야한다는 의미이다. 이런 과정을 거치려면 길이가 1인 계단 수에서 각각 +1, -1 한 수 를 뒤에 붙여주면 길이가 2인 계단 수가 완성되는데 앞에는 수 0이 오면 안되고 9에서는 +1이 불가능하므로 만약 0이 뒤에 붙으면 그 다음 길이의 계단 수에서 뒤에는 무조건..

이번 문제는 DP 연습 겸 해서 풀어본 문제이다. 이 문제와 연관된 문제들도 풀어볼 예정이다. https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석: 문제는 LCS (Longest Common Sequence)와 비슷하고 다른 여타 순열 문제와 마찬가지로 동적 계획법(Dyanamic Programming. 이하 DP)로 풀어나가는 문제이다. 문제에서 주어진 수열의 최대 길이는 1,000으로 비교적 작은 편에 속하므 로 모든 경우의 수를 탐색해도 1초 안에 충..

역시 학교 수업은 제대로 들어야겠다는 교훈을 얻은 알고리즘이다. 문제해결기법이라는 강의가 있었는데 그 강의 시간에 교수님께서 설명해주신 방법대로 풀면 바로 풀리는 쉬운 문제였다. 물론 처음에는 조금 돌긴 했지만 이내 금방 길을 찾을 수 있었다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 익히들 알고 있을 수도 있고 유명한 knapsack problem이다. 그런데..