졍's 기술 블로그

가장 긴 감소하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열을 이용
dp[i] : i번째 원소를 마지막으로 하는 부분 증가수열의 길이
1. 입력 받는 수열을 reverse
2. 가장 긴 증가하는 부분 수열 찾기

Code

N = int(input())
A = list(map(int, input().split()))

# 수열 reverse
A.reverse()

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30864 KB
시간: 196 ms

가장 긴 증가하는 부분 수열

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입출력

Algorithm

dp[i] : i 번째 원소를 마지막으로 하는 부분 증가 수열의 최대 길이
1. 리스트를 이중 for문으로 돌면서 자신보다 작은 index에 값이 작은 수가 몇 개 있는지 확인
    ➝ i : 1 ~ N-1, j : 0 ~ i
2. j번째 원소가 i번째 원소보다 작으면 i번째 dp Table의 값과 j번째 dp Table의 값 + 1 중 큰 값으로 dp Table 갱신

Code

N = int(input())
A = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N):
  for j in range(i):
    if A[j] < A[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

메모리: 30860 KB
시간: 200 ms

1, 2, 3 더하기

티어 : Silver 3
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입출력

Algorithm

dp[i] : 1, 2, 3의 합으로 i를 만들 수 있는 개수
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

Code

T = int(input())
for _ in range(T):
  n = int(input())

  dp = [0]*(11)
  dp[1] = 1
  dp[2] = 2
  dp[3] = 4
  for i in range(4, n+1):
    dp[i] = dp[i-3]+dp[i-2]+dp[i-1]
  

  print(dp[n])

메모리: 30860 KB
시간: 72 ms

다리 놓기

티어 : Silver 5
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예제 입출력

Algorithm

1. nCk 조합 계산 :  n! // (k! * (n-k)!)   
    ☞ M 개 중에 N개를 골라서 다리를 놔야하기 때문

Code

def factorial(num):
    if num < 2:
        return 1
    else:
        return num * factorial(num-1)

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    print(factorial(M) // (factorial(N) * factorial(M - N)))

메모리: 30860 KB
시간: 112 ms

이항 계수 2

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

예제 입출력

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔
4. 3번의 결과를 10007로 나눈 나머지 출력

Code

import sys
sys.setrecursionlimit(10 ** 6)

# Factorial 계산하는 함수
def factorial(K):
    if K < 2:
        return 1
    else:
        return K*factorial(K-1)
    
# 입력
N, K = map(int, input().split())

# N * N-1 * ...
num1 = 1
for i in range(K):
    num1 *= N-i
    
# K!
num2 = factorial(K)

# (N * N-1 * ... // K!) % 10007
print((num1 // num2) % 10007)

메모리: 31324 KB
시간: 72 ms