문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

풀이

우선 제한 사항을 통해서 알고리즘의 최대 시간복잡도를 유추해보자. 보통 처리 라인이 1억 미만인 경우에 효율성 테스트가 통과가 된다. s의 길이는 최대 1000이므로 최대 시간 복잡도는 $s^2logs$ 정도로 추측할 수 있다.

우선 가장 쉬운 방법으로 문제를 해결해보자. 문자열을 압축한 결과를 리턴하는 함수를 추상화한다면 솔루션을 아래와 같이 모든 단위에 적용하여 최솟값을 찾도록 정의할 수 있다.

def solution(s):
    answer = 1002
    for i in range(1,len(s)+1):
        answer=min(answer,len(compress(s,i)))
    return answer

위에서 정의한 $compress(s,i)$ 함수의 정의는 다음과 같다. 이를 차근차근 풀어가면 재귀적 구조를 찾을 수 있다.

compress(s,i) = 문자열 s를 단위 i를 통해서 압축한다.

= 앞의 i개의 글자로 가능한 만큼 먼저 압축한다. + 나머지 글자를 단위 i를 통해서 압축한다

= frontCompress(s,i) + compress( 나머지 글자, i )

$$compress(s,i) = frontCompress(s,i) +compress(left, i) $$

재귀 함수는 당연히 조건문이 필요하다. 글자는 점점 길이가 줄어들고 만약 남은 글자가 단위보다 작다면 그대로 전달하면 되므로 아래와 같은 조건문을 추가하자

$frontCompress(s,i)$의 경우에는 맨 앞 i개의 단어를 선택한 후 얼마나 반복되는지 확인만 하면 된다. 간단하게 구현할 수 있으니 내부에 같이 구현하도록 하면 아래와 같은 코드를 작성 할 수 있다.

def compress(s,size):
        #check condition
    if len(s)<size:
        return s
        #frontCompress
    count=1
    while s[0:size]==s[size*count:size*(count+1)]: count+=1
        #return, 갯수가 1인 경우에는 숫자는 리턴하지 않는다.
    if count==1:
        return s[0:size] + compress(s[size:],size)
    else:
        return str(count)+s[0:size] + compress(s[count*size:],size)

자 그럼 이 코드는 $s^2logs$ 안에 실행되는지 확인해보자. $compress(s,i)$ 는 솔루션에서 s번 호출되므노 $slogs$안에 실행되어야 한다. 함수를 자세히 보면 중간에 while문이 있지만, 이 결과가 s의 길이를 줄이고 있으므로 $compress(s,i)$ 의 $O(n)$은 $s$이다. 따라서 총 수행시간은 $s^2$이 되므로 제한사항을 충족한다.

들어가며

이번 글에서는 문제를 해결하는 가장 단순한 방법인 완전탐색 또는 Brute-Force알고리즘에 대해서 알아보도록 하겠습니다.

목차

• 정의
  • 사용개념(재귀호출)
  • 재귀 호출을 완전탐색에 사용하는 방법
• 문제 예시 : Boggle Game
• 시간복잡도 분석

정의

Brute-Force는 직역하면 무식하게 풀기라는 의미입니다. 문제가 주어졌을 때 일어날 수 있는 모든 경우의 수를 계산해서 원하는 출력값을 얻는 것을 의미합니다. 모든 경우의 수를 탐색하므로 완전탐색(Exhaustive Solving)이라고도 불립니다. 이는 컴퓨팅 자원을 극심하게 소모하기 때문에 입력값이 작을 것으로 기대될때만 사용하는 것이 좋습니다.

간단하게 예를 들어보겠습니다. 열 명의 학생을 한 줄로 세우려고 하는데 서로 사이가 안 좋은 학생들을 붙여서 세우면 안된다는 조건이 있습니다. 이 조건을 만족하면서 열 명을 세우는 경우의 수를 구하는 문제는 어떻게 풀어야 할까요? 가장 단순한 방법은 열명의 학생을 한 줄로 세우는 모든 경우의 수를 만들고 사이가 안 좋은 학생들이 떨어져 있는 경우의 수를 세면됩니다.  10!은 대략 360만 가지의 경우의수를 가지지만 이는 컴퓨터가 1초안에 처리할 수 있기 때문에 완전탐색을 사용하는것이 적합한 문제입니다. 

사용개념(재귀호출)

자 이제 정의를 알아보았으니 코드로 어떻게 구현해야 할 지 고민할 차례입니다. 여기에서 우리는 재귀호출이라는 개념을 사용할 수 있습니다. 

우선 재귀호출의 정의부터 차근차근 설명하겠습니다.

재귀호출은 "자기 자신을 호출하는 함수"입니다. 

.

