MingyuPark

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 아이디어 P(N) = P(N-5) + P(N-1)로 나타낼 수 있다. P(N)의 값을 저장해놓고 사용하면 메모리를 절약할 수 있다. 이 때, P(5)까지는 직접 입력해주고 P(6)부터는 점화식으로 표현할 수 있다. Solution t = int(input()) cache = [0 for _ in range(101)] cache[1] = 1 cache[2] = 1 cache[3] = 1 cache[..

문제 11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 아이디어 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 f(n)이라고 하면 이를 점화식으로 표현할 수 있다. f(1) = 1, f(2) = 2이다. n이 3 이상인 경우 f(n) = f(n-1) + f(n-2)로 표현할 수 있다. f(4) = f(3) + f(2) = {f(2) + f(1)} + f(2) 와 같은 방식으로 계산이 진행되기 때문에 recursive call을 이용하면 메모리가 낭비될 수 있다..

문제 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 아이디어 단순 구현이다. deque를 통해 큐를 구현하고, 조건에 맞춰서 명령을 처리하도록 하면 된다. 난이도는 높지 않고, 주어진 조건을 정확하게 구현하는 게 중요하다. 한 가지 주의할 점은 여러 줄에 걸쳐서 입력을 받기 때문에 input()을 통해서 입력을 받게 되면 시간 초과가 발생할 수 있다. 이런 경우 입력의 개수 T는 input을 통해 받아도 상관이 없지만..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 아이디어 동쪽(M개)의 사이트에서 서쪽(N개)의 사이트를 선택하는 문제로 간단한 조합 문제이다. 조합을 이용하면 쉽게 해결할 수 있다. 아이디어 자체는 어렵지 않았고 조합을 구현할 때 factorial, combination을 직접 구현해보고, 모듈을 이용해서도 풀어봤다. Solution 1. factorial을 직접 구현 def factorial(n) : num = 1 for i in ra..