알고리즘 이야기

알고리즘 이야기

대학교 시절에 알고리즘을 좀 공부했다가 포기하고, 나이가 들어서 다시 공부했다가 "이 길이 아닌가보다" 하고 접었습니다. 코딩을 잘 하는 방법에 대해서 이야기하자면 많은 언어를 학습해 보는 것과 알고리즘을 학습해 보는 것이 좋다고 생각합니다.

국내에서는 C, Java 가 주류를 이루고 있는데, 함수형 언어에 대한 개념을 간과하기 쉽습니다. 파이선이나 자바스크립트에 있는 함수형 언어의 특징을 사용하는 개발자와 이야기해 보면 "그냥 저렇게 쓰는 예제가 있으므로 나도 쓴다"고 대답을 하는 경우가 있습니다만 조금만 신경써서 이 분야를 이해하려고 한다면 코드를 쉽게 짜는데 큰 도움을 줄 것입니다.

많은 언어를 학습해 보면 다양한 언어의 장점을 이해할 수 있어 "우물안 개구리"에서 벗어날 수 있을 것이고, 내 비록 C 로 코딩하고 있지만 훨씬 더 훌륭한 방법으로 코딩하고 있음을 발견하게 될 지도 모릅니다.

함수형 언어로 대표적인 것은 하스켈, Lisp 등이 있습니다. 하스켈을 잠깐이라도 배워보는 것은 아주 좋은 일입니다. 외국의 어느 대학에서는 함수형 언어를 먼저 배우게 하기도 한다는군요.

이야기가 이상한데로 간 것 같습니다만 요즘은 스팀잇에 코딩 연습하는 글에 댓글을 다는 것이 소소한 즐거움입니다. 언어/알고리즘을 배우는 글을 보면 반가우면서 댓글로는 어떤 자극이 되기 어렵지 않을까 하는 생각이 듭니다.

한가지 이야기꺼리가 많은 글이 있어서 이를 소개하고 이야기를 좀 해도록 합니다.

문자열에서 어떤 문자의 첫번째 위치를 얻어내는 getIndexOf 라는 함수를 만드는 문제입니다.
문자열 "abcdefghijk" 가 있고, 'd' 의 위치는 3이 되는 아주 쉬운 문제 같습니다.

알고리즘에서는 시간복잡도가 매우 중요합니다. 보통 Big O 로 표시하는데 대충 아래의 경우가 있습니다.

O(1) : 원소의 갯수와 무관하게 상수의 시간이 걸리는 경우
O(logN) : 원소의 log 값만큼의 시간이 걸리는 경우
O(N) : 원소의 갯수만큼의 시간이 걸리는 경우
O(N^2) : 원소의 갯수의 제곱 만큼의 시간이 걸리는 경우

가장 좋은 것은 O(1) 입니다. 데이터를 해쉬로 구성했을 때 Search 는 O(1) 의 시간을 갖습니다.
그 다음은 logN, N, N^2 이런 순입니다.
N 이 1억이라고 하면 logN 은 10초, N 은 1억초, N^2 은 1억x1억=1경인가요? 만큼의 시간이 걸린다고 보시면 됩니다.

위 문제를 딱 봤을 때 얼마나 걸릴 것 같습니까? N 은 문자열의 길이입니다.

'a' 는 금방 찾겠지만, 'k' 를 찾으려면 앞에서부터 0,1,...11 까지 순차적으로 비교해야 하므로
이런 경우 O(N) 이라고 합니다.
그냥 딱 봐도 O(N) 입니다.
더 빠른 방법이 있을까요?

그럼 코딩에 들어가기 전에 잠깐 생각부터 해보지요.

문자열에 문자가 포함되어 있지 않으면 -1 임
순차적으로 앞에서부터 하나씩 비교해서 같으면 인덱스를 리턴한다

그리고 코딩하면,

function getIndexOf(char, str) {
  if(!str.includes(char)) {
    return -1;
  } else {
    for(var i = 0; i < str.length; i++) {
      if(str[i] === char) {
        return i;
      }
    }
  }
}

시간 복잡도를 측정해 볼까요? 보통 시간 복잡도는 for, while 등의 루프의 갯수를 세면 됩니다.
for 문이 하나 있으니 이는 N 입니다.

하지만 str.includes(char) 라는 것에는 루프가 없어 보이지만 실제로는 있습니다.
includes 라는 API 의 구현체를 보면 알 수 있겠지만, 그냥 감으로도 딱 루프가 있어 보입니다.

"abcdef" 에서 f 를 찾는 경우라면 str.includes(char) 에서 5회의 루프를 돌고
else 로 내려와서 다시 5회의 루프를 돌것입니다. 즉 worst case 2xN 의 시간을 갖습니다.
N 이나 2xN 이나 알고리즘의 시간복잡도에서는 크게 다르다고 보지는 않습니다.
하지만 N 으로 할 수 있는 일을 2xN 으로 하는 것은 바람직하지 않지요.

if 문의 순서를 바꾸면

if (str.includes(char)) {
  for(var i = 0; i < str.length; i++) {
    if(str[i] === char) {
      return i;
    }
  }
}
else {
  return -1;
}

if (str[i] === char) 라는 내용이 str.includes(char) 와 같다는 것을 볼 수 있습니다.
그래서 그냥

for (var i = 0; i< str.length; i++) {
  if (str[i] === char) {
    return i;
  }
}
return -1;

이렇게 하면 됩니다.

str.length 가 마음에 걸리네요. 이것은 진짜 루프가 없을까요? 정 불안하면

var slen = str.length
for (var i = 0; i < slen; i++)

하면 되겠지요?

한가지 더, 만일 위와 같은 일을 반복해서 해야 한다면 어떻게 할까요?
"abcdef" 에서 a 도 찾고 f 도 찾고 이러한 일을 계속 해야 한다면?

N 길이의 문자열에서 문자를 찾는 것을 M 번한다.
총 시간 복잡도는 N x M 이 되겠지요?
왠지 더 빠르게 하는 방법이 있을 것 같은데...

이러한 경우는 문자열 구성을 다르게 하는 방법을 생각해 볼 수 있습니다.
문자열을 정렬하면서 트리구조를 한번 만들어 놓으면 logN 의 시간에 문자를 찾을 수 있습니다.
그래서, 시간 복잡도는 NlogN + logN x M 의 시간이 걸리게 됩니다.

이런 종류는 고전적인 알고리즘에 속하고,
요즘은 몬테카를로, 머클트리 이런거 공부해야 하는게 아닐까 싶군요.

저는 알고리즘을 따로 공부하지는 않습니다만 가끔씩 올라오면 머리를 굴리게 되니 재밌기도 합니다.
치매 예방에 아주 좋을 것 같습니다.