728x90 Algorithm 썸네일형 리스트형 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 [백준알고리즘] 11066번: 파일 합치기 -Python [백준알고리즘] 11066번: 파일 합치기 -Python https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 추가) 새로 풀어봤다. 밑에 나오는 크누스 최적화를 사용 안 하고 그냥 .. 더보기 [백준알고리즘] 1912번: 연속합 -Python [백준알고리즘] 1912번: 연속합 -Python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2019-08-20 첫 번째 풀이 이번 문제는 LCS에서처럼 뻘짓을 하지 않아서 좀 빨리 풀렸다!!ㅎㅎ 주어진 수열에서 연속하는 부분 수열들 중 최대 합을 구하면 된다. 이번에는 단순히 max만 비교해서 유지했기 때문에 풀면서 딱히 배열을 사용하지 않았다. 풀면서 max_val이라는 전체에서 여태까지 구한 최대합을 나타내는 변수와 tmax라는 max_val을.. 더보기 이전 1 ··· 24 25 26 27 다음