곽의 개발 blog

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

입력

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

문제

https://www.acmicpc.net/problem/1158

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은

<3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

import sys

def Josephus(queue, k ):
    result = list()
    index = k-1
    while queue:
        if(len(queue) > index):
            result.append(queue.pop(index))
            index += k-1
        elif(len(queue) <= index):
            index = index%len(queue)
            result.append(queue.pop(index))
            index += k-1
    return result


if __name__ == "__main__":
    n , k = map(int, input().split())
    queue = list()
    for i in range(1, n+1):
        queue.append(i)
    result = Josephus(queue, k)
    print('<', end='')
    for i in range(n):
        if (i != n-1):
            print(f'{result[i]}, ', end='')
        else:
            print(f'{result[i]}', end = '')
    print('>', end='')

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

import sys
input = sys.stdin.readline

n = int(input())
d = [0]*1000000

for i in range(2, n+1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i-1]+1
    # 현재의 수가 2의 배수
    if i % 2 == 0 :
        d[i] = min(d[i], d[i//2] + 1)
    # 현재의 수가 3의 배수
    if i % 3 == 0 :
        d[i] = min(d[i], d[i//3] + 1)

print(d[n])

분석

10을 구할 때, 9의 결과와 3의 결과를 이용해야 한다.

그 전에 구한 결과값을 저장해두었다가 더 큰 값의 결과를 구할 때 이용하는 방법

3과 2로 나누어떨어지지 않는다면 무조건 -1을 해야한다.

d[i] = d[i-1] + 1 로 계산 횟수 +1을 해준다.

i가 2 와 3으로 나누어 떨어지는 경우에는 dp[i](1을 빼는 경우)와 dp[i // 2or3]+1(나누었을 경우) 중 최솟값을 선택한다.

NEW

동적프로그래밍이란(DP)?

큰 문제를 작은 하위 문제로 나누어 해결함으로써 전체 문제의 최적해를 구하는 것

동일한 하위 문제가 여러 번 발생할 수 있는데 이를 다시 계산하는 것은 비효율적일 수 있다.

기본원리

1. 주어진 문제를 하위 문제로 나눈다.

2. 각 하위 문제의 해결책을 계산하고 기억한다.

3. 상위 문제의 해결책을 계산할 때 필요한 하위 문제의 해결책을 재사용한다.

주로 최적화 문제를 해결하는 데 사용되며, 최단경로문제 / 가장 긴 공통 부분수열 / 베낭 문제 등에 적용

처음에 문제를 봤을 때 동적 프로그래밍으로 풀어야한다는 생각이 정말 1도 들지 않았다.

첫 동적 프로그래밍 문제였어서 그런 것 같다. DP 문제도 많이 풀어봐야 문제를 읽고 DP로 풀어야겠다는 생각이 들겠지?

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

3 5
42101
22100
22101

9

2 2
12
34

1

2 4
1255
3455

4

1 10
1234567890

1

11 10
9785409507
2055103694
0861396761
3073207669
1233049493
2300248968
9769239548
7984130001
1670020095
8894239889
4053971072

49