[알고리즘] 코딩면접, 이것만 풀면 된다?!

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

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

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

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

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

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

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

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

용자는 퇴직하기 직전,

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

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

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

<조엘 온 소프트웨어>의 한 챕터에서 제시한 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;
}

끝_