Ray`s Tech Lab

https://www.acmicpc.net/problem/1759

무식하게 풀어본다면 어떻게 풀 수 있을지 어림짐작을 하려고 했는데, 못 했다. 어떻게해서 풀 수 있을지는 구상이 되는데, 그 방법을 토대로 어떻게 어림짐작을 할 수 있을지를 모르겠었다. 직관적으로 떠오른 방법은 주어진 알파벳들을 자음과 모음들로 구분하고, 자음에서는 2개 이상을 고르는 모든 조합, 모음에서는 1개 이상을 고르는 모든 조합을 서로 매핑시켜서 암호를 만드는 것이었다. 일단 떠오르는 무식한 방법(비단 브루트포스 방식이 아니더라도)에 대한 어림짐작이 잘 안되면 일단 그 방법으로 풀어보는 것도 하나의 방법이라고 한다.

파이썬에서는 순열/조합에 관해서 쓸 수 있는 편리한 라이브러리가 있다.  이를 활용하기로 했으며, 코드는 다음과 같다.

from itertools import combinations
import sys

L, C = map(int, sys.stdin.readline().split())

# data[0] = 자음, data[1] = 모음
data = [list(map(str, sys.stdin.readline().split())), []]
password_list = []
# 자음 모음 분리 .
for ch in ['a', 'e', 'i', 'o', 'u']:
    if ch in data[0]:
        data[1].append(ch)
        data[0].remove(ch)

# 주어진 알파벳들로 암호를 만들 수 있을 경우는 자음이 2개, 모음이 1개 이상인 경우
if len(data[0]) >= 2 and len(data[1]) >= 1: 

    # i는 모음의 개수를 의미
    for i in range(1, len(data[1]) + 1):
        if L - i >= 2:
            vowels = list(combinations(data[1], i)) # 가능한 모든 모음의 조합
            consos = list(combinations(data[0], L - i)) # 그로부터 생기는 가능한 모든 자음의 조합
            for v in vowels:
                for c in consos:
                    # 모음의 조합과 자음의 조합들을 합쳐 비밀번호만들기
                    password = ''.join(sorted(list(v + c)))
                    password_list.append(password)

    # 비밀번호들 사전순 정렬
    password_list.sort()

    for i in password_list:
        print(i)

모음은 총 5개까지 고를 수 있는데, 주어지는 알파벳들이 중복되어 주어지는 것이 없다고 했으므로 모음은 0개 ~ 5개까지 있을 것이다. 따라서 자음 / 모음을 분리했을 때 모음이 1개 이상, 자음이 2개 이상 있어야지 암호를 만들 수 있으므로 이에 대한 예외처리를 해준다. 

combinations()의 파라미터로 첫 번째는 반복 가능한 것(배열처럼), 두 번째는 요소의 개수를 넣어주면 첫 번째로 받은 반복 가능한 객체에서 두 번째 파라미터로 받은 개수만큼의 조합을 튜플 형태들로 반환해준다. 주어진 알파벳들로 L글자의 암호를 만든다고 할 때, 모음의 개수를 정했다면 자음의 개수는 L - 모음의 개수이므로 이를 활용해 가능한 모음의 조합과 자음의 조합들을 만들어주고 이들을 합치고 정렬하여 알파벳 순서로 된 비밀번호를 만드는 식으로 코드를 짰다.

24번째 줄, if L - i >= 2를 처음엔 넣어주지 않아 틀렸다고 나왔다. 자음은 2개 이상, 모음이 1개 이상 있어도 모음의 개수에 따라 암호를 못 만들 수도 있는 상황이 있음을 간과한 것이었다. 예를 들어 자음이 3개, 모음이 3개 있을 때 4글자짜리 암호를 만들라고 했다고 하자. 자음이 2개 이상 모음은 1개 이상있는 상황이니 비밀번호를 아예 못 만드는 상황은 아니지만, 모음이 3개인 비밀번호는 만들 수 없다! 이 경우 자음은 1개만 써야 4글자짜리 비번을 만들 수 있는데, 문제의 조건 상 자음은 2개 이상 써야 하기 때문이다. 즉 이에 대한 예외처리를 해줘야했다. 

브루트포스 알고리즘은 사실 설명하기 민망할 수 있을 정도로 직관적이다. 가능한 모든 경우를 따져가며 답을 찾는 방식. 따라서 시간만 충분하다면 이 방식으로 찾은 답은 정답임이 보장된다. 모든 경우를 다 따져본 거니까..

ex - 1) 1부터 N까지의 합은?

: 무식하게 풀자면, 1부터 N까지 숫자들을 하나하나 다 더해보면 됨. 시간은 좀 걸리지만 100% 확실한 정답을 보장.

sum = 0
for i in range(1, N + 1):
	sum += N

ex - 2) 주어진 배열에 x라는 수가 있는가?

: 무식하게 풀자면, 주어진 배열의 원소를 순서대로 순회해보면 된다. 모든 원소를 순회해보면 있는지 없는지 100% 따질 수 있다.

N = 100

def solution(N, arr):
	for i in arr:
    	if i == N:
        	return True
    return False

이 방법의 최고 장점은 100% 확실한 답을 보장한다는 것. 그러나 단점은 시간이 오래 걸릴 확률이 매우 높다는 것! 

최근 알고리즘 스터디를 시작했는데, 문제를 푸는 방법에 대해 설명을 들었다. 다음과 같다.

1. 우선 무식하게 접근해보기. 즉 브루트하게 풀려면 어떻게 할 수 있나 설계해보기

2. 설계한 브루트 방식의 시간복잡도를 계산해보고, 주어진 문제의 시간제한 내에 풀 수 있을 것 같으면 코드로 옮기기

3. 시간 내에 풀 수 없을 것 같으면 다른 방식으로 해보기. 설계했던 브루트한 방식을 어떻게 최적화할 수 있을지도 고민하기.

참고로 c++언어는 대략 1억번의 연산을 1초 내로 할 수 있고, 파이썬 언어는 대략 5천만번의 연산을 1초 내에 할 수 있다고 한다. 따라서 설계한 브루트한 방식의 시간복잡도가 O(n^2) 뭐 이런 식으로 나왔다면, 여기에 문제에서 n의 최댓값으로 주어지는 값을 넣어봐서 시간 내에 충분히 될 것 같으면 코드를 짜보라는 것. 참고로 애매하게 음 한 1억번 정도 연산할 것 같은데? 로 되지는 않고 100억번 정도  연산하네? 또는 100만번만 연산하네? 정도로 확실하게 주어진다고 한다.