Algorithm Theory/Dynamic Programming10 [DP] [BOJ 1463] 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 어떤 자연수 N에 대해서 세 가지의 연산을 할 수 있다. 1. 3으로 나누어 떨어지면 나눈다. 2. 2로 나누어 떨어지면 나눈다. 3. 1을 뺀다. 임의의 자연수는 이 연산을 반복할 경우 1로 만들 수 있다. 어떤 자연수 N에 대해서, 1로 만들기 위한 연산의 최소 횟수를 구하는 문제. 무식하게 접근하기 우선 가장 무식한 방법은 모든 숫자에 대해서 세 가지 연산을 해보는 것이다. 하지만, 각각의 숫자에 대해서 최대 3개의 연산을 할 수 있으므로, 시간복잡도는 $O(3^N)$가 된다. 근데 N = 100,000이므로 절대로 풀 수가 없다. 제출해보니 메모리 초과가 뜬다. .. 2020. 3. 18. DP 백준 문제 풀이 문제 리스트 다이나믹 프로그래밍 - 1 페이지 다이나믹 프로그래밍 www.acmicpc.net 1. 1로 만들기 2. 1, 2, 3 더하기 2020. 3. 18. 동적 프로그래밍(Dynamic Programming)의 개념 DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다. Dynamic Programming 동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다. 위의 코드를 한 번 읽어보자. 1 = 1 2 = 2 + 1 3 = 3 + 2 + 1 ... 100 = 100 + 99 + 98 + ... + 3 + 2 + 1 이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므.. 2019. 10. 7. [백준] 9251번 LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제를 풀기 전에 알아야 할 개념 : Dynamic Programming LCS란? LCS란 두 문자열 str1과 str2가 있다고 할 때, 공통된(Common) 부분 수열(Substring) 중, 가장 긴 것(Longest)을 의미한다. 여기서 Subsequence의 개념을 명확히 할 필요가 있는데, 원래 문자열의 글자를 몇 개 선택해서 원래 문자.. 2019. 10. 6. 이전 1 2 다음