자신을 호출하면 함수 하나가 할 일을 반복해서 호출할 수 있습니다. 반복문이랑 비슷하다고 생각하면됩니다.

하지만 조건없이 계속 호출한다면 위 처럼 무한으로 반복되기에 중간에 멈추기 위한 종료조건(Base Case)이 필요합니다.

재귀 호출을 완전탐색에 사용하는 방법

다시 위 예에서 10명을 한줄로 세우는 경우의수로 돌아가봅시다.

10명을 한 줄로 세우는 경우의 수를 출력하는 문제를 푸는 과정은 다음과 같습니다.

1. 10명 중 한 명을 선택해서 줄에 추가

2. 9명 중 한 명을 선택해서 줄에 추가

3. 8명 중 한 명을 선택해서 줄에 추가

.

.

10. 1명 중 한 명을 선택해서 줄에 추가

비슷한 점이 보이시나요? 10번의 과정은 선택하는 인원의 차이만 있지 방법은 모두 똑같습니다.

이 처럼 경우의 수를 구하는 문제는 비슷한 부분문제들로 쪼갤 수 있습니다. 

그렇다면 비슷한 부분문제를 코드로 작성하는 방법은 무엇이 있을까요?

바로 재귀함수입니다!

결국 경우의 수는 부분문제로 쪼갤 수 있고 이를 코드로 작성하는데는 재귀함수가 적합하므로 완전탐색 알고리즘은 재귀함수로 작성합니다.

예제 문제 : Boggle Game

완전 탐색의 정의와 문제 풀이방법을 알아보았으니 실제로 문제를 풀어보도록 하겠습니다.

문제: Boggle Game

설명 : N x N의 필드에 각 칸마다 하나의 문자가 새겨져 있고 상하좌우, 대각선 방향으로 이어서 하나의 단어를 찾을 수 있는지 찾는 문제입니다. (위의 경우 coding을 찾아야합니다. )

완전탐색으로 해결하기

문제를 해결하기 위한 과정을 만들어봅시다.

1. 하나의 칸을 선택하고 단어의 첫 번째 글자가 있는지 확인

2. 상하좌우,대각선 방향 등 총 8가지의 방향에 두 번째 글자가 있는지 확인

3. 두 번째 글자에서 다시 상하좌우,대각선 방향 등 8가지 방향에 세 번째 글자가 있는지 확인

.

.

.

위 과정을 보니 계속해서 글자가 일치하는지 확인하고 8가지 방향을 탐색하는 과정을 반복합니다.

이렇게 반복하는 과정을 정의했으니 재귀함수로 이 정의를 구현하고 문제를 해결해봅시다.

const int dx[8] = { -1, -1, -1,  1,  1,  1,  0,  0};
const int dy[8] = { -1,  0,  1, -1,  0,  1, -1,  1};
/*
함수 정의 : 보드의 위치를 받아 글자가 일치하는지 확인하고 다음 8방향 탐색
*/
bool hasWord(int x, int y, int pos) {
	//종료조건1: 넘겨받은 보드의 위치가 범위를 초과한 경우 
    if (x < 0 || x >= 5 || y < 0 || y >= 5)
        return false;
	//종료조건2: 글자가 일치하지 않는 경우
    if (Board[x][y] != Word[pos])
        return false;
	//종료조건3: 글자수와 탐색 횟수가 일치하는 경우 = 모든 단어의 글자가 일치하는 경우
    if (Word.size() == pos + 1)
        return true;

    bool ret = false;

    for (int d = 0; d < 8; ++d) {
    	//8방향의 결과값들을 하나씩 확인 후 하나라도 true를 반환하면 true반환
        //모든 방향의 결과값들이 false일 경우 false를 반환
        if (hasWord(x + dx[d], y + dy[d], pos + 1)) {
            ret = true;
            break;
        }
    }
    
    return ret;
}

시간복잡도 분석

보글게임을 문제를 해결했으니 이제 위 알고리즘이 얼마나 시간이 걸리는지 계산하기 위해서 시간복잡도를 계산해보겠습니다.

시간복잡도는 항상 최악의 경우를 생각해서 작성해야합니다. 예를 들어 찾고자하는 단어가 aaaab이고 보드에는 전부 a만 있다고 가정합시다. 이런 경우 위 알고리즘은 모든경우를 탐색하기에 8^4의 경우의 수를 탐색합니다. 즉 단어의 길이가 n 일때 8^(n-1)개의 경우의 수를 탐색하기에 하나의 단어를 찾는데 O(8^n)의 시간복잡도가 기대됩니다. 이는 기하급수적으로 경우의 수가 상승하므로 단어의 길이가 길고 보드의 크기가 클 경우 다른 알고리즘을 사용하는 것이 좋습니다.