[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..
[Python] 백준 알고리즘 온라인 저지 9093 단어 뒤집기 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문제 난이도는 낮은 편으로 문자열의 순서는 바꾸지 않고 내용을 거꾸로 뒤집기만 해야 하는 문제였다. reversed와 join을 적절히 사용해야 했다. 코드 import sys input = sys.stdin.readline n = int(input()) words_lists = [list(input().split()) for..
[Python] 백준 알고리즘 온라인 저지 10828 스택 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택의 개념을 이용하여 풀이하는 문제로 5가지 명령을 이용해 자료를 컨트롤하는 방법에 대한 알고리즘이다. 시간제한이 짧은 문제로 sys모듈을 사용하였고 이를 이용하다 문제점을 발견하여 수정하였다. 코드 import sys input = sys.stdin.readline # 5가지 명령 def push(x): stack.a..
[Python] 백준 알고리즘 온라인 저지 18870 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제를 간단하게 설명하자면 좌표를 크기 순으로 0부터 나열하여 같은 좌표는 같은 수를 출력하도록 하는 문제이다. 예를 들면 (5, 6, 7, 8, 5) 를 입력받으면 크기대로 (0, 1, 2, 3, 0)을 출력하면 된다. 코드 import sys input = sys.stdin.rea..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
