내가 사랑하는 알고리즘

아.. 글고.. 아랫분...
kruskal 말씀하시는거져? shortest path가 아니공..
minimum spanning tree구하는 것으로 알고있는데..
shortest path는 Djikstra일껄여..
kruskal말고 prim도 생각나는군여..

1. RSA 등의 공개키 알고리즘

알고리즘 자체 뿐만 아니라 그것을 빠르게 계산하는 방법들에 대한 알고리즘도 정말 놀라웠습니다.

2. Splay Tree

insert, find, remove를 모두 splay로 해결하는 것도 그랬고 amortized cost라는 개념도 정말 신기했었습니다 ^^

전 많은 알고리즘을 알지는 못합니다....

가장 좋아한다기 보다는 가장 신기했던것 중의 하나가
FFT Series, FFT Trnasform 이었습니다.

관련 링크에도 나와 있군요.
DSP 하시는분들의 생각은 어떠신지 모르지만요....

"어설프게 손으로 작성한 알고리듬보다는 STL 알고리듬이 훨씬 낫습니다."
Scott Meyers의 'Effective STL'에서

흠.. 제가 사랑하는 STL의 70가지 알고리듬들입니다.

Nonmodifying Algorithms

for_each() Performs an operation for each element 334
count() Returns the number of elements 338
count_if() Returns the number of elements that match a criterion 338
min_element() Returns the element with the smallest value 340
max_element() Returns the element with the largest value 340
find() Searches for the first element with the passed value 341
find_if() Searches for the first element that matches a criterion 341
search_n() Searches for the first n consecutive elements with 344
certain properties
search() Searches for the first occurrence of a subrange 347
find_end() Searches for the last occurrence of a subrange 350
find_first_of() Searches the first of several possible elements 352
adjacent_find() Searches for two adjacent elements that are 354
equal (by some criterion)
equal() Returns whether two ranges are equal 356
mismatch() Returns the first elements of two sequences that differ 358
lexicographical_compare() Returns whether a range is lexicographically less 360
than another range.

Modifying Algorithms

for_each() Performs an operation for each element 334
copy() Copies a range starting with the first element 363
copy_backward() Copies a range starting with the last element 363
transform() Modifies (and copies) elements; combines elements 367
of two ranges 368
merge() Merges two ranges 416
swap_ranges() Swaps elements of two ranges 370
fill() Replaces each element with a given value 372
fill_n() Replaces n elements with a given value 372
generate() Replaces each element with the result of an operation 373
generate_n() Replaces n elements with the result of an operation 373
replace() Replaces elements that have a special value with 375
another value
replace_if() Replaces elements that match a criterion with 375
another value
replace_copy() Replaces elements that have a special value while 376
copying the whole range
replace_copy_if() Replaces elements that match a criterion while 376
copying the whole range

Removing Algorithms

remove() Removes elements with a given value 378
remove_if() Removes elements that match a given criterion 378
remove_copy() Copies elements that do not match a given value 380
remove_copy_if() Copies elements that do not match a given criterion 380
unique() Removes adjacent duplicates (elements that are 381
equal to their predecessor)
unique_copy() Copies elements while removing adjacent duplicates 384

Mutating Algorithms

reverse() Reverses the order of the elements 386
reverse_copy() Copies the elements while reversing their order 386
rotate() Rotates the order of the elements 388
rotate_copy() Copies the elements while rotating their order 389
next_permutation() Permutes the order of the elements 391
prev_permutation() Permutes the order of the elements 391
random_shuffle() Brings the elements into a random order 393
partition() Changes the order of the elements so that elements 395
that match a criterion are at the front
stable_partition() Same as partition(), but preserves the relative order 395
of matching and nonmatching elements

Sorting Algorithms

sort() Sorts all elements 397
stable_sort() Sorts while preserving order of equal elements 397
partial_sort() Sorts until the first n elements are correct 400
partial_sort_copy() Copies elements in sorted order 402
nth_element() Sorts according to the nth position 404
partition() Changes the order of the elements so that elements 395
that match a criterion are at the front
stable_partition() Same as partition(), but preserves the relative order 395
of matching and nonmatching elements
make_heap() Converts a range into a heap 406
push_heap() Adds an element to a heap 406
pop_heap() Removes an element from a heap 407
sort_heap() Sorts the heap (it is no longer a heap after the call) 407

Algorithms for Sorted Ranges

binary_search() Returns whether the range contains an element 410
includes() Returns whether each element of a range is also 411
an element of another range
lower_bound() Finds the first element greater than or equal to 413
a given value
upper_bound() Finds the first element greater than a given value 413
equal_range() Returns the range of elements equal to a given value 415
merge() Merges the elements of two ranges 416
set_union() Processes the sorted union of two ranges 418
set_intersection() Processes the sorted intersection of two ranges 419
set_difference() Processes a sorted range that contains all elements 420
of a range that are not part of another
set_symmetric_difference() Processes a sorted range that contains all elements 421
that are in exactly one of two ranges
inplace_merge() Merges two consecutive sorted ranges 423

Numeric Algorithms

accumulate() Combines all element values (processes sum, 425
product, and so forth)
inner_product() Combines all elements of two ranges 427
adjacent_difference() Combines each element with its predecessor; 431
converts absolute values to relative values
partial_sum() Combines each element with all of its predecessors; 429
converts relative values to absolute values

반드시 안정적이야 하는 큰 규모의 프로그램을 하다보면, 현란한 알고리즘을 적용하기가 꺼려질 때가 많습니다. 속도도 빠르고 보기도 좋은 것들이 많이 있지만, 그냥 단순하게 하는 것이 보다 안정적이기 때문이죠.

하지만, 그래도 너무 속도가 떨어지면 그나마 만만한 해쉬를 쓰는 경우가 생깁니다. 간단하게 이중 해쉬 정도 쓰고, global variable을 써서 미리 stack 으로 잡은 어레이로 pool 을 만들어 놓으면 가장 속 편하더군요.