11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net {8, 2 , 3 , 4} 라는 수열이 있다고 하자. 여기서 가장 긴 증가하는 부분수열을 구하면 {2,3,4}이다. 처음 접근법으로는 단순하게 전수조사했다. {8,2,3,4}라는 수열이 있을때 먼저 8을 선택한 경우와 그렇지 않을 경우를 나눈다. 8을 선택하고 다음으로 가면 2가 있는데 2는 8보다 작으므로 선택할수 없다. 따라서 바로 3으로 넘어가도록 했다. 이런식으로 가장 마지막에 ..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Dynamic Programming을 통해 풀어야하는 문제. 재귀를 통해 정답은 맞출수 있으나, 메모이제이션을 하지 않으면 시간초과가 발생한다. ( 중복된 연산을 제거해야한다 ) 입력으로 10이 주어졌을때 수행방식을 작성해보면 다음과 같다. 여기서 f(n)은 n을 1로만드는 최소 연산횟수. 10이 들어왔을떄 3으로 나눌수 있는지 확인했는데 불가능하다. 그렇기 때문에 나누기2와 빼기1 연산만 수행했다. f(10) = f(5)와 f(9)의 결과중 작은값 + 1 f(10) = min( f(5) , f(1) ) + 1 이므로 f(5) 와 f(1)을 구해야한다. 위의 개념을 코드화 하..