[BOJ] 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 사고과정 아무거나 수열 출력하는 부분에서 매우 고생했다.. 오히려 문제의 난이도가 여기에서 올라가는 것 같다.. 반례에 자꾸 걸려서 구글링을 했는데 구글링한 것 중에서도 간결한 코드를 찾기가 쉽지 않았다. 그러던 중 하나의 훌륭한 블로그 글을 발견하고! 해당 풀이를 참조했다!(감사합니다 :) 풀이(스스로 못..
[BOJ] 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 사고과정 이전에 이코테 문제에서 풀어본 병사 배치하기 문제를 통해서 LIS(가장 긴 증가하는 부분 수열) 알고리즘에 대해 배웠었다. git 팀 노트에 적어놓긴 했었지만 다시 회상할 겸 소스코드를 보지 않고 직접 머릿속으로 구현하려 했다. LIS 알고리즘 개념은 여기를 참고하자. 풀이 a = int(input()..
[BOJ] 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 사고과정 저번 1,2,3 더하기 문제와 난이도가 매우 달랐던 것 같다.. DP 테이블을 1차원으로 정의하고 어떻게든 규칙을 찾아보려 했지만 실패했다. 핵심 풀이는 2차원으로 DP 테이블을 운영하는 것이었고 또 하나는 다이나믹 프로그래밍의 핵심인 "뒤의 입장에서 생각" 하기 였다. 어떤 뒤의 입장이냐.. 바로 1, 2, 3 합으로만 이루어진 것을 찾는 것이므로 특정한 수 n을 1, 2, 3의 합으로 만들 때, 그 연산에 사용된 마지막 피연산..
