기타 알고리즘 - 2

1. 더 알아두면 좋은 알고리즘

예제 B - 1. 소수 구하기

난이도 : 🌕🌕

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 <= M <= N <= 1,000,000)
• 단, M 이상 N 이하의 소수가 하나 이상 있는 입력만 주어진다.

출력 조건

• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

입력 예시
3 16

출력 예시
3
5
7
11
13

문제 해설

이 문제는 에라토스테네스의 체 알고리즘을 이용해 쉽게 해결할 수 있다. 가능한 수의 범위가 1부터 1,000,000이기 때문에 초기에 에라토스테네스의 체 알고리즘을 이용하여 1부터 1,000,000까지의 모든 소수를 계산한다. 이후에 M과 N이 입력으로 주어졌을 때, 그사이에 존재하는 모든 자연수에 대하여 소수인지 아닌지 판별하여 출력하면 된다.

문제 답안

import math

# M과 N을 입력받기
m, n = map(int, input().split())
array = [True for i in range(n + 1)] # 처음에는 모든 수가 소수(True)인 것으로 초기화
array[1] = False # 1은 소수가 아님

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우(남은 수인 경우)
        # i를 제외한 i의 모든 배수를 제거하기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

# M부터 N까지의 모드 소수 출력
for i in range(m, n + 1):
    if array[i]:
        print(i)

기출 : 핵심 유형
링크 : https://www.acmicpc.net/problem/1929

예제 B - 2. 암호 만들기

난이도 : 🌕🌕

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

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

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

입력 조건

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

출력 조건

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

입력 예시
4 6
a t c i s w

출력 예시
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

문제 해설

이 문제는 조합 알고리즘 문제 유형에 속한다. 길이가 1인 모든 암호 조합을 확인한 뒤에, 최소 1개의 모음과 최소 2개의 자음이 있는 경우에만 출력하면 된다. 따라서 길이가 1인 모든 암호 조합을 계산하기 위하여 파이썬의 combinations 라이브러리를 이용한다. 그리고 다음 소스코드에서 등장한 join() 내장함수 리스트에 포함되어 있는 문자열들을 새로운 문자열로 합치는 함수이다. 또한 합칠 때, 중간에 문자열을 삽입할 수 있다. 예를 들어 “:”.join([“23”, “59”, “59”])는 “23:59:59”가 된다.

아래 소스코드에서는 단순히 리스트 자료형 형태인 암호(password) 변수를 문자열로 바꾸어 출력하기 위해 사용했다.

문제 답안

from itertools import combinations

vowels = ('a', 'e', 'i', 'o', 'u') # 5개의 모음 정의
l, c = map(int, input().split(' '))

# 가능한 암호를 사전적으로 출력해야 하므로 입력 이후에 정렬 수행
array = input().split(' ')
array.sort()

# 길이가 l인 모든 암호 조합을 확인
for password in combinations(array, l):
    # 패스워드에 포함된 각 문자를 확인하며 모음의 개수를 세기
    count = 0
    for i in password:
        if i in vowels:
            count += 1
    # 최소 1개의 모음과 최소 2개의 자음이 있는 경우 출력
    if count >= 1 and count <= l - 2:
        print(''.join(password))

기출 : 핵심 유형
링크 : https://www.acmicpc.net/problem/1759

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Appendix 카테고리 내 다른 글 보러가기