졍's 기술 블로그

로또

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

이전 순열

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

암호 만들기

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 조합론, 백트래킹

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입출력

Algorithm

back tracking - 재귀
1. 입력받은 문자열을 리스트로 저장해 오름차순 정렬
2. stack에 들어있지 않은 문자열 append
3. stack의 길이가 L이 되면 stack 안에 모음이 1개 이상, 자음이 2개 이상 포함되어있는 것만 출력

Code

def back_tracking():
    
    # stack의 길이가 L이 되면
    if len(stack) == L:
        # stack 안에 모음과 자음 개수 확인
        vowel = 0 # 모음
        consonant = 0 # 자음
        for word in stack:
            if word in ['a', 'e', 'i', 'o', 'u']:
                vowel += 1
            else:
                consonant += 1
                
        # stack 안에 모음 1개 이상, 자음 2개 이상 포함되어있으면 출력
        if vowel > 0 and consonant > 1:
            print(''.join(stack))
    else:
        for word in words:
            # stack이 비어있으면
            if not stack:
                # 바로 append
                stack.append(word)
                back_tracking()
                stack.pop()
            # stack 비어있지 않으면 satck에 없고 stack의 마지막 원소보다 큰 알파벳만 저장
            elif word not in stack and word > stack[-1]:
                stack.append(word)
                back_tracking()
                stack.pop()
                
L, C = map(int, input().split())
words = list(input().split())
words.sort()

stack = []
back_tracking()

메모리: 30864 KB
시간: 148 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

이항 계수 1

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

문제

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

입력

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

출력

\(\binom{N}{K}\)를 출력한다.

예제 입출력

이항 계수(Binomial Coefficient)
조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 가짓수

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔

Code

# 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!
print(num1 // num2)

메모리: 30864 KB
시간: 72 ms