기타 알고리즘

소수 구하기

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

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

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

💡 아이디어
M, N 입력이 최대 1,000,000이기 때문에 소수 판별을 할 때 순차 탐색으로 반복하면 시간 초과를 받을 수 있다.
따라서 아레토스테네스의 체 알고리즘을 이용해야 한다.

문제 풀이

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

void printPrimeNums(bool* primes, int m, int n){
    for (int i = 2; i <= sqrt(n); i++)
    {
        if(primes[i]){
            int j = 2;
            while(1){
                if(i * j > n){
                    break;
                }
                primes[i * j] = false;
                j += 1;
            }
        }
    }
    for (int i = m; i <= n; i++)
    {
        if(primes[i]){
            cout << i << '\n';
            // endl은 출력 버퍼를 지워야 해서 더 느리다.
            // endl을 사용했을 때 시간 초과를 받았다.
        }
    }
}

int main(void) {

    int m, n;
    cin >> m >> n;
    
    bool* prime = new bool[n+1];
    memset(prime, true, sizeof(bool) * (n+1));
    prime[1] = false;

    printPrimeNums(prime, m, n);

    return 0;
}

주의할 점
c++로 답안을 제출할 때, endl 사용 대신 '\n'사용하는 것이 좋다.
endl은 출력 버퍼를 지우는 기능도 있기 때문에 '\n'보다 느리다는
단점이 있어서 시간 초과가 걸린다.

---

암호 만들기

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

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

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

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

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

💡 아이디어

1. 조교의 성향상 알파벳이 오름차순 정렬이 되었기 때문에 받은 문자들을 정렬한다.
2. 중복되는 것이 없기 때문에 조합(Combination)을 이용하여 문자열 조합을 추려낸다.
3. 만들어진 모든 조합에 대해서 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있으면 가능성이 있는 암호 조건을 모두 만족하므로 출력해준다.

문제 풀이

from itertools import combinations

# 모음 정의
mo = {'a', 'e', 'i', 'o', 'u'}

l, c = map(int, input().split())

# 암호를 사전순으로 출력해야 하니까 정렬
arr = input().split(' ')
arr.sort()

# 사전순으로 정렬된 arr를 l 개수에 맞도록 combination 수행
for passwd in combinations(arr, l) :
    cnt_mo = 0
    cnt_ja = 0
    for i in passwd :
        # 조합된 문자열에서 모음 개수 세기
        if i in mo :
            cnt_mo += 1
        # 조합된 문자열에서 자음 개수 세기
        else :
            cnt_ja += 1
    # 최소 한개의 모음, 최소 두개의 자음이 있으면 출력
    if cnt_mo >= 1 and cnt_ja >= 2 :
        print(''.join(passwd))