강좌 전 태오의 잡담>

김민오님의 알고리즘 강좌 그 두번째 이야기입니다. ^^  이번 내용은 꽤 유익한 것들로 구성되었네요

강좌 시작 >

Replace 함수와 bubble_sort 알고리즘

"평범한 웹디자이너는 포토샵을 잘다루고 뛰어난 웹디자이너는 남들이 따라올수 없는 감각이 있다.."

사실 asp 에서 string 을 다루기는 굉장히 쉽습니다. 각종 함수들이 지원을 해주기 때문에 어렵지 않게 문자열을 자를수도 있고 문자열을  바꿀수도 있습니다. 또한  문자열을 추가 할수도 있습니다.  하지만  다른언어를 해보신분들은 아시겠지만 이 문자열을 다룬다는것은 상당히 복잡하고 귀찮은 일이기 까지 합니다.    

가까운 예를 들어 여러분은 게시판을 만들때 작은따움표  문제를 해결하기 위해 replace(str, "'", "''" ) 가 항상 들어 갑니다. 그렇다면 어떻게 해야 할까요...게시판 위에다가 " 작은 따움표가 들어가면 에러가 나니 쓰지 말아 주세요 " 라고 하면 될까요 ?

일단 우리는  left 함수와 right , mid , len 함수는 사용할수 있다고 가정해야 합니다. 이것은 asp 로 구현하기는 거의 불가능합니다. C에서는 포인터 라는것이 있기 때문에 이런함수까지도 만들수 있지만   asp 에서는 그정도까지는 힘이 드내요 T.T

해보시면 알겠지만   str_me 에는 "엄마돈없다." 라는 문자열이 들어가 있습니다. 이상합니다.. 우리는 str_me 라는 변수에 값을 넣어준적이 없고 단지 파라미터인 str_ mother 에만 "엄마돈없다." 라는 문자열을 넣어 줬는데 str_me 값도 변경 되었습니다.

이게 왜이렇게 되냐면 vb나 asp 는 기본적으로 call by reference 를 사용해서 함수에 값을 전달 합니다.  즉 call test(str_me) 라는 함수를 호출하면 str_me 에 들어있는 "엄마돈줘" 라는 값이 넘어 가는 것이 절대 아닙니다 . 내부적으로 로는  str_me 의 메모리 주소가 넘어 갑니다..

즉 변수의 이름은 다르지만  같은 메모리 주소값을 갖게 해서  하나의 변수값을 변경하면  그 메모리주소가 가르키고 있는 값도 변경이 됩니다. 이것은 상당히 편리한 방법이고 알게 모르게 우리는 전부 call by reference 를 사용하고 있었던 것입니다. 하지만  변경되지 않고 값만 넘겨줘야 할때도 있습니다.. 이것을 call by value 라고 하고  속도도 약간 빠르다고 합니다.

파라미터 앞에다가 byval 이라고 해주면 메모리 주소는 필요 없이 값만 전달 받겠다는 뜻입니다.

1. replace 함수 만들기

일단 str_mother = "엄마'천원'만줘" 에 작은 따움표가 두개 들어 있습니다. 우리는 이것을 "엄마''천원''만줘" 로 만들어야 합니다.  원리는 아주 간단합니다     들어온 문자열을 한개씩 잘라서  비교 한다음 작은따움표라면 큰따움표로 바꿔주면 되는것입니다. 초보자분들이 여기서 잘못하는것이 문자열을 한개씩 자르는 것과  마지막에 문자열을 하나씩 더해서 다시 새로운 문자열을 만들어 되돌려 주는것을 대부분 잘 못합니다. 밑에 소스를 잠깐 보겠습니다.

1.  일단 str_mother 에는  "엄마천'원'만줘" 라는 값이 들어있고 이것을  call replace_str(str_mother, "'", "''")  에서 함수호출을 하였습니다. 그렇다면 함수 내부에서는 어떤 동작을할까요?. 일단 문자열을 하나하나씩 비교 하려면  반복문이 필요할것이고 이 반복문은 문자열의 끝까지 돌면 됩니다..

for i = 1 to len(str)

2. 그다음에는 문자열을 하나씩 잘라서 어딘가에 저장시켜야 한다. mid 함수는   ("abcdefg" , 2, 3 ) 이라고 하면 abcdefg 의 두번째 글자부터 3개를 가져온다  즉 bcd 를 가져오는 함수이다. 여기서 우리는 한글자씩 만 가져오면 된다.    즉 1부터 마지막 번호까지 가져올려면 

str_temp =  mid(str, i ,  1)

3. 이제 str_temp 에는 첫번째글자가 담겨 있을 것이고 이것이 ' 와 같다면  '' 로 바꿔준다.  

    if str_temp = equal then         -> if str_temp = "'" then
       str_temp = change              ->   str_temp = "''" 
    end if                                      -> end if

