그 동안 알고스팟의 '왕초보'문제를 풀어보았습니다.

퇴근하고 집에 와서 졸린 눈 부비며 풀기에는 '왕초보'도 벅찬 경우가 많았습니다.

코딩은 정말 정신이 또렷한 상태에서 해야지,

졸음코딩이나 음주코딩을 하면 효율을 내기가 힘든 작업이란걸 다시 깨달았습니다.


오늘부터는 '초보' 문제들을 하나씩 풀어보도록 하겠습니다.

튜토리얼에 '초보' 난이도로 총 26문제가 명시되어 있습니다.

하루에 한 문제씩 풀다보면 한달이 훌쩍 지나가 있겠네요.



- 제목 : URI

- 난도 : ☆☆☆☆☆ (0점/5점)

- 문제

   (간단히 의역해보겠습니다) URI(Uniform Resource Identifier)는 인터넷 공간에서 리소스를 확정할 때 사용하는 간단한 스트링입니다.

    http://storycompiler.com

    mailto:storycompiler@storycompiler.com

    ftp://127.0.0.1/main.php

    README.txt

    위의 URI를 인터넷으로 보낼때 몇몇 특수문자는 %인코딩으로 변환해야 합니다.

    %인코딩은 %와 두자리의 16진수로 구성됩니다.

    예를 들자면, " "(빈칸)은 %20, "!"은 %21, "$"은 %24 등으로 정의됩니다.

    %인코딩된 문자열을 본래 문자열로 변환하는 프로그램을 작성하세요.

- 답안

#include <stdio.h>

int main(int argc, char **argv)
{
    int total_count = 0;
    int count = 0;

    scanf("%d", &total_count);

    for (; count < total_count; count++) {
        char string[81] = {0, };
        char tostring[81] = {0, };
        register int i = 0;
        register int j = 0;

        scanf("%s", string);

        while (string[i]) {
            if (string[i] == '%') {
                char special = '0';
                if (string[i + 1] != '2') {
                    i += 3;
                    continue;
                }

                switch (string[i + 2]) {
                case '0':
                    special = ' ';
                    break;
                case '1':
                    special = '!';
                    break;
                case '4':
                    special = '$';
                    break;
                case '5':
                    special = '%';
                    break;
                case '8':
                    special = '(';
                    break;
                case '9':
                    special = ')';
                    break;
                case 'a':
                    special = '*';
                    break;
                default:
                    break;
                }
                tostring[j] = special;
                i += 3;
                j++;
            } else {
                tostring[j] = string[i];
                i++;
                j++;
            }
        }
        printf("%s\n", tostring);
    }

    return 0;
}


- 문제에 특화하여 코딩하였습니다.

   %인코딩에 첫번째 숫자가 '2'외에도 많겠지만,

   문제에서 제한한 숫자는 '2'이기에 if 문을 하나 두어 '2'인 경우에만 처리하도록 하였습니다.


- while (string[i]), 오랜만에 while문을 사용하였습니다.

   경우에 따라 i++ 혹은 i += 3처럼 사용해야해서 for문 대신 while문으로 i값을 직접 컨트롤하였습니다.


- switch - case문은 커널 코딩스타일에 따라 같은 열에 배치되도록 하였습니다.

   case문은 switch보다 한 탭 아래에 두는 경우도 많긴 한데요,

   커널에서는 탭을 매우 제한적으로 사용하도록 하고 있기 때문에 switch - case에서는 탭을 아끼는 정책을 택했습니다.

   탭을 제한적으로 사용했던 이유는 예전 터미널이 80열까지만 지원했기 때문이지요.


이상으로 알고스팟에서 총 10문제를 풀었습니다.

순위는 1284위로 상승하였습니다.

머지않아 1000위 내로도 올라가겠군요.


그럼 좋은 하루 보내세요~

끝_

성격을 도무지 종잡을 수 없다고 하여,

'세 쌍둥이'로 불린 한 임원 분이 계셨습니다.

세 쌍둥이 중 첫째 분은 언제나 매우 인자한 미소로 '훌륭하다', '잘했다'를 연발하셨습니다.

둘째는 잔혹하고 포악하여 물건을 던지거나 육두문자를 섞어가며 인신공격을 하셨습니다.

셋째는 조울기가 다분하여 '분'단위로 성격이 바뀌어 어느 장단에 춤춰야할지 갈피를 잡을 수 없었습니다.

문제는 같은 내용의 보고를 해도,

어느 분을 만나느냐에 따라 결과가 달라진다는데 있었습니다.


그런 임원분에게 과감히 반론을 제기했다가 소리 소문도 없이 퇴직한 용자가 계셨습니다.

용자는 퇴직하기 직전,

한 책을 열심히 홍보하고 다니셨죠.

