[Python] 백준 알고리즘 온라인 저지 11057 오르막 수 출처 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 자릿수가 오름차순으로 증가하는 수를 오르막 수라고 하고 이전이나 다음 자릿수는 같은 크기를 가져도 오르막 수이다. 점화식을 찾아 문제를 풀이해야 했고 그 과정이 생각보다 오래 걸렸다. N과 끝으로 오는 수를 기준으로 점화식을 세워야 한다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import..
[Python] 백준 알고리즘 온라인 저지 14490 백대열 출처 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 저번 포스트에 작성한 알고리즘과 비슷한 분류이다. 최대공약수를 구해야 하는 문제로 두 수를 약분하여 출력하면 된다. math.gcd 라이브러리를 활용하는 방법은 전 포스트를 확인하시면 됩니다. - 이전 발행 글보기 알고리즘 분류 수학 문자열 정수론 파싱 유클리드 호제법 소스코드 n, m = map(int, input().split(':')) def gcd(a, b): if b == 0: return a return gcd(b, a%b) t ..
[Python] 백준 알고리즘 온라인 저지 1309 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이번 문제도 다이내믹 프로그래밍을 이용해 경우의 수를 계산하는 문제로 주의할 점은 사자가 없는 경우도 경우의 수로 계산한다는 점이었다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 3, 7] + [0] * (n - 2) for i in range(3, n+1): dp[i] = (dp[i-2]+(dp[i-1] * 2)) % 9901 print(dp[n]) 풀이 점..
[Python] 백준 알고리즘 온라인 저지 1149 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이전의 집과 색이 같지 않고, 다음 집의 색이 같지 않아야 한다. 이 조건을 만족하며 비용의 최솟값 또한 고려해야 한다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline n = int(input()) RGB = [list(map(int, input()...
[Python] 백준 알고리즘 온라인 저지 15988 1, 2, 3 더하기 3 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 정수 n을 1, 2, 3의 합으로 표현해야 한다. 표현하는 방법이 어느 정도 규칙적인 것 같아 규칙을 찾아 풀이하기로 했다. 알고리즘 분류 다이내믹 프로그래밍 소스코드 import sys input = sys.stdin.readline dp = [1,2,4,7] for i in range(int(input())): n = int(input()) for j in range..
[Python] 백준 알고리즘 온라인 저지 2693 N번째 큰 수 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 처음 문제를 접했을 땐 순열로 출력하면 되겠다고 생각하였다. 백트래킹 알고리즘을 잘 알지 못해 같이 소개하며 두 가지 방법 모두 풀이해보려고 한다. 알고리즘 분류 백트래킹 소스코드 1 (permutation) from itertools import permutations n, m = map(int, input().split()) ..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
