졍's 기술 블로그

차이를 최대로

티어 : 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

모든 순열

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

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입출력

Algorithm

Back Tracking 이용
1. stack이 비어있으면 숫자 바로 append
2. stack이 비어있지 않으면 stack에 포함되어있지 않은 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 N이 되면 stack print

Code

# 입력
data = list(map(int, input().split()))

# 입력 값 Dictionary에 저장 (key: 입력 값, value: 횟수)
dict_ = {}def back_tracking():
    
    # stack의 길이가 N이 되면 print
    if len(stack) == N:
        print(' '.join(list(map(str, stack))))
    else:
        for num in range(1, N+1):
            # stack 비어있으면 바로 추가
            if not stack:
                stack.append(num)
                back_tracking()
                stack.pop()
            # stack이 비어있지 않으면 stack에 없는 숫자만 append
            elif num not in stack:
                stack.append(num)
                back_tracking()
                stack.pop()
                
N = int(input())
stack = []
back_tracking()
for i in data:
    if i not in dict_:
        dict_[i] = 1
    else:
        dict_[i] += 1

flag = False # 같은 숫자가 있는 경우 False, 모두 다른 경우 True
for key, value in dict_.items():
    if value == 3:
        print(10000 + key * 1000)
        flag = False
        break
    elif value == 2:
        print(1000 + key * 100)
        flag = False
        break
    else:
        flag = True

if flag:
    print(max(dict_.keys()) * 100)

메모리: 30864 KB
시간: 216 ms

카이사르 암호

티어 : Bronze 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 문자열

문제

가이우스 율리우스 카이사르(Gaius Julius Caesar)는 고대 로마 군인이자 정치가였다. 카이사르는 비밀스럽게 편지를 쓸 때, 'A'를 'D로', 'B'를 'E'로, 'C'를 'F'로... 이런 식으로 알파벳 문자를 3개씩 건너뛰어 적었다고 한다.

26개의 대문자 알파벳으로 이루어진 단어를 카이사르 암호 형식으로 3문자를 옮겨 겹치지 않게 나열하여 얻은 카이사르 단어가 있다. 이 카이사르 단어를 원래 단어로 돌려놓는 프로그램을 작성하시오.

각 문자별로 변환 전과 변환 후를 나타낸 건 아래와 같다.

변환전    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
변환후    D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

예를 들어서, 이 방법대로 단어 'JOI'를 카이사르 단어 형식으로 변환한다면 'MRL'을 얻을 수 있고, 앞의 예와 같은 방법으로 얻은 카이사르 단어 'FURDWLD'를 원래 단어로 고치면 'CROATIA'가 된다.

입력

입력은 한 줄로 이루어져 있으며, 그 한 줄에는 대문자 알파벳으로 구성된 단어가 1개 있다. 단어는 최대 1000자 이하이다.

출력

입력받은 카이사르 단어를 원래 단어로 고친 걸 출력하시면 된다.

예제 입출력

Algorithm

1. 카이사르: 원 문자 형태로 Dictionary 만들기
2. 입력을 받아 각 문자의 원 문자가 무엇인지 Dictionary에서 찾기

Code

words = input()
for i in words:
    print(Caesar[i], end = '')

메모리: 30860 KB

시간: 80 ms

Algorithm

1. 단어를 입력받아 각 문자를 리스트에 담음
2. 각 문자의 ASCII 코드 - 3의 글자 출력
    ☞ 문자가 D 이전이면 Z의 ASCII 코드 - 2, -1, -0

Code

words = input()
for i in words:
    if ord(i) < 68:
        print(chr(ord(i)+23), end = '')
    else:
        print(chr(ord(i)-3), end = '')

메모리: 30860 KB
시간: 68 ms

이전 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

예제 입출력

Algorithm

Greedy 이용
1. 입력 순열을 리스트로 받음
2. N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
3. 리스트의 마지막 숫자가 1보다 크면
3.1. 리스트의 끝에서부터 내림차순 정렬되어있는 부분 모두 pop
3.2. 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
4. 리스트의 마지막 숫자가 1이면
4.1. pop하고 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
5. 남은 자리수 stack에 포함되어있지 않은 값으로 채우기

Code

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

# N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
if N == 1 or stack == list(range(1, N+1)):
    print(-1)
