|
강좌 전 태오의 잡담>
김민오님의 알고리즘 강좌 그 두번째 이야기입니다. ^^ 이번 내용은 꽤 유익한 것들로 구성되었네요
강좌 시작 >
Replace 함수와 bubble_sort 알고리즘
첫강의를 마치고 나서 생각보다도 많은 분들이 격려의 메일을 보내주셔서 너무 감사 했습니다. 아직 알고리즘이 무엇이고 왜 배워야 하는지 모르겠다고 하신 분들도 꽤 많았습니다. 그중 어떤 분이 그러시더군요 .
"평범한 웹디자이너는 포토샵을 잘다루고 뛰어난 웹디자이너는 남들이 따라올수 없는 감각이 있다.."
제가 말안해도 이뜻이 무엇인지 잘알것이고 .. 우리는 감각을 배우기위해 알고리즘을 배운다 생각하셔도 됩니다. 강좌가 조금 늦었는데 어떤강좌를 해야 할지 솔직히 제 스스로 기준이 잡히질 않았었습니다. 좀 더 이론적으로 가야 할것인가 아니면 실무에 필요한것을 가르쳐 드려야 하는지 T.T 일단 주제가 알고리즘이기 때문에 replace 를 함수를 만드는 법과 문자열을 정렬하는 법을 알려드리겠습니다.
사실 asp 에서 string 을 다루기는 굉장히 쉽습니다. 각종 함수들이 지원을 해주기 때문에 어렵지 않게 문자열을 자를수도 있고 문자열을 바꿀수도 있습니다. 또한 문자열을 추가 할수도 있습니다. 하지만 다른언어를 해보신분들은 아시겠지만 이 문자열을 다룬다는것은 상당히 복잡하고 귀찮은 일이기 까지 합니다.
가까운 예를 들어 여러분은 게시판을 만들때 작은따움표 문제를 해결하기 위해 replace(str, "'", "''" ) 가 항상 들어 갑니다. 하지만 asp 와 같은 웹스크립트 언어인 jsp 에는 replace 함수가 없습니다. 그렇다면 어떻게 해야 할까요...게시판 위에다가 " 작은 따움표가 들어가면 에러가 나니 쓰지 말아 주세요 " 라고 하면 될까요 ?
아 이런것은 우리 프로그래머의 자존심이 용납하지 못합니다.. 그렇다면 우리는 asp 에 replace 라는 함수가 없다고 생각하고 replace 함수를 만들어 보도록하죠.. 이것의 성능은 기존의 replace 함수보다 빠르다거나 하지는 않을것입니다. 왜냐하면 그 replace 함수는 분명 c언어로 만들어 졌을테니까요 .. 우리는 단지 원리를 알고나서 " 필요한 함수따위는 언제든지 만들수 있어!!! " 라는 자신감과 문자열을 다루는 방법에 대해서만 알면 됩니다.
일단 우리는 left 함수와 right , mid , len 함수는 사용할수 있다고 가정해야 합니다. 이것은 asp 로 구현하기는 거의 불가능합니다. C에서는 포인터 라는것이 있기 때문에 이런함수까지도 만들수 있지만 asp 에서는 그정도까지는 힘이 드내요 T.T
replace 함수의 원리는 간단합니다 str 이라는 문자열이 있고 여기서 ' 를 찾으면 '' 로 바꿔서 str에 저장만 시키면 되는 것입니다. 아 그전에 여러분들에게 함수에서 메모리 주소의 전달과 값전달의 차이에 대해서 말씀을 드려야 할 것 같습니다. 일단 우리는 포인터가 무엇인지 잘모르는 분들이 많고 asp 에서 포인터는 구현할수도 없을뿐더러 사용할 일도 거의 없습니다.
그런데 우리는 알게 모르게 포인터 개념과 비슷한것을 사용하고 있습니다. 바로 레퍼런스라는 것이지요.. 이것은 포인터가 너무 어렵기 때문에 java 나 C# 에서 포인터를 대체 하기 위해 나온것인데 일단 및의 함수를 보면서 설명하겠습니다.
|
<%
sub test(str_mother)
str_mother = "엄마돈없다."
end sub
str_me = "엄마돈줘"
call test(str_me) ' 함수 호출
response.write str_me ' <- 여기서 과연 어떤값이 찍힐까요.. (직접한번씩 해보세요 . )
%> |
해보시면 알겠지만 str_me 에는 "엄마돈없다." 라는 문자열이 들어가 있습니다. 이상합니다.. 우리는 str_me 라는 변수에 값을 넣어준적이 없고 단지 파라미터인 str_ mother 에만 "엄마돈없다." 라는 문자열을 넣어 줬는데 str_me 값도 변경 되었습니다.
이게 왜이렇게 되냐면 vb나 asp 는 기본적으로 call by reference 를 사용해서 함수에 값을 전달 합니다. 즉 call test(str_me) 라는 함수를 호출하면 str_me 에 들어있는 "엄마돈줘" 라는 값이 넘어 가는 것이 절대 아닙니다 . 내부적으로 로는 str_me 의 메모리 주소가 넘어 갑니다..
그렇게 str_mother 는 str_me 의 메모리주소를 읽어와서 str_me 와 동일한 주소를 같게 되고 str_mother 는 str_me 가 가르키고 있는 주소와 동일한 주소를 갖은 상태에서 str_mother 의 값을 = "엄마돈없다" 로 바꾸게 되면 동일한 메모리주소를 가리키고 있는 곳의 값이 변경되게 때문에 str_me 의 값도 변경이 됩니다.
즉 변수의 이름은 다르지만 같은 메모리 주소값을 갖게 해서 하나의 변수값을 변경하면 그 메모리주소가 가르키고 있는 값도 변경이 됩니다. 이것은 상당히 편리한 방법이고 알게 모르게 우리는 전부 call by reference 를 사용하고 있었던 것입니다. 하지만 변경되지 않고 값만 넘겨줘야 할때도 있습니다.. 이것을 call by value 라고 하고 속도도 약간 빠르다고 합니다.
|
str_me = "엄마돈줘"
sub test(byval str_temp)
str_temp = "엄마돈없다."
end sub
call test(str_me)
Response.write str_me '-> 이것의 값은 "엄마돈줘" |
파라미터 앞에다가 byval 이라고 해주면 메모리 주소는 필요 없이 값만 전달 받겠다는 뜻입니다.
사실 이것은 asp 보다는 여러분이 vb 공부 하실때 많이 도움이 될듯하고 또 이번에 배울 함수에 서 call by referance 를 사용해야 하는데 여러분들이 헉갈리실까봐 미리 말씀 드렸습니다.
1. replace 함수 만들기
일단 str_mother = "엄마'천원'만줘" 에 작은 따움표가 두개 들어 있습니다. 우리는 이것을 "엄마''천원''만줘" 로 만들어야 합니다. 원리는 아주 간단합니다 들어온 문자열을 한개씩 잘라서 비교 한다음 작은따움표라면 큰따움표로 바꿔주면 되는것입니다. 초보자분들이 여기서 잘못하는것이 문자열을 한개씩 자르는 것과 마지막에 문자열을 하나씩 더해서 다시 새로운 문자열을 만들어 되돌려 주는것을 대부분 잘 못합니다. 밑에 소스를 잠깐 보겠습니다.
|
<%
str_mother = "엄마천'원'만줘" '초기의 문자열
call replace_str(str_mother, "'", "''") ' 함수 호출
Response.Write str_mother ' str_mother
sub replace_str (byref str , byval equal , byval change) ' (문자열, 비교할문자, 바꿀문자)
for i = 1 to len(str) ' 반복문은 str의 길이 만큼돈다.
str_temp = mid(str, i , 1)
' 이런식으로 하면 str_temp 에는 한개의 문자씩이 담긴다 즉 처음에는 "엄"
' 두 번째 반복문째에는 "마" 이런식....
if str_temp = equal then ' 만약에 "엄" 이라는글자가 작은따움표 와 같다면
str_temp = change ' 큰따움표로 바꾼다.
end if
str_return = str_return + str_temp
' 문자열을 하나씩 더해서 다시 하나의 문자열을 만든다. < BR > next
str = str_return
' 되돌려 준다. (여기서 이게 가능한 이유는 byref 즉 call by reference 이기 때문)
end sub
%> |
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 '
5. 결과 값을 되돌려준다 ( 사실 되돌려준다는 말은 틀린 것이다 같은 메모리 주소에 저장 시킬 뿐이다. )
str = str_return
' for 문이 끝난뒤에 그 값을 저장한다 (이것은 call by referance 이기때문에 가능하다.)
아마도 이 함수는 프로그램 경력이 있으신분들은 그리 어렵지 않게 스스로 만드실수 있을꺼라는 생각이듭니다. 이 원리를 이용하면 Trim (공백문자 제거 ) 함수는 쉽게 만들수 있습니다. . (이것은 여러분 스스로 한번 해봤으면 좋겠 습니다. )
이번에는 문자열 정렬에 관해서 알아 보겠습니다.
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가 제일 뒤로 보내지게 되면
2. 처음으로 돌아가서 b 와 a를 바꾼다.
그럼 "abdcef " 가 된다.
다음에 b d 를 비교한다.
d 가 더 크므로 교환할필요가 없다
교환할필요가 없어지면서 d 화 c를 비교한다
(처음에 말했듯이 자리를 옮기면서 옆자리하고만 비교를 합니다. )
c가 더 작으므로 교환해야한다. "abcdef"
그다음에는 d 와 e를 비교 한다.
(처음에 맨뒤로간 f와는 비교 하지 않는다.!)
이것이 bubble sort 의 기본 정렬 방법이다.
결국 "abcdef" 가 되고 제일 큰문자를 뒤로 보내가면서 중간중간 정렬을 해나가고 있
다.
3. 이미 "abcdef" 로 정렬은 다 되었지만 계속 해나간다면
다시 a 와 b를 비교하고 d까지만 비교 한다 (맨뒤로보낸 e, f 는 비교 하지 않는다. )
이 버블 소트는 비교적 어느정도 정렬이 되있는 문자를 정렬할때 굉장히 빠른 속도를 자랑하지만 역순으로 정렬되있는 문자를 정렬할때는 비교적 느립니다. 이유는 간단합니다 앞뒤 자리를 계속 바꿔줘야 하기 때문이지요.
이것을 asp 로 나타내 보면..
<%
strstring = "aslkjasdghglasdjfjfqhwejfasjdflkasfkhasdkjfals" ' 정렬할 문자열
Call bubble_sort(strstring) ' 함수 호출
Response.write strstring
Sub bubble_sort(str_string) '함수 선언부 문자열이 들어온다.
Dim i, j ' 변수 선언
Dim str_temp()
' 반드시 배열로 할필요는 없지만 배열에 문자열을 하나씩 저장해 두는 것이 편하다.
str_length = Len(str_string) '문자열의 길이를 미리 저장 해둔다 (속도 향상을 위해서임.)
ReDim str_temp(str_length) ' 문자열의 길이만큼 배열을 재선언
For i = 1 To str_length ' 문자열의 길이 만큼 반복문을 돈다.
str_temp(i) = Mid(str_string, i, 1) ' 문자열을 배열에 한글자씩 넣어주고 있다.
Next
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
str_string = ""
' 반복문은 모두 끝났다 값을 되돌려주기 위해 그전에 정렬 안된 문자열을 모두 지운다.
For i = 1 To str_length '이부분은 str_string 에 정렬된 문자열을
str_string = str_string + str_temp(i)
'넣어주는 과정이다. str_string 에는 정렬된 문자가 들어가게 된다.
Next
End Sub
%> |
지금 이 함수는 이글을 쓰면서 바로바로 만들고 있는것인데 뭔가 최적화 되지는 않은느낌입니다. 버블소트의 장점은 중간에 정렬이 다되었으면 끝까지 비교 하지 않고 중간에 멈출 수 있습니다.
이것을 소스에 넣으면 너무 복잡해 보이기 때문에 소스에서 뺐으며 중간에 멈출 수 있는 것은 버블소트의 장점입니다. 여러분이 직접 한번 해보시기 바랍니다 (힌트 : 문자열을 비교하다 교환이 일어나지 않으면 문자열은 정렬된상태 이다. 교환이 일어 나지 않을 때 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
이부분입니다. 여기서 어떤 분들은 왜 2중 for 문으로 하냐고 물어 보시는 분들도 있을텐데.. "54321 " 이라는 문자가 있을 때 반복문을 한번만 돌리게 되면 "43215"에서 끝나 버립니다. 다시 처음으로 돌아가야 하기 때문에 2중 for 문을 써야합니다.
사실 머리가 좋은 사람들은 이부분 정도는 머리로 따라가면서 결과 값을 예측하곤 하지만 한번씩 해보면서 이해하시길 부탁 드립니다. 가장 중요한 것은 버블소트는 뒷부분 부터 정렬이 되며 앞뒤값을 비교 해서 자리바꿈을 한다는것입니다. 이해가 돼셨는지 잘 모르겠습니다 . T.T | 
강좌 최초 작성일 : 2003년 07월 25일
강좌 최초 작성일 : 2000년 12월 28일