[BOJ/백준] 14002 가장 긴 증가하는 부분 수열 4
● [문제번호 14002] 가장 긴 증가하는 부분 수열 4 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 ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 : Longest Increasing Subsequence ● 풀이 과정 : 기존 [11053 가장 긴 증가하는 부분 수열]의 문제에서 해당 수열을 출력하는 것이다. 그래서 부분 수열..
2021. 7. 30.
[BOJ/백준] 11053 가장 긴 증가하는 부분 수열
● [문제번호 11053] 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 : Longest Increasing Subsequence ● 풀이 과정 : 시간복잡도가 O( N^2 ) 인데 더 줄일 수 없는 방법을 고민하다가 일단 채점했는데 통과되었다. : DP의 풀이..
2021. 7. 30.
[BOJ/백준] 15990 1, 2, 3 더하기 5
● [문제번호 15990] 1, 2, 3 더하기 5 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : DP의 풀이과정 (Bottom-Up) 1. 테이블 정의하기 → end1 : index를 만드는데 마지막으로 추가한 숫자가 1인 경우 → end2 : index를 만드는데 마지막으로 추가한 숫자가 2인 경우 → end3 : index를 만드는데 마지막으로 추가한 숫자가 3인 경우 2. 점화식 찾기 → end..
2021. 7. 30.
