졍's 기술 블로그

모든 순열

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

숫자의 개수

티어 : Bronze 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다.

출력

첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

예제 입출력

Code

A = int(input())
B = int(input())
C = int(input())

num = str(A*B*C)
count = [0 for _ in range(10)]
for i in range(len(num)):
    count[int(num[i])] += 1

for i in count:
    print(i)

메모리: 29200 KB
시간: 72 ms

회의실 배정

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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은

보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입출력

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

Algorithm

Greedy
1. 리스트로 입력받아 끝나는 시간을 기준으로 오름차순 정렬
2. stack에 첫 번째 회의 추가
3. stack의 마지막 회의의 끝나는 시간보다 시작 시간이 크거나 같은 회의만 추가
4. stack의 길이 출력

Code

import sys
input = sys.stdin.readline
    
# 입력
N = int(input())
I = []
for _ in range(N):
    I.append(tuple(map(int, input().split())))
    
# 시작 시간, 회의 시간 순서대로 기준을 잡아 정렬
I.sort(key = lambda x: (x[1], x[0]))

# 회의 시작 시간이 이전 회의 끝나는 시간보다 크거나 같으면 추가
stack = [I[0]]
for index in range(1, N):
    if I[index][0] >= stack[-1][1]:
        stack.append(I[index])
print(len(stack))

메모리: 51636 KB
시간: 4420 ms