[알고리즘][백준] 14002번 가장 긴 증가하는 부분 수열 4 - 파이썬(python) 풀이
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 11053번 가장 긴 증가하는 부분 수열의 응용 문제로 부분 수열의 길이 출력에 부분 수열까지 출력하는 문제이다. 이미 앞 문제에서 수열 길이를 max(dp)로 출력하였고 dp에서 1~max(dp)인 순서대로 a 수열에서 뽑아오면 되는 문제이다 import sys n = int(sys.stdin.readline())..
2024. 3. 8.
[알고리즘][백준] 11053번 가장 긴 증가하는 부분 수열 - 파이썬(python) 풀이
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 어려워서 다른분들의 코드를 참고해서 풀었다... import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) dp = [1] * n for i in range(1, n): for j in range(i): if a[i] ..
2024. 3. 7.
[알고리즘][백준] 10844번 쉬운 계단 수 - 파이썬(python) 풀이
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 나의 아이디어는 끝나는 숫자별로 뒤에 올 수 있는 숫자가 한정되어 있어 1 -> 0 2 -> 1, 3 3 -> 2, 4 ... 8 -> 7, 9 9 -> 8 각 숫자로 끝나는 수의 개수로 2차원을 만들어 dp 진행해보았다!! import sys n = int(sys.stdin.readline()) dp = [[0] * 10 for _ in range(101)] # 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 로 끝나는 수의 개수 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] dp[..
2024. 3. 6.
