오늘 풀어본 문제는 프로그래머스의 모음사전이라는 문제이다.
문제 설명은 다음과 같다.
문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- word의 길이는 1 이상 5 이하입니다.
- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
이 문제는 모음 알파벳으로 이루어진 word가 모음 사전 A~UUUUU중에서 몇 번째인지 구하는 문제이다.
처음에는 규칙을 찾아 문자열의 각 위치마다 알파벳이 뭔지 확인하고 값을 계산해주려고 했는데 생각보다 쉽지 않았다.
이런 방법을 사용해서 푼 사람도 존재하지 않을까?
아무튼 이 방법이 통하지 않아 다음 방법을 생각해 보았다. 그 방법은 바로 완전탐색을 이용한 것이다.
현 위치에서 모음을 추가하고 값을 1 추가하고 다음 위치로 이동해서 또 모음 추가하고 끝에 도달하면 모음 5개만큼 반복을 돌고 마지막 모음까지 완료하면 전 위치로 돌아가서 다음 노드로 하는 식으로 푸는 방법을 생각해 보았고 정답을 맞추게 되었다.
풀이 코드는 다음과 같다.
class Solution {
String word;
int answer;
int count = 0;
String[] dict = new String[]{"A", "E", "I", "O", "U"};
public int solution(String word) {
this.answer = 0;
this.word = word;
String initString = "";
dfs(initString);
return answer;
}
public void dfs(String initString) {
if (initString.equals(word)) {
answer = count;
}
if (initString.length() == 5) {
return;
}
for (int i = 0; i < dict.length; i++) {
count++;
dfs(initString + dict[i]);
}
}
}코드를 정답이 나오면 멈춰야 하는데 모든 경우에 수를 다 돌고 정답을 저장한 뒤 코드가 끝나는 것을 볼 수 있다. 이 부분은 다음에 수정해서 올리겠다.
다음 코드를 살펴보면 일단 word와 answer 그리고 값을 증가시키기 위한 count, 단어들을 추가하기 위한 모음들의 배열 dict를 만들어주고 solution함수 내부에서 전역변수에 값을 할당해주고 dfs를 초기 문자열을 넣어줌과 동시에 실행시킨다.
dfs 함수를 살펴보면 문자열을 받아서 모음 배열의 길이만큼 반복문을 돌리며 count를 하나씩 증가시키고 다음 현재 문자열에 모음을 한개 추가해서 다음 dfs 함수로 이동한다.
위 함수가 반복하다가 word와 같아지면 answer에 count값을 넣고 문자열의 길이가 5와 같아지면 return을 하게된다.이렇게 되면 문자열이 5글자가 되면 4번째 위치로 돌아가게 되고 거기에 다음 모음을 더해서 다시 dfs를 돌게된다.
이렇게 모든 경우의 수를 다 돌고 나면 answer에는 word의 사전 위치가 저장되고 answer를 리턴하면 정답이 나오게 된다.
완전탐색
완전탐색 알고리즘이란?
완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다.
이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.
예를 들어, 4자리 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000~9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능)
하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다.
1. 사용된 알고리즘이 적절한가?(문제를 해결할 수 있는가)
2. 효율적으로 동작하는가?
위 2가지의 규칙에 대해서 생각할 때, 1번은 만족될 수 있는 가장 확실한 방법이겠으나 대부분의 경우 2번의 경우 때문에 이 방법이 사용되는데는 제한이 따른다.
완전탐색 기법을 활용하는 방법
우선 완전탐색 기법으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다.
1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2. 가능한 모든 방법을 다 고려한다.
3. 실제 답을 구할 수 있는지 적용한다.
여기서 2의 모든 방법에는 다음과 같은 방법 등이 있다.
1. Brute Force 기법 - 반복/조건문을 활용해 모두 테스트하는 방법
2. 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 없이 나열하는 방법
3. 재귀 호출
4. 비트마스크 - 2진수 표현 기법을 활용하는 방법
5. BFS, DFS를 활용하는 방법
Brute Force 기법
이 방법은 반복/조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미한다.예를 들어, 위의 자물쇠 암호를 찾는 경우와 같이 모든 경우를 다 참조하는 경우가 그러하다.
순열(Permutation)
우선 순열이 무엇인지 이해하자. 순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다.
즉, 순서가 중요하다. 만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미한다.
같은 데이터가 입력된 수열이지만, 그 순서에 따라 의미가 있고 이 순서를 통해 연결되는 이전/다음 수열을 찾아낼 수 있는 경우를 계산할 수 있다.
그래서 만약 N개의 서로 다른 데이터가 있고 이를 순열로 나타낸다면 전체 순열의 가지 수는 N!개가 된다. 최초에 N개 중 1개가 올 수 있고 그 이후에는 각각 N - 1, N - 2, ..., 1개가 올 수 있어 이를 모두 곱하면 N!이 되기 때문이다.
[1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정해보자. 그러면 아래와 같이 나열될 수 있을 것이다.
{1 2 3}
{1 3 2}
{2 1 3}
{2 3 1}
{3 1 2}
{3 2 1}
위 내용과 같이 순열을 나열할 수 있는데, 최초/최종 순열을 보면 숫자가 오름/내림차순인 것을 알 수 있다.(중복된 숫자가 있다면 비내림/비오름차순으로 된다.)
여기서 사전 순 순열의 규칙을 알아낼 수 있는데 N개의 데이터가 있고 1~i번째 데이터를 설정했을 때, i번째 데이터 기준 최종 순열은 i + 1부터 N까지가 모두 내림차순이라는 것이다.
예를 들어, 1 3 2를 보자. 이는 0번째 숫자가 1일 때의 최종 순열이다. 왜냐하면 3 2는 내림차순이기 때문이다. 그렇다면 이 다음 순열은 어떻게 구할 수 있을까?
i번째가 고정이었고 i + 1부터 내림차순인 경우가 최종 순열이므로 다음은 i번째부터 모두 오름차순이 되는 최초 순열이 된다. 즉, i - 1까지는 변동이 없고 i는 i + 1에서 N까지의 숫자 중 자신보다 크지만 가장 작은 숫자와 교환이 되고 그 i + 1에서 N은 다시 오름차순이 되어야 한다.
그래서 1 3 2의 다음 순열은 2 1 3이다. 1 3 2에서 1은 2와 교체되었고 1 3은 오름차순으로 정렬되었다.
이러한 규칙을 통해 이전/다음 순열을 구하거나 모든 순열을 완전탐색으로 구하는 로직을 구현할 수 있게 된다.
순열을 구현하는 방법
현재 순열을 구성하는 배열을 A라고 하고 i, j는 그 배열의 index값을 의미한다고 하자. 예를 들어 A = {7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index값이다.아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.
1. A[i - 1] <= A[i]를 만족하는 i중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i - 1] >= A[i]중 가장 작은 i를 찾는다.) -> 현재 값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는다는 것이다. 현재 기준 최종 순열을 찾음
A배열을 보면 A[i - 1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.
j >= i중, A[j] > A[i - 1]을 만족하는 가장 큰 j의 값을 찾는다. -> 현재가 최종 순열 상태이므로 i - 1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
A배열을 기준으로 i - 1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j값이 가장 큰 경우는 4이다.A[i - 1]과 A[j]를 Swap한다. -> i - 1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A배열은 드음과 같이 변경된다.
A = {7, 2, 4, 6, 5, 3, 1}i이후의 순열을 모두 뒤집는다. -> 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
A = {7, 2, 4, 1, 3, 5, 6}
위 로직의 시간복잡도는 어떨까? 전체 N개의 숫자에 대해 각각 순열을 구하는 문제가 된다. 제일 좌측에 숫자 N개가 올 수 있고 각 것마다 (N - 1)!개의 순열이 있기 때문에 시간복잡도는 O(N * (N - 1)!)이라서 O(N!)이 된다.
N!은 굉장히 높은 시간복잡도를 갖는다 N = 10이면 360만번의 연산이 수행되며 N = 11이 되면 4억번의 연산이 필요하다. 따라서 이 방법은 항상 사용할 수는 없고, 문제에서 주어진 N의 크기를 고려해야 한다.
다음 순열을 구하는 코드
import java.io.*;
public class Main {
static int[] perm;
static int n = 4;
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
perm = new int[]{1, 2, 3, 4};
while(get_next_perm()) {
for(int num : perm) {
bw.write(String.valueOf(num) + " "):
}
bw.write("\n");
}
bw.flush();
}
private static boolean get_next_perm() {
int i = n - 1;
while(i > 0 && perm[i - 1] >= perm[i]) i--;
if (i <= 0) return false;
int j = i - 1;
while(j < n - 1 && perm[j + 1] > perm[i - 1]) j++;
swap(i - 1, j);
j = n - 1;
while(i < j) {
i++; j--;
}
return true;
}
private static void swap(int i, int j) {
int temp = perm[i];
perm[i] = perm[j];
perm[j] = temp;
}
}재귀(Recursive)
재귀는 말 그대로 자기 자신을 호출한다는 의미이다. 왜 자기 자신을 호출할 필요가 있을까?
예를 들어, 총 4개의 숫자 중에 2개를 선택하는 경우를 모두 출력한다고 가정해보자. 1~4까지 숫자가 있고 2개를 중복 없이 선택하는 모든 경우의 수를 출력하고자 한다고 가정하자.
for(int i = 1; i < 5; i++) {
for (int j = i + 1; j < 5; j++) {
System.out.println(i + " " + j);
}
}이 경우 2중 반복문으로 손 쉽게 해결할 수 있다. 그런데 만약 숫자 N개의 숫자 중 M개를 고르는 경우라고 할 때, N과 M이 매우 큰 숫자라면 어떨까? 반복문을 수백, 수천 개를 써내려갈 수는 없다.
이를 재귀 함수를 활용한다면 자기 자신을 호출함으로써 다음 숫자를 선택할 수 있도록 이동시켜 전체 코드를 매우 짧게 줄일 수 있다.
재귀함수를 사용할 때 중요한 점
1. 재귀를 탈출하기 위한 탈출 조건이 필요
이것이 없으면 n개를 모두 골랐음에도 더 숫자를 선택하고자 하여 선택된 숫자를 저장하는 배열에 범위 초과 오류가 나거나, 다른 자료구조를 쓴 경우 잘못된 출력이 나올 수 있고, 혹은 무한 루프가 발생할 수 있다.
-
현재 함수의 상태를 저장하는 파라미터가 필요
이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다. -
Return문을 신경쓸 것
재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있다. 즉, 문제 해결을 위한 정확한 정의를 수행하여야 이것을 완벽히 풀 수 있다.
비트마스크(Bitmask)
비트마스크란 비트 연산을 통해서 부분 집합을 표현하는 방법을 의미한다.
비트 연산이란 다음과 같은 것들이 있다.
AND 연산: 둘 다 1이면 1
OR 연산: 둘 중 1개만 1이면 1
NOT 연산: 1이면 0, 0이면 1
XOR 연산: 둘의 관계가 다르면 1, 같으면 0
shift 연산: A<<B라고 하면 A를 좌측으로 B 비트만큼 미는 것이다.
비트 연산의 시간복잡도는 내부적으로 상수 시간 정도로 처리가 되어 O(1)이라고 보면 된다.(그렇다고 프로그래밍 시 산술 연산을 비트 연산으로 모두 바꾸는 것은 오히려 비효율적이다. 유지보수에도 좋지 않고 실제로 미미한 차이만 나기 때문이다.)
NOT 연산 사용 시 주의할 점
코딩 시, 숫자들을 저장할 수 있는 자료형은 1가지가 아니다. Java의 경우 byte, short, int, long 형으로 정수 형태의 자료를 저장할 수 있다.
이 때, byte는 8비트, short는 16비트, int는 32비트, long은 64비트이기 때문에 전체 저장할 수 있는 비트의 수가 다르므로 어떤 자료형에서 Not 연산을 하느냐에 따라 숫자 자체의 결과는 같더라도 비트마스크 결과는 다를 수 있다.
Shift 연산
그럼 Shift 연산에 대해서도 알아보자. <<, >>로 표현하며 해당 방향으로 원 비트를 특정 값만큼 밀어버린다는 개념으로 이해하면 된다.
예를 들어 1 << 3이라고 하면 1을 왼쪽으로 3칸 밀어서 1000이 된다.
반대로 >>는 우측르ㅗ 밀어버리는 것인데, 우측으로 밀어버리면 버려지는 것들은 그냥 삭제가 된다.
예를 들어 10 >> 2라고 한다면 10은 2진수로 1010이므로 2칸 밀면 10이 되는 것이다.
참고로, 비트 연산은 +, -보다 연산의 우선 순위가 낮다. 헷갈리지 않게 코딩할 때는 () 연산자를 잘 써서 헷갈리지 않게 해주자.
비트 연산으로 집합을 나타내는 법
비트마스크는 정수로 집합을 나타내는 것이 가능하다. 예를 들어 0 ~ 9까지의 숫자로만 이루어지는 정수 집합이 있다고 할 때, 그 중 하나의 부분 집합이 A라고 하자. 그럼
A = {1, 3, 4, 5, 9}라고 가정하면, 이를 570이라는 하나의 숫자로 나타낼 수 있다.
길이가 10인 배열을 만들어 A배열의 값에 해당하는 인덱스의 값으로 1을 넣어주고 거꾸로 1과 0을 붙여주면 1000111010이 되며 이 숫자를 2진수로 보고 10진수로 바꾸면 570이 된다.
이 비트마스크로 집합을 나타낼 때는 0~N까지 정수로 이루어진 집합을 나타낼 때 사용된다. 1~N까지로 하면 1개의 비트가 더 필요하여 전체 공간이 2배가 된다.(시가도 2배가 됨) 그래서 0~N-1까지로 활용(또한, 0이 없으면 연산을 더 변형해야 함.)
그러면 아래에서 비트 연산을 어떻게 활용하는지 알아보자
집합 포함 여부 검사
0~9까지의 숫자 중 해당 숫자가 현재 집합에 포함되어 있는지를 알아보는 방법이다.
{1, 3, 4, 5, 9} = 570이라고 할 때, 0이 포함된 여부를 검사하려면 0번째 비트만 1로 만들고 나머지를 0으로 한 것과 570을 2진수로 만든 것을 AND 연산하면 있는지를 알 수 있다.
왜냐하면, &연산은 둘 다 1인 경우만 1이므로 0이 포함된 경우는 1로 표시되기 때문에 그 결과로 나온 위치의 비트가 1이라면 해당 수가 집합에 포함 여부를 알 수 있기 때문이다.
숫자 추가하기
위의 경우와 같이 ,비트 연산을 통해 숫자를 추가할 수 있다. 특정 숫자를 추가하기 위해서는 해당 위치의 비트를 1로 만들어야 한다.
1도 만들기 위해서는 OR 연산을 사용하면 된다. 추가하고자 하는 위치의 비트만 1로 만들고 나머지는 0으로 된 비트와 570을 2진수로 만든 비트를 OR 연산 시, 추가하고자 하는 비트 위치가 1로 변경되기 때문이다.
특정 숫자 제거하기
특정 숫자를 제거하기 위해서는 NOT 연산과 AND 연산을 같이 쓰면 된다.
NOT 연산으로 제거하고자 하는 위치의 비트만 0으로 하고 나머지는 1로 만든 다음 AND 연산을 하면 해당 위치만 0으로 바뀌고 나머지는 그대로가 되기 때문이다.
토글 연산하기
0, 1을 왔다갔다 할 수 있게 하는 연산을 해보자. 만약 현재 있으면 없애고, 없으면 있게 하고자 한다면 어떨까?
즉, 0이면 1로 바꾸고, 1이면 0으로 바꾸고자 한다. 그러면 XOR 연산을 수행하면 된다.
전체 집합, 공집합 표현하기
전체 집합은 모든 숫자가 1이라는 것이므로, N개의 비트가 모두 1이라는 의미이다. 따라서 전체 집합을 표시하는 방법은 다음과 같다.
0부터 시작하므로 좌측으로 N번 이동한 뒤 1을 빼면 된다.
전체 집합: (1 << N) - 1
공집합은 그냥 0으로 표시하면 된다.
이제 위 방법을 응용하여 비트마스크를 이용한 완전탐색 문제를 해결해볼 수 있다. 비트마스크는 보통 처리할 전체 데이터가 정해져 있고 그 안에서 특정 개수를 가지고 연산을 수행할 때 사용한다.
보통 재귀로도 풀 수 있는데 비트마스크를 이용해서도 해결이 가능하다.
BFS, DFS 사용하기
이는 그래프 자료구조에서 모든 정점을 탐색하기 위한 방법이다.
BFS는 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하고 DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식이다.
위 방법들 중 상황에 따라 이용 가능한 방법을 활용하여 문제를 해결할 수 있는지 테스트하고 실제 답을 구해보는 훈련을 통해 문제 해결 역량을 기를 수 있다.
