개발자 퉁이리

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 이번에는 LIS의 길이만 출력하는 것이 아닌 LIS 수열도 출력해야 하는 문제였다. ⊙ 문제 풀이 #include #include #include using namespace std; int n,temp,index,l..

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 ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 슬라이딩 윈도우 ⊙ 문제 접근 과정 그렇게 어렵지는 않은 문제다. 공간 복잡도를 조금만 신경 쓴다면. 메모리 제한이 4MB이기에 공간을 잘 사용해야 한다. 변수를 여러 개 설정해주고 매번 갱신해 공간을 절약하는 방법을 선택했다. 아래 예시를 통해 접근 과정을 알아보자. 3 1 2 3 4 5 6 7 8 9 N=3, 3줄을 입력받는다. 첫 번째 줄은..

www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 다이나믹 프로그래밍 ⊙ 문제 접근 과정 어머나, 문제에 정답이 적혀있다. F(n) = F(n-1) + F(n-2) // (n>=2) 코드로 그대로 옮기자 ⊙ 문제 풀이 #include using namespace std; int def(int n) { if (n==0) { return 0; } else if..

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 3,4개 정도를 직접 풀어보면서 규칙을 찾고 점화식을 만들면 된다. 1-> 1 2-> 2 3-> 4 4-> 7 5-> 13 점화식으로 표현하면 solution(n) = solution(n-1) + solution(n-2)+ solution(n-3) //(n>3) ⊙ 문제 풀이 t= int(input()) def solution(n): if n==1: return 1 elif n==2: return 2 elif ..