졍's 기술 블로그

1로 만들기

티어 : Silver 3
시간 제한 : 0.15 초 (Python3 1.5 초)
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고,

보다 작거나 같은 정수 N이 주어진다.

출력

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

예제 입출력

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

Algorithm

Dynamic Programming
1. dp table을 N+1 까지 생성
2. dp[1]은 0, dp[2], dp[3]은 1로 초기화
3. 4부터 N+1까지 검사하면서 dp[num]을 최솟값으로 초기화
3.1. 3으로 나누어떨어지는 경우 dp[num]을 dp[num//3]과 dp[num] 중 최솟값으로 갱신
3.2. 2로 나누어떨어지는 경우 dp[num]을 dp[num//2]와 dp[num] 중 최솟값으로 갱신
3.3. dp[num]을 dp[num-1]과 dp[num] 중 최솟값으로 갱신
3.4. dp[num]에 + 1
4. dp[N] 출력

Code

N = int(input())
dp = [10**6] * (N+1)
dp[1] = 0
if N > 1:
    dp[2] = 1
if N > 2:
    dp[3] = 1

value = 10**6
for num in range(4, N+1):

    # 3으로 나누어떨어지면 index 3 이전의 값과 index 1 이전의 값 중 최솟값 갱시
    if num % 3 == 0:
        dp[num] = min(dp[num], dp[num//3])
    # 2로 나누어떨어지면 index 2 이전의 값과 index 1 이전의 값 중 최솟값 갱신
    if num % 2 == 0:
        dp[num] = min(dp[num], dp[num//2])
    # index 1 이전의 값과 value 중 최솟값 갱
    dp[num] = min(dp[num], dp[num-1])
    dp[num] += 1
print(dp[N])

메모리: 38652 KB
시간: 892 ms

부분수열의 합

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입출력

Algorithm

Back Tracking
1. stack에 수열의 숫자 하나씩 추가
1.1. stack이 비어있으면 바로 append
1.2. stack이 비어있지 않으면 stack의 마지막 숫자보다 큰 숫자만 추가
2. stack 원소의 합이 S가 되면 ANSWER 1 증가
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 N이 되면 바로 append하지 못하도록 구현

Code

def back_tracking(sum_):
    global answer
    
    # stack 길이가 N이 되면 POP먼저 하도록 구현
    if len(stack) == N:
        pass
    else:
        for idx in range(N):
            # stack 비어있으면 바로 append
            if not stack:
                stack.append(idx)
                sum_ += list_[idx]
                if sum_ == S:
                    answer += 1
                back_tracking(sum_)
                stack.pop()
                sum_ -= list_[idx]
                
            # stack 비어있지 않으면 들어있지 않은 숫자만 추가
            elif stack[-1] < idx:
                stack.append(idx)
                sum_ += list_[idx]
                if sum_ == S:
                    answer += 1
                back_tracking(sum_)
                stack.pop()
                sum_ -= list_[idx]
                
N, S = map(int, input().split())
list_ = list(map(int, input().split()))

global answer
answer = 0
sum_ = 0
stack = []
back_tracking(sum_)
print(answer)

메모리: 30840 KB
시간: 1936 ms

집합

티어 : Silver 5
시간 제한 : 1.5 초
메모리 제한 : 4 MB
알고리즘 분류 : 구편, 비트마스킹

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입출력

Algorithm

구현 - Simulation
문제에 따라서 진행

Code

import sys
input = sys.stdin.readline

M = int(input())
S = []
for _ in range(M):
    orders = input().rstrip()
    
    # add x 이면 S에 x 추가
    if orders[:3] == 'add':
        order, x = orders.split()
        # S에 이미 x가 있는 경우 연산 무시
        if int(x) in S:
            continue
        S.append(int(x))
    
    # remove x : S에서 x를 제거
    elif orders[:6] == 'remove':
        order, x = orders.split()
        # S에 x가 없는 경우 연산 무시
        if int(x) not in S:
            continue
        S.remove(int(x))
    
    # check x : S에 x가 있으면 1, 없으면 0 반환
    elif orders[:5] == 'check':
        order, x = orders.split()
        if  int(x) in S:
            print(1)
        else:
            print(0)
            
    # toggle x : S에 x가 있으면 x 제거, 없으면 x 추가
    elif orders[:6] == 'toggle':
        order, x = orders.split()
        if int(x) in S:
            S.remove(int(x))
        else:
            S.append(int(x))
            
    # all : S를 {1, 2, ... , 20}으로 변환
    elif orders == 'all':
        S = list(range(1, 21))
    
    # empty : S를 공집합으로 변경
    elif orders == 'empty':
        S = []

메모리: 30840 KB
시간: 4428 ms

로또

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 조합론, 백트래킹, 재귀

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. 입력받은 수를 리스트로 저장
2. 리스트에 들어있는 숫자를 stack에 append
2.1. stack이 비어있으면 숫자 바로 추가
2.2. stack이 비어있지 않으면 stack의 마지막 숫자보다 큰 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 stack pop
5. stack의 길이가 6이 되면 print

Code

def back_tracking():
    
    # stack의 길이가 6이 되면 print
    if len(stack) == 6:
        print(' '.join(list(map(str, stack))))
    else:
        for index in range(1, nums[0]+1):
            # stack 비어있으면 숫자 바로 추가
            if not stack:
                stack.append(nums[index])
                back_tracking()
                stack.pop()
            elif nums[index] > stack[-1]:
                stack.append(nums[index])
                back_tracking()
                stack.pop()

while True:
    nums = list(map(int, input().split()))
    if nums[0] == 0:
        break
    stack = []
    back_tracking()
    print()

메모리: 30840 KB
시간: 76 ms

외판원 순회 2

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹, 외판원 순회 문제

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. 입력으로 리스트로 저장해 graph 구현
2. stack에 값 추가
2.1. stack이 비어있으면 현재 숫자 바로 추가
2.2. stack이 비어있지 않으면 stack에 들어있지 않으면서 비용이 0 이상인 값만 추가
3. 재귀함수 호출
4. 재귀함수 호출되면 stack pop
5. stack의 길이가 N이 되면 시작지점으로 돌아올 수 있는지(비용이 0 이상인지) 확인
5.1. 시작지점으로 돌아올 수 있다면 최소비용 갱신

Code

def back_tracking(costs):
    global answer
    
    # stack의 길이가 N-1이 되면
    if len(stack) == N:
        # 시작지점으로 돌아올 수 있으면 최소 비용 갱신
        if graph[stack[-1]][stack[0]] > 0:
            costs += graph[stack[-1]][stack[0]]
            if answer > costs:
                answer = costs

    else:
        for num in range(N):
            # stack이 비어있으면
            if not stack:
                if num == 1:
                    return
                # 그냥 추가
                stack.append(num)
                back_tracking(costs)
                stack.pop()
            # stack이 비어있지 않으면 stack에 들어있지 않으면서 비용이 0 이상인 값만 추가
            elif num not in stack and graph[stack[-1]][num] > 0:
                stack.append(num)
                costs += graph[stack[-2]][stack[-1]]
                back_tracking(costs)
                costs -= graph[stack[-2]][stack[-1]]
                stack.pop()
                
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

global answer
answer = 1000000*N*N
stack = []
costs = 0
back_tracking(costs)
if answer == 1000000*N*N:
    print(0)
else:
    print(answer)

메모리: 30840 KB
시간: 1360 ms

촌수계산

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

예제 입출력

Code

from collections import deque

n = int(input())
start, end = map(int, input().split())
m = int(input())
graph = []
visited = []
for i in range(n+1):
    graph.append([])
    visited.append(0)
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    if x not in graph[y]:
        graph[y].append(x)
        
def bfs(start, end):
    queue = deque([start])
    
    while queue:
        now = queue.popleft()
        
        for i in graph[now]: # 인접한 노드를 모두 돌면서
            if visited[i] == 0: # 한 번도 접근한 적 없다면
                queue.append(i) # 큐에 모두 추가
                visited[i] = visited[now] + 1 # 방문 기록
        
        if visited[end] > 0: # 마지막 노드 값이 갱신되면 return
            return visited[end]
        
    if visited[end] == 0: # while문을 다 돌았는데도 마지막 노드 값이 갱신되지 않았다면
        return -1 # -1 return
    
print(bfs(start, end))

메모리: 32404 KB
시간: 96 ms

차이를 최대로

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. stack에 포함되어있지 않은 index append
2. 재귀함수 호출
3. 재귀함수 return되면 pop
4. stack의 길이가 N이 되면 식의 최댓값 갱신

Code

def back_tracking():
    global answer
    
    # stack의 길이가 N이 되면 식의 최댓값 갱신
    if len(stack) == N:
        sum_ = 0
        for idx in range(1, N):
            sum_ += abs(nums[stack[idx-1]] - nums[stack[idx]])
        if answer < sum_:
            answer = sum_
    else:
        for index in range(N):
            if index not in stack:
                stack.append(index)
                back_tracking()
                stack.pop()
                
N = int(input())
nums = list(map(int, input().split()))

global answer
answer = 0
stack = []
back_tracking()
print(answer)

메모리: 30864 KB
시간: 200 ms

바이러스

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

예제 입출력

Code

# BFS
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어있는 컴퓨터 쌍의 수

graph = []
visited = [False] * (N+1)
for i in range(N+1):
    graph.append([])
    
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    if i not in graph[j]:
        graph[j].append(i)
    
# BFS
from collections import deque

def bfs(start):
    queue = deque([start])
      
    while queue:
        now = queue.popleft()
        # 현재 컴퓨터 방문 처리
        visited[now] = True
            
        # 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 Queue에 삽입하고 방문처리
        for i in graph[now]:
            if not visited[i]:
                queue.append(i)

bfs(1)

count = -1
for i in visited: # 방문한 노드 수 세기
    if i:
        count += 1
print(count)

메모리: 30864 KB
시간: 80 ms

Code

# DFS
N = int(input()) # 컴퓨터 수
M = int(input()) # 네트워크 상에서 직접 연결되어있는 컴퓨터 쌍의 수

graph = []
visited = [False] * (N+1)
for i in range(N+1):
    graph.append([])
    
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    if i not in graph[j]:
        graph[j].append(i)
    
# DFS
def dfs(n):
    # 현재 컴퓨터 방문 처리
    visited[n] = True
    # 연결되어있는 컴퓨터 하나씩 방문
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

dfs(1)

count = -1
for i in visited: # 방문한 노드 수 세기
    if i:
        count += 1
print(count)

메모리: 30864 KB
시간: 100 ms