else:
    # 리스트의 마지막 숫자가 1보다 크면
    if stack[-1] > 1:
        # 리스트의 끝에서부터 처음으로 가면서 내림차순 정렬되어있는 부분 모두 pop
        for index in range(N-1, 0, -1):
            if stack[index-1] < stack[index]:
                stack.pop()
            else:
                break
        stack.pop()
        
        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)
    else:
        stack.pop()

        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)

    print(' '.join(list(map(str, stack))))

메모리: 30864 KB
시간: 640 ms

소수

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 정수론, 소수 판정

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입출력

Code

# 입력
M = int(input())
N = int(input())

# 소수 찾기
sum_ = 0
min_ = 10000
for i in range(M, N+1):
    count = 0
    if i > 1 and i < 4: # i가 2 또는 3인 경우 소수로 판별
        sum_ += i
        if min_ > i:
            min_ = i
    else: # 그 외의 숫자인 경우
        for j in range(2, i//2 + 1): # 2 ~ i의 절반에 해당하는 숫자까지로 i를 나눠봄
            if i % j == 0: # 나누어 떨어지면 더이상 검사하지 않고 다음 숫자 확인
                break
            else: # 나누어 떨어지지 않는 경우 몇 번 나누어 떨어지지 않았는지 Count
                count += 1
        if count == i//2 - 1: # 나누어 떨어지지 않은 횟수가 j for문을 돈 횟수와 같다면
            sum_ += i # 소수로 판별
            if min_ > i:
                min_ = i
            
if sum_ > 0:
    print(sum_)
    print(min_)
else:
    print(-1)

메모리: 30860 KB
시간: 480 ms

로프

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 192 MB
알고리즘 분류 : 수학, 그리디 알고리즘, 정렬

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 각 로프의 중량을 리스트에 담아 sort
2. 1개 쓸 때부터 N개 쓸 때까지의 최댓값 구하기
    ☞ 각 최댓값은 [N-i] * i

Code

import sys
input = sys.stdin.readline

# 입력
N = int(input())
weights = []
for _ in range(N):
    weights.append(int(input()))

# 중량 리스트 오름차순 정렬
weights.sort()

# 로프 i개 쓸 때부터 N개 쓸 때까지 최댓값 갱신
max_weights = 0
for i in range(1, N+1):
    if max_weights < weights[N-i] * i:
        max_weights = weights[N-i] * i
print(max_weights)

메모리: 34080 KB
시간: 140 ms

다음 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 입력 숫자를 리스트에 받음
2. N이 1이면 -1 출력
3. nums의 마지막 숫자가 N보다 작으면
3.1. 끝에서부터 증가하는 숫자인 경우 모두 pop
3.2. 리스트가 비어있으면 -1 pop
3.3. 리스트가 비어있지 않으면 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
    ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함
4. nums의 마지막 숫자가 N이면
4.1. 2번 pop
4.2. 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
   ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함

Code

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

# 한자리숫자이면 -1 출력
if N == 1:
    print(-1)
# nums의 마지막 숫자가 N보다 작으면 끝에서부터 1씩 증가하는 부분 모두 pop
elif nums[-1] < N:
    for index in range(N-1, 0, -1):
        if nums[index-1] > nums[index]:
            nums.pop()
            # nums의 길이가 1인데 값이 N이면 -1출력
            if len(nums) == 1 and nums[0] == N:
                print(-1)
                break
        else:
            break
    nums.pop()
    # nums가 빈 리스트가 아니면
    if nums:
        # 다음에 올 숫자 저장
        num = (nums[-1] + 1) % (N + 1)
        if num == 0:
            num += 1
        # 이미 포함되어있는 숫자인지 확인
        while num in nums:
            if num in nums:
                num = (num + 1) % (N+1)
        
        nums.pop()
        nums.append(num)
        
        for num in range(1, N+1):
            if num not in nums:
                nums.append(num)
        print(' '.join(list(map(str, nums))))
# nums의 마지막 숫자가 N이면 2번 pop
else:
    nums.pop()
    num = (nums[-1]+1)%(N+1)
    if num == 0:
            num += 1
    # 이미 포함되어있는 숫자인지 확인
    while num in nums:
        if num in nums:
            num = (num + 1) % (N+1)

    nums.pop()
    nums.append(num)

    # 숫자를 1부터 N까지 확인하면서 들어있지 않은 숫자이면 append
    for num in range(1, N+1):
        if num not in nums:
            nums.append(num)
    print(' '.join(list(map(str, nums))))

메모리: 30864 KB
시간: 996 ms