LCS(Longest Common Subsequence) 찾기
오... 완전 신기>_ <
LCS(X, Y)
for(i=1; i<=m; i++) L[i, 0] = 0
for(j=0; j<=n; j++) L[0, j] = 0
for(i=1; i<=m; i++)
for(j=1; j<=n; j++)
if(x[i] == y[j])
L[i, j] = 1 + L[i-1, j-1]
else if(L[i-1, j] >= L[i, j-1])
L[i, j] = L[i-1, j]
else
L[i, j] = L[i, j-1]
Bubble Sort
Bubble Sort (Ascending Order)
bubblesort(A)
N = the number of elements in A
for(i=0; i<n; i++)
for(j=0; j<n-(i+1); j++)
if(A[j] > A[j+1]) swap(A[j], A[j+1])
end
end
end
기본 원리는 아주 간단하다: 뒤쪽부터 올바른 값으로 채워넣는다. Insertion Sort 와 상반되는 방법이라고도 할 수 있다.
15, 38, 2, 1, -3, -10, 0, 11, -2, 9
이러한 자료를 담고 있는 배열을 정렬한다고 할 때
15, 2, 1, -3, -10, 0, 11, -2, 9, 38
2, 1, -3, -10, 0, 11, -2, 9, 15, 38
1, -3, -10, 0, 2, -2, 9, 11, 15, 38
-3, -10, 0, 1, -2, 2, 9, 11, 15, 38
-10, -3, 0, -2, 1, 2, 9, 11, 15, 38
-10, -3, -2, 0, 1, 2, 9, 11, 15, 38
-10, -3, -2, 0, 1, 2, 9, 11, 15, 38
-10, -3, -2, 0, 1, 2, 9, 11, 15, 38
-10, -3, -2, 0, 1, 2, 9, 11, 15, 38
-10, -3, -2, 0, 1, 2, 9, 11, 15, 38
이런식으로 동작한다. 여기서 이야기를 멈추면 중학생 수준의 포스트가 되어버리므로 계속 진행하겠다.
문제점
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
위와 같이 이미 정렬되어있는 배열을 정렬하려고 할 경우 똑똑하지 못한 모습을 보여준다. 더이상 정렬할 필요가 없는데도 불구하고 sig(i, 1, N-1) 번 실행된다.
발전된 형태의 알고리즘
bubblesort(A)
flag = N
while(flag > 0)
k = flag - 1
flag = 0
for(j=0; j<k; j++)
if(A[j] > A[j+1])
swap(A[j], A[j+1])
flag = j + 1
end
end
end
end
이미 정렬 되어있는 배열의 경우 O(N) 의 실행시간을 보여준다 (best case). flag 가 하는 역할에 주목할 필요가 있다. 이미 정렬된 부분을 표시함으로써 불필요한 연산을 하지 않도록 만들어준다.
각자 좋아하는 언어로 직접 구현해서 코멘트나 트랙백 다는것도 재밌을것 같다 ;-)
log(N)
CS345 이번 과제는 여러가지 해시 알고리즘을 직접 구현하는것이었다.
In the program spec, Dr. Moon wrote that a family of hash functions would be created by h sub k(s) = MyUtil.ELFhash(s, 2^k) for k > 0. Since M = 2^k, in order to find the value of k (so we can pass it into the argument of ElfHash when creating the extended function), we need to find the log2(M), am I correct? If so, how do I find this in Java? I cannot find any fuctions in Java's math utility that returns the log base 2 of a number.
메일링 리스트에 대략 이런 내용의 글을 올린 사람이 있어서 잠시 log(N) 의 값을 구하는 방법에 대해서 생각해보게 되었다. 사실 구할 필요도 없긴 하지만.
log(N)
c = 0
while(N > 1)
N = N >> 1
c = c + 1
end
return c
end
대략 의사 코드(pseudo code)로 작성해보았다. 길이가 짧기도 하고 복잡한 조건도 없어서 아주 예뻐보인다 :D
public int log(int n) {
int c = 0;
while(n > 1) {
n = n >> 1;
c++;
}
return c;
}
자바로는 이렇게 구현하면 될까나... 어떤 언어든지 1분 내로 구현할 수 있다고 본다. 어셈블리어는 제외.
이미 눈치 챈 사람도 있겠지만, N 의 값이 2의 k제곱이 아닐때에는 결과값이 floor of log(N) 이 된다. 아~ 이거 의외로 쓸만할지도 모르겠다.