4. 이제 그 문자열을 하나씩 조합해서 새로운 문자를 만든다. 

    str_return  = str_return + str_temp    '

이번에는 문자열 정렬에 관해서 알아 보겠습니다.

2. bubble sort

정렬알고리즘은 정말 무수히 많습니다. 필자가 알고 있는 정렬알고리즘만해도 8개 가까이 되고 현재도 정렬 알고리즘은 연구 되고 있고 새롭고 성능좋은 정렬 알고리즘을 개발한다면이것은  논문감입니다 :-) 그만큼 많은 사람들이 연구해왔고 최적화 되어 왔습니다. 이중에서 우리는 거품정렬(bubble sort) 을  사용해서 문자열을 정렬해볼 것입니다.  

일단 문자열을 정렬한다 함은 "bacdfe" 를 오름차순으로 정렬하면 "abcdef" 가 됩니다. 거품 정렬 알고리즘의 원리는 인접한 배열의 요소를 비교 , 교환한다음에 전체적으로 대충 정렬을 하면서  최대값을 배열의 제일 마지막으로 보내는 것을 반복하다보면 오른차순으로 정렬이 됩니다.

"fbadce" 가 있다고 치면  우선 

   1.  f 와 b 를 비교한다
        b 가 앞에 와야 하므로 자리를 바꾼다. 
        그렇게 되면  "bfadce" 가 될것이다 
        다시 f 와 a를 비교한다 
        a 가 앞에 있어야 하므로 자리를 바꾼다. 
        그렇게 되면 "bafdce" 가 된다. 
        다시 f 와 d를 비교한다 
        d 가 앞에 있어야 하므로 자리를 바꾼다. 
        "badfce" 가 되고 이렇게 되면서 결국 f는 제일 뒤로 가게되면서 
        "badcef" 의 형태가 될것이다.   
        f가 제일 뒤로 보내지게 되면

    3. 이미 "abcdef" 로 정렬은 다 되었지만 계속 해나간다면 
        다시 a 와 b를 비교하고 d까지만 비교 한다 (맨뒤로보낸 e, f 는 비교 하지 않는다. )

이 버블 소트는  비교적 어느정도 정렬이 되있는 문자를 정렬할때 굉장히 빠른 속도를 자랑하지만 역순으로 정렬되있는 문자를  정렬할때는 비교적 느립니다. 이유는 간단합니다  앞뒤 자리를 계속 바꿔줘야 하기 때문이지요.

지금 이 함수는 이글을 쓰면서 바로바로 만들고 있는것인데 뭔가 최적화 되지는 않은느낌입니다. 버블소트의 장점은  중간에 정렬이 다되었으면 끝까지 비교 하지 않고 중간에 멈출 수 있습니다.  이것을 소스에 넣으면 너무 복잡해 보이기 때문에  소스에서 뺐으며 중간에 멈출 수 있는 것은 버블소트의 장점입니다.  여러분이  직접 한번 해보시기 바랍니다 (힌트 : 문자열을 비교하다 교환이 일어나지 않으면  문자열은 정렬된상태 이다. 교환이 일어 나지 않을 때 for 문을 빠져나오면 된다. )

뭔가 복잡해 보이긴하지만 실제로 여러분이 만들어 가면서 소스를 보면 그리 어렵지도 않습니다.. 제일 윗부분의 반복문과 아래부분의 반복문은 사실 중요하지 않고 중요한 부분은 

For i =  0   To str_length        
' 여기서 부터가 버블 소트 이다.  문자열의 길이만큼 다시 반복문을 돈다. 
    For j = 1   To str_length - i      ' 2중 반복문이다. 
    'str_length - i 의 이미는 제일 마지막에 있는 제일 큰문자는 다시 비교할 필요가 없어서이다.

         If str_temp(j - 1) > str_temp(j) Then     ' "a" 와 "s" 를 비교 해서 
              t = str_temp(j - 1)                          ' "s"가 크면 임시 변수에 저장해놓고
              str_temp(j - 1) = str_temp(j)           '자리를 서로 바꾼다. 
              str_temp(j) = t
         End If

    Next
Next

사실 머리가 좋은 사람들은 이부분 정도는 머리로 따라가면서 결과 값을 예측하곤 하지만   한번씩 해보면서 이해하시길 부탁 드립니다. 가장 중요한 것은 버블소트는 뒷부분 부터 정렬이 되며 앞뒤값을 비교 해서 자리바꿈을 한다는것입니다. 이해가 돼셨는지 잘 모르겠습니다  . T.T

혹시라도 질문있으신 분은 메일 주세엽...~~ caelin@dreamwiz.com

Back