바로- <조엘 온 소프트웨어>

지금은 어디서 무얼 하고 있을지 모르는 용자를 기리며,

<조엘 온 소프트웨어>의 한 챕터에서 제시한 7가지 간단한 코딩문제를 풀어보겠습니다.


1. 원래 저장위치에서 문자열을 역순으로 변환하기


문자열을 역순으로 변환하려면,

- 문자열의 길이를 알아낸 후,

- 문자열의 첫번째 문자와 마지막 문자를 서로 교환하고,

- 문자열의 두번째 문자와 마지막 문자 - 1을 서로 교환하고...

위의 절차를 반복하면 됩니다.


int strrev(char *src)
{
char *end_pointer = NULL;

if (!src) return -1;
if (!*src) return -1;

end_pointer = src + strlen(src) - 1;

while (src < end_pointer) {
char tmp = *src;
*src = *end_pointer;
*end_pointer = tmp;
src++;
end_pointer--;
}

return 0;
}

위의 strrev 함수를 사용하여 'Hello'를 뒤집어보죠.

$ ./test
origin word : (Hello)
reverse word : (olleH)


하지만, strrev는 바이트 단위로 swap하고 있기 때문에,

ASCII처럼 바이트당 한 글자가 지정된 코드페이지에서만  원하는 결과값을 얻을 수 있습니다.

유니코드 한글을 입력하면 아래처럼 엉뚱한 값이 찍히게 됩니다.


$ ./test
origin word : (안녕하세요.)
reverse word : (.��츄옕핅눕�)

이를 해결하기 위해서는 유니코드계열 함수를 사용하면 됩니다.

유니코드 관련 함수는 차후에 다시 다루기로 하죠. :)



2. 연결 리스트를 역순으로 만들기


연결리스트에 삽입된 n개의 노드를 모두 순회하기 위해서는 최소 n번 동안 한 노드에서 다음 노드로 이동해야 합니다.

총 3개의 노드로 이뤄진 아래 그림의 linked list를 보면,

first 노드에서 last 노드까지 3번의 노드간 이동으로 3개의 노드를 탐색하였습니다.

(first 노드에 다다르는 것도 한 번이라 셈함)



위의 linked list를 역순으로 배치하려면,

리스트를 순회하기 위해 소요되는 최소한의 횟수인-

'n'번(!) 이상 노드를 거치면서 loop를 돌아야합니다.

그렇게 하여 아래 그림처럼 next가 가리키는 노드의 방향을 바꿔야 합니다.



prev -> cur -> next로 이동하며 각각의 노드의 next 값을 아래의 루틴처럼 변경합니다.

다음에 탐색하여 나갈 다음 노드를 next 변수에 저장해두고,

현재(cur) node의 next를 이전(prev) 노드로 저장하고,

다음 순회 때에는 현재 노드가 이전(prev) 노드가 되고,

이전(prev) 노드가 현재(cur) 노드가 되어야 합니다.


typedef struct {
void *data;
node *next;
} node;

node *reverse_list(node *first)
{
node *cur = first;
node *prev = NULL;
node *next = NULL;

if (!first) return NULL;
if (!first->next) return NULL;

do {
next = cur->next;
cur->next = prev;

prev = cur;
cur = next;
} while (next);

return prev;
}

O(n)의 복잡도로 순회를 하며 리스트를 역순으로 변경합니다.



3. 한 바이트에서 1인 비트 세기


한 바이트 곧 8비트에서 1인 비트를 세려면,

비트를 하나씩 오른쪽으로 옮겨서 1과 &연산을 해보면 됩니다.


위의 옅은 파랑 영역이 1과 &연산을 하는 구역이다.

이를 코딩해보면 아래와 같습니다.


unsigned char count_bit(unsigned char number)
{
unsigned char count = 0;

while (number) {
count += number & (unsigned char) 1;
number = number >> 1;
}

return count;
}


'unsigned'는 오른쪽으로 shift 시에 가장 왼쪽에 있는 비트가 '0'으로 채워지게 합니다.

'signed' 타입은 가장 왼쪽의 비트가 '1'일 때,

오른쪽으로 shift시키면 다시 1로 채웁니다.

signed로 변수의 타입을 지정하고 while 루프를 돌리면,

'>>' 연산의 결과가 계속 1로 채워지기 때문에 무한루프에 빠지게 됩니다.


여기서 한 걸음 더 나아가-

비교적 작은 배열을 하나 만들어 캐싱을 해도 됩니다.


#define MAXIMUM 256
static struct {
unsigned char count[MAXIMUM];
} s_info;

unsigned char count_bit(unsigned char number)
{
unsigned char count = 0;

while (number) {
count += number & (unsigned char) 1;
number = number >> 1;
}

return count;
}

