[Python] 백준 알고리즘 온라인 저지 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 처음에는 그냥 set으로 중복을 없애고 길이를 출력하는 거라고 생각했다.😅 (그렇게 쉬울 리가 없다고 생각해서 이런 식으로 풀진 않았지만) 수열을 돌면서 더 큰 수가 있다면 큰 순으로 번호를 매긴다고 생각하면 된다. 코드 import sy..
[Python] 백준 알고리즘 온라인 저지 11052 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이번 문제의 핵심은 n장의 카드를 구매하는데 가장 많은 돈(최대 값)을 사용해야 한다는 점이다. 문제를 이해하는 것은 오래 걸리지 않았지만 점화식을 어떤 방식으로 만들어야 하는지 이해하는데 오래 걸렸다. 코드 import sys input = sys.stdin.readline n = int(input()) p = [0] + list(ma..
[Python] 백준 알고리즘 온라인 저지 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726번의 후속 문제로 2x2타일이 추가되었다. 풀이 방법은 11726번 2×n 타일링 파이썬 풀이과 동일하게 동적 계획법과 점화식을 이용하여 풀이하였습니다. 코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 1, 3, 5] for i in range(4, n+1): dp.append..
[Python] 백준 알고리즘 온라인 저지 11726 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP(동적 계획법)과 점화식을 이용하여 풀어야 하는 문제로 먼저 작은 수들의 경우의 수를 구해 이를 활용하여 코드를 작성하였다. 코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 1, 2, 3] for i in range(4, n+1): dp.append((dp[i-1] + (dp[..
[Python] 백준 알고리즘 온라인 저지 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법을 이용해 풀어야 하는 문제로 재귀 같은 경우도 어렵다고 느꼈지만 이번 문제도 어렵다고 느꼈다. 3이나 2로 나눠지면 나누거나 1을 빼서 1로 만드는 최소한의 경우의 수를 구해야 하는 문제였다. 이 문제에서 DP를 사용하는 이유는 이전 경우의 수들의 값을 이용하기 위해 계산결과를 저장하고 그 값을 이용하기 위함이다. 코드 import sys import math input = sys.stdin.readline def dp(): x = i..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
