[Python] 백준 알고리즘 온라인 저지 1874 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제를 이해하는데 시간이 좀 걸렸다. n값을 받고 수를 차례대로 입력할 때 입력한 수까지 스택에 넣었다가 그 수를 빼서 입력받는 수열을 만들 수 있는지 출력하는 문제로 중복으로 스택에 추가되지 않는다는 점을 신경 써야 한다. 예를 들면 n = 5 (3, ..
[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..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