void cache_bit(void)
{
int i = 0;

for (; i < MAXIMUM; i++) {
s_info.count[i] = count_bit(i);
}
}


최초 실행 직후 caching을 위한 배열을 구성합니다.

그 이후로는 캐싱된 배열에 접근하여 O(1)로 비트 개수를 얻습니다.

캐시를 한꺼번에 하지 않고 필요할 때마다 하나씩 할 수도 있을 것입니다.

어느 쪽이든 자기 상황에 맞게 구성하면 됩니다.



4. 이진 검색


이진검색은 O(logn)으로 데이타를 검색할 수 있습니다.

n개의 데이타 중에 검색하고자 하는 데이타를 순차적으로 찾으려면,

평균 n/2번 검색을 수행하고 나서야 데이타를 얻을 수 있습니다.


하지만, 순차탐색 대신 데이타가 속한 영역을 반씩 줄여가며 검색하고자 합니다.

이를 위해서는 먼저  데이타가 정렬되어 있어야만 합니다.

데이타가 삽입, 삭제, 갱신되는 시점에 데이타들은 reordering을 합니다.


그리고 검색하게 되면,

이진검색은 정렬된 n개의 데이타 중에 n/2번째에 위치한 데이타를 꺼내와서 찾고자 하는 데이타 value와 크기를 비교합니다.

if (value < (n/2)), value는 0과 n/2 사이에 있을테고,

else 라면, value은 n/2와 n 사이에 있겠죠.



위의 그림은 나름 worst case를 준비한 것입니다.

9개의 데이타 중 3번을 검색하여 1을 찾아내는 과정을 보여줍니다.

순차탐색에서는 한 번에 1을 찾아냈을 것입니다.

하지만, 이러한 극단적인 일부 케이스에서는 순차탐색이 더 좋을지는 몰라도 n의 갯수가 늘어날수록 이진검색의 위력이 세집니다.


int binary_search(int array[], int size, int value)
{
int first = 0;
int last = size - 1;
int mid = 0;
int i = 0;

if (!array) return -1;
if (size < 0) return -1;

while (first != last) {
mid = (first + last) / 2;
if (array[mid] > value) {
last = mid - 1;
} else if (array[mid] < value) {
first = mid + 1;
} else {
return mid;
}
}

if (array[first] == value) return first;

return -1;
}

이 함수에서는 검색한 값이 없을 경우 -1을 리턴하게 하였습니다.



5. 문자열에서 '연속적으로 문자가 반복되는 길이 run-length'가 가장 긴 부분문자열 찾기


첫번째 문자부터 마지막 문자까지 한 번만 훑는 평이한 알고리즘을 짜보았습니다.

이전 문자와 비교하여 같으면 count를 하나씩 올리도록 하였습니다.

O(n)보다 나은 알고리즘이 있을까요?


unsigned int count_longest_run_length(const char *string)
{
unsigned int count = 1;
unsigned int max = 0;
char cur = 0;
char pre = 0;

if (!string) return 0;
if (!*string) return 0;

while (cur = *string) {
if (cur == pre) {
count++;
if (max < count) max = count;
} else {
count = 1;
}
pre = cur;
string++;
}

return max;
}


6. atoi


ascii to integer. 아스키 문자열을 integer로 변환해주는 함수입니다.

문자열을 앞 부분부터 한 글자씩 읽어서 아스키 숫자값이 아니면 리턴합니다.

아스키 숫자인 경우에만 자릿수를 고려하여 더해줍니다.


int _atoi(const char *a)
{
int i = 0;
char tmp = 0;

if (!a) return 0;
if (!*a) return 0;

while (tmp = *a) {
tmp -= '0';
if (tmp < 0 || tmp > 9) return 0;
i = i * 10 + tmp;
a++;
}

return i;
}



7. itoa (스택이나 strrev를 써야 하기 때문에 좋은 문제임)


integer to ascii. 정수형 integer를 radix 진수 문자열로 변환하는 간단한 함수를 만들어 보았습니다.

itoa는 (integer % 10) 나누어 최하위 자리부터 문자로 변환합니다.

따라서 최하위 -> 최상위로 변환작업을 마친 후 스택이나 strrev로 문자열을 뒤집어줘야 합니다.

아래 코드에서 strrev는 위의 1번에서 만들어둔 strrev를 그대로 사용하였습니다.


char *itoa(int integer, char *buf, int buf_size, int radix)
{
int i = 0;

if (!buf) return NULL;
if (!buf_size) return NULL;
if (radix <= 0) return NULL;

for (; integer; i++, buf_size--) {
if (!buf_size) return NULL;
buf[i] = integer % radix + '0';
integer /= radix;
}

if (strrev(buf) < 0) {
return NULL;
}

return buf;
}



끝_


+ Recent posts