알고리즘 이야기

in #kr-dev4 years ago

알고리즘 이야기

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

국내에서는 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 의 시간이 걸리게 됩니다.

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

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

Sort:  

써 놓고 나니까 벌써 틀린게 보이는군요... ^^ 찾아보세요...

진짜 일하면서 "학교다닐 때 공부 열심히할 걸" 후회 많이 했...

늦었다고 생각할때가 가장 빠...

그럼 내일 부터...

안녕하세요! 제 글에 댓글달아주시는데, 상당히 도움이 많이 되고 있습니다. 지금은 기초를 공부하면서 정리하느라, 시간복잡도까지는 고려를 못하고 있었는데, 좀 더 고려를 해볼 수 있을 것 같습니다! 위에 글을 보니 조금 이해가 되긴 합니다! 그런데 위에서 str.length 부분에서 var slen = str.length해서 for문을 돌리는 것이랑, 그냥 str.length를 쓰는 것이랑 시간복잡도 관련해서 어떤 차이가 있을까요?

for문 안에서 str의 길이가 바뀐다면 str.length로 사용해야겠지만, 그렇지 않다면 var slen = str.length를 사용하는게 일반적으로 조금 더 좋은 선택일겁니다.

str.length의 시간 복잡도는 관련 문서를 봐야 알겠지만, O(1)은 아닐 거라 가정을 하겠습니다.
그러면 시간복잡도가 O(n)인 for문을 하나만 썼더라도, 실제로는 이중 반복문인 것과 같은 시간 복잡도(.length의 시간 복잡도에 따라 O(nlogn),O(n^2) 등)을 갖게 될겁니다.

자바에서의 string length는 int 변수인데 자바스크립트는 다른걸까요? ㅎㅎ

C++ 일부 STL의 크기 판별 함수가 O(n)이더라고요.
JAVA나 javascript는 따로 문서를 봐야 알 수 있을 것 같습니다

C 는 zero terminated string 이라서 len(str) 은 O(n) 입니다.
자바의 경우 String 은 객체로 취급하며 내부적으로 length 를 가지고 있습니다.
참고로 자바 String 은 Constant 이므로 length 가 변하지 않습니다.

오~~ 코딩이야기 재밌습니다~~ ㅎㅎㅎ
앞으로 요런 이야기 종종 해주시면 좋겠어요~~ ㅎ

자주 올리도록 해보지요...

O(N) 쉽고 간결하게 설명해주셨네요~

제게 소프트웨어는 미지의 영역입니다. 재밌는 이야기 감사해요 ^^

Coin Marketplace

STEEM 0.30
TRX 0.06
JST 0.041
BTC 37123.23
ETH 2469.23
USDT 1.00
SBD 4.03