문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.간단한 예로 "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)의 시간복잡도가 기대됩니다. 이는 기하급수적으로 경우의 수가 상승하므로 단어의 길이가 길고 보드의 크기가 클 경우 다른 알고리즘을 사용하는 것이 좋습니다.

 Selection Sort(선택정렬) &  Bineary search(이진탐색)

목차

설명

선택정렬을위한 단계

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

배열의 크기를 받고 동적할당(malloc)이용해 크기만큼 정수형 배열을 생성합니다.

그리고 반복문과 scanf()함수를 통해서 데이터를 입력받습니다.

2. 선택정렬을합니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <stdio.h> #include <stdlib.h> #define swap(a,b,temp) {temp=a;a=b;b=temp;} int main(void) {     //make array     int array_size, *array;     scanf("%d", &array_size);     array = (int*)malloc(sizeof(int)*array_size);     //get data     int i;     for (i = 0; i < array_size; i++)         scanf("%d", &array[i]);     //loop for n     for (i = 0; i < array_size; i++) {         //loop for find min         int smallesti = i, j;         for (j = i + 1; j < array_size; j++) {             if (array[smallesti] > array[j]) {                 smallesti = j;             }         }         //exchange         int t;         swap(array[smallesti], array[i], t)     }   //print } Colored by Color Scripter

cs

구상했던데로 이중 반복문을 입력해서 범위를 줄여가며 가장작은 부분을 앞에오도록합니다.

3. 정렬된 배열을 출력합니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #define swap(a,b,temp) {temp=a;a=b;b=temp;} int main(void) {     //make array     int array_size, *array;     scanf("%d", &array_size);     array = (int*)malloc(sizeof(int)*array_size);     //get data     int i;     for (i = 0; i < array_size; i++)         scanf("%d", &array[i]);     //loop for n     for (i = 0; i < array_size; i++) {         //loop for find min         int smallesti = i, j;         for (j = i + 1; j < array_size; j++) {             if (array[smallesti] > array[j]) {                 smallesti = j;             }         }         //exchange         int t;         swap(array[smallesti], array[i], t)     }     //print     for (i = 0; i < array_size; i++) {         printf("%d ", array[i]);     } } Colored by Color Scripter

cs

 Bineary search(이진탐색)

설명

이진탐색이란?

 이진탐색은 배열중에서 어떤 수를 찾는 방법중 하나입니다.

 전체 범위에서 가운데 숫자를 기준으로 그 숫자보다 큰 지 작은지 범위를 좁혀가며 숫자를 찾습니다. 이 방식은 순서대로 찾는것보다 훨씬 효율적입니다.

 이진탐색은 오름차순으로 정렬된 배열에서만 사용이 가능합니다.

그럼이제 배열의 크기, 배열 그리고 찾고 싶은 수를 받아서 수의 위치를 반환하는 알고리즘을 작성해보도록 하겠습니다.

위와 마찬가지로 구상을 해봅시다.

1. 배열의크기, 배열 그리고 찾고 싶은 수를 입력받는다

2. 중간값이 찾고싶은 수인지 더 작은지, 큰지 비교하여 범위를 좁혀나가는걸 반복한다.

3. 찾고싶은 수가 있다면 위치를 출력하고 없다면 -1을 출력한다.

이번 구상은 위보다 조금 어려울수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int main(void) {     //make array     //get data( array and target)          // loop while range > 0          // find midle value                  //check value is target                  //else if value < target         //else(target < value)     //check find }

cs

구상한걸 우선 각주로 표현하고 하나씩 진행해봅시다.

1. 배열의크기, 배열 그리고 찾고 싶은 수를 입력받는다

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int main(void) {     //make array     int array_size, *array, target;     scanf("%d", &array_size);     array = (int*)malloc(sizeof(int)*array_size);     //get data( array and target)     int i;     for (i = 0; i < array_size; i++)         scanf("%d", &array[i]);     scanf("%d",&target);     // loop while range > 0          // find midle value                  //check value is target                  //else if value < target         //else(target < value)     //check find } Colored by Color Scripter

cs

이부분은 쉬우니 따로 설명하지 않습니다.

2. 중간값이 찾고싶은 수인지 더 작은지, 큰지 비교하여 범위를 좁혀나가는걸 반복한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int main(void) {     //make array     int array_size, *array, target;     scanf("%d", &array_size);     array = (int*)malloc(sizeof(int)*array_size);     //get data( array and target)     int i;     for (i = 0; i < array_size; i++)         scanf("%d", &array[i]);     scanf("%d",&target);     int start=0,end=array_size-1, target_loc=0;     // loop while range >= 0      while(start<=end){         // find midle value         int mid=(start+end)/2         //check value is target         if(array[mid]==target){             target_loc=mid;             break;         }         //else if value < target         else if(array[mid] < target){             start=mid+1;         }         //else(target < value)         else{             end=mid-1;         }     }     //check find } Colored by Color Scripter

cs

이 부분에서 범위를 start변수로 첫번째 지점, end변수로 마지막 지점을 정합니다.

그리고 int mid=(start+end)/2  를 이용해서 중간지점을 찾아 target과의 값을 비교하고 결과에 따라 범위를 새로 지정합니다.

3. 찾고싶은 수가 있다면 위치를 출력하고 없다면 -1을 출력한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int main(void) {     //make array     int array_size, *array, target;     scanf("%d", &array_size);     array = (int*)malloc(sizeof(int)*array_size);     //get data( array and target)     int i;     for (i = 0; i < array_size; i++)         scanf("%d", &array[i]);     scanf("%d",&target);     int start=0,end=array_size-1, target_loc=0;     // loop while range >= 0      while(start<=end){         // find midle value         int mid=(start+end)/2         //check value is target         if(array[mid]==target){             target_loc=mid;             break;         }         //else if value < target         else if(array[mid] < target){             start=mid+1;         }         //else(target < value)         else{             end=mid-1;         }     }     //check find     if (start > end) {         printf("-1");     }     else {         printf("%d", target_loc);     } }  Colored by Color Scripter

cs

start > end인 경우가 못찾은 경우랑 같은이유는 다음과 같습니다.

위 반복문안에서는 범위가 점점줄어들고 있습니다. 범위가 줄어들어 start와 end가 같아질때의 위치에 있는 숫자가 없다면 end=mid-1; 이 실행되어 end는 start보다 작아지게 됩니다. 따라서 start > end == 못찾음이 성립됩니다.

알고리즘 코딩을위한 팁

두 개의 대표적인 알고리즘 코드를 짜보았습니다. 앞으로는 이보다 더 어렵고 복잡한 알고리즘을 짤 일이 많을 수 있습니다. 이 때 빠르고 정확하게 알고리즘을 짜는법은 절대 이해하지도 못하면서 빨리 시작부터하는것이 아닙니다.

1.복잡한 문제를 빠르게 짜기위해서는 항상 전체적인 구상을 생각해봐야 합니다. 

2. 각주를 사용해 미리 코딩을 한다는 생각으로 살짝 적어주고 맞는지 판단합니다.

3. 그리고 코드를 짜면 자잘한 에러를 제외하고 거의 정확합니다.

코드를 짜기전에는 항상 이해를 해야하기 때문에 무턱대고 코드를 짜는것은 나중에 누더기옷같은 코드를 만들수 있습니 꼭 이해와 구상을 하고 짜시기 바랍니다.