내가 사랑하는 알고리즘

권순선의 이미지

/.에 올라왔던 내용입니다. 자세한 사항은 관련 링크를 참조하십시오.

Stridar writes "A paper presented in a recent article quotes Donald Knuth as saying the computer science has 500 deep algorithms. He mentions that Euclid's algorithm is one of the most important, and he seems to agree with the idea that CS will be mature when it has 1000 deep algorithms. What I would like to ask Slashdot is the following. What are the most important algorithms in CS? What is your favorite algorithm? And finally, what are the outstanding problems for which algorithms would be immediately placed in the "Top 1000" category."

여러분이 가장 좋아하는 알고리즘은 무엇이며, 즐겨 사용하는 알고리즘은 또 무엇입니까? 알고 있는 알고리즘들 중 가장 중요한 알고리즘은 무엇이라고 생각하시는지요?

익명 사용자의 이미지

쯧쯧 여기있는 인간들은 왜 한글 안 쓰고 전부다 영어만쓰냐
잘난척 하는거냐 -_-?
재귀호출을 재귀호출이라 부르면 되지 왜 recursion 이라고
같지도 않은 영어쓰냐 -_-;; 자증나는녀석들
글구 알고리즘이 쉽다구?
빙신들
정보올림피아드나 acm 문제나 한번 자기힘으로 풀어봤니?
강의나 책한번 들여봤다고 알고리즘 안다는것처럼 얘기를
하지마라~~~~~~~~~~~~~~~
제발 깝죽대지 말고 좀 찌그려져 있어라

익명 사용자의 이미지

한심한 녀석아.
언어로 구현하는 부분을 제거하고 논리적 부분만 고려한다면 그다지 어려울 것 없다는 lamp님 말씀이 이해가 안되나 보지?

익명 사용자의 이미지

저는 휴리스틱한 모든 앨거리듬을 좋아합니다. :)

뭔지 모르게 컴퓨터가 사람 냄새를 풍기는..

뭐랄까.. 인간미 넘치는 앨거리듬이랄까..

엉뚱한 접근으로 답을 찾아내는 방법은 재미납니다. :)

익명 사용자의 이미지

^^

저도 random 알고리즘을 상당히 좋아하는 편인데...

ASA 나 유전자 알고리즘에 상당한 매력을 느꼈었죠^^;;

올해 ACM 대회에 대해 함 알아볼까 생각중인데 큼큼.. 흐흐 ㅡㅡ;;

경문의 이미지

스택(stack). 다른것들에 비해 쉬우면서도 기본을 다져준 알고리즘입니다.

사실 프로그래밍하면서 가장 많이 사용하게 되는 것은
recursion 입니다. 가독성을 많이 잃어가면서까지 저는
비비꼬거나 한줄로 만들려는 나쁜습관을 가지고 있습니다.

요즘 고민하는것은 사람이 쉽게 이해 할 수 있는 소스를
작성하는법입니다. 어떤책에 보니 컴퓨터가 이해할 수 있는
소스는 바보도 만들수있다는 말에 충격을 받아서..

--
#include

#include

dawnsea의 이미지

저는 가독성을 위해서 더 많은 줄로

코드를 늘여쓰고 더 많은 공백과 더 많은 빈 줄을 삽입합니다. ㅡ.ㅡ;

탭의 리듬을 즐기는 편이라나요. ㅡ.ㅡ;

익명 사용자의 이미지

저하고 비슷한 성향을 가지고 계시는군요.

*^^*

익명 사용자의 이미지

recursion은 속도를 위해서는 사용을 삼가하는 것이 좋습니다.

글씀이 : 겁쟁이 아님 나는 lamp임

익명 사용자의 이미지

recursion은 개발속도를 위해서 자주 사용합시다 ^^

익명 사용자의 이미지

recursion이 빠르냐 명시적인 사용자stack사용이 빠르냐는 문맥과 구현에 따라 달라지는 문제입니다.. 문맥에 대한 아무런 정보 없이 어느쪽이 빠르다고 결론내릴 수는 없는거죠

리커젼이란 것도 (시스템이 제공하는) 스택을 사용하는 거니까, 결국 함수 호출시 인자전달을 얼마나 효율적으로 하게 할 수 있느냐 vs 사용자구현 스택을 얼마나 효율적으로 구현하고 사용할 수 있느냐를 고려해서 결정할 문제죠

사실 아주 개판으로 만들지 않는 이상, 아주 크리티컬한 문맥이 아니면 리커젼이든 사용자스택이든 그리 큰 차이는 나지 않으리라 봅니다

익명 사용자의 이미지

(그리고 물론 간단한 recursion의 경우는 iteration으로 대치가능하겠죠; lamp씨의 얘기는 이 얘기 같음)

wizcat의 이미지

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

wizcat의 이미지

지금 생각나는 알고리즘은..
radix sort, shortest path, 그리고 ACM에 자주나오는 union and find...등등..
무엇보다도 가장 기억에 남는것은..
state minimize하는 tabulation method..
저거 구현할라구 일주일동안 20시간 밖에 못잤다는..

익명 사용자의 이미지

lamp님의 글을 모두 읽었습니다.
처음에는 이해도 잘 안되고 태도도 마음에 안들어서 감정부터 안 좋았습니다. 그러다가 몇번 더 읽으면서 생각하니 상당히 동감이 가는 부분이 많았습니다.
특히 종교가 마약에 비유되는 면에서는 처음에 강한 거부감이 생겼는데 사실은 나도 이 마약에 중독이 되었기 때문이란 걸 조금씩 느끼게 되었습니다.
교회에서 울고불고 하던 모습들 나는 그것이 회개하는 모습이라 여겼는데 지금 생각하면 참 어리석었습니다.
얼마전 TV에서 테러를 하고 죽은 소녀가 알라신께 기도하던 모습이 나의 생각을 되돌아 보게 한 것 같습니다.
이런글이 이 토론장에서 어울리지 않겠지만 제가 이토론장에서 글을 읽고 변하게 되었으므로 이글을 남깁니다.
감사합니다. lamp님!

익명 사용자의 이미지

전 이렇게 생각합니다.
알고리즘은 쉽다!
단! 이미 나와있는 알고리즘을 구현한 소스를 가져다 쓰거나 아주 쉽게( or 허접하게) 풀이해놓은 문서를 볼때...

저도 알고리즘을 공부한지 좀 되는 사람인데,...
정말 알고리즘이란건 파도파도 끝이 없고, 어렵기로는 한이 없는것 같습니다. 그리고 남과 조금은 다른 관점에 접근을 해야 새로운 알고리즘을 발견할 수 있다는 것.
Krustra(철자가 맞는지 모르겠지)알고리즘을 보면 정말 그 원리는 쉽고 간단하죠. 하지만 최단거리를 구하기위한 알고리즘을 생각해 낼때 과연 몇 명이나 Krustra알고리즘과 같은 생각을 했을까요?

제 결론은 그렇습니다.
수박 겉 핥기 식으로 나가면 쉽죠... 어느 알고리즘이든 쉽죠.
하지만 그 알고리즘의 진짜의미를 파악하려 한다면 정말 어려울겁니다.
거기에 새로운 알고리즘을 만들어낸다는건 더 어렵겠죠...

익명 사용자의 이미지

이쪽으로 공부를 시작한지 벌써 8년째이지만 한때는 이쪽 공부가 너무 어려워 흥미를 잃고 있었던 적이 있었습니다.
그때 한 교수님이 어차피 공부란 자기가 무엇을 모르는지 알아가는 과정일 뿐이지 않겠느냐는 말을 하시더군요. 제가 NP문제에 관해 질문했을때 한시간 넘게 답변해 주시고도 제대로 된 답변을 못해줬다고 미안해 하시던 분이었습니다. 그 분은 일리노이대에서 알고리즘을 전공하신분이었는데도 말이죠.
Knuth같은 교수의 글에서도 알고리즘이 쉽다는 말은 본적이 없는데 여긴 정말 대단한 분들만 계신가 봅니다.

김영희의 이미지

알고리즘 솔직히 별로 어렵지 않죠...
왜냐구?
이미 남들이 다 해놓은거 보고있으니까!!!

언제나 그런거 같아요.
누군가 좀 쓸만하게 만들어 놓으면 이렇게 하는거지...
그럼 그렇게 할수밖에 없어...

그리구 한참이 흐른다음에... 다른 누군가
어 그것보단 내가 한게 좀더 좋은거 같은데...
하면 다르놈이 와서
맞아 전에 그놈 알고리즘 졸라 구려...
그런식의 이야긴 많죠...

정작 필요해서, 대기리 뽀개지게 고민해서 만들어 놓으면
너무도 쉽게 배우니... 그렇게 쉽게 느껴 지나 보죠?

밤세면서 졸라 닭질해가면서 프로젝트 마감할때... 해결책은 안보이는데 해는 떠오르고... 결과는 나와야 하는데...
똥줄이 타면서 허우적 대다보면 정말 스스로 한심하게 느껴지죠... 왜 난 그러한 졸라 허접한 알고리즘 하나도 못생학해낼까... 지금 이문제들 한방에 날릴만한 그러한 것이 떠오르지 않는것일까...

익명 사용자의 이미지

자료구조 책에 나온 알고리즘 별로 인상깊은 것이 없었음.
그걸 대단한 것인양 이야기하는 교수가 한심했음.
약간만 생각하면 되는 것을 책에 씩이나 기술?
미친놈들! 대가리 덜 떨어진줄 모르고
나는 그보다 괴델이란 학자가 논리의 완전성을 두장남짓 분량으로 서술한 논문에 감명!
더 놀라운 것은 그 것의 적용범위가 무한하다는 사실!

익명 사용자의 이미지

아~ 거 참 시원하다. 쓰레기같은 글에 당연히 붙어야할 점수가 붙었구나.

익명 사용자의 이미지

넌 증명은 안하고 그냥 읽기만 했나 보구나.

어디 한번 그 허접한 algorithm 들 맞는건지 틀리는건지 증명좀 해 봐라.

거기 있는것들 웬만큼 증명할 수 있을 정도면

기타 등등 수학에 있는 여러가지 theorem 이나 algorithm 들 증명하는데

전혀 애로사항이 없을것 같은데.

익명 사용자의 이미지

그래 문제없다.

익명 사용자의 이미지

단, 내가 본 책에 나온 내용정도라면

Fundamentals of Data Structures in C - Horowitz 기타등등

익명 사용자의 이미지

겨우 그런거 보고 책을 봤다고 주장하냐.. 한심하구만.

익명 사용자의 이미지

그래 니가 한번 Turing Award 좀 받아봐라.

그 허접한 전산장이들에게 주는 최고의 명예를 안겨주는 상 중에 하나인데

어디 한번 대한민국 최초로 Turing Award 좀 따먹어봐라.

익명 사용자의 이미지

받을 자격 충분히 있다.
걱정마라 곧 받을 예정이니

익명 사용자의 이미지

사실 언어로 구현하는 과정을 접어두고 대다수의 알고리즘을 그 자체만으로 평가한다면 대단할 것도 없고 어려운 것도 없어요.
내가 보기에는 전산쪽에 종사자들 대가리가 모자란 것 같아요.
특히 수학은 아주 꽝!
그런돌로 미국놈들 배만 채워주기에 급급한 것 같음
한심한 인간들

익명 사용자의 이미지

지식이 얇으면 쉬워 보이고 깊으면 깊을수록 어려운거 아니겠어요..

익명 사용자의 이미지

너같은 녀석은 병원의 환자 수술이 쉬워 보이겠지.
그리도 일반상대성 이론도 마찬가지고
안그래? 등신아

slayer의 이미지

의사의 고충을 알기에 수술이 어렵다는 것을 알고..
물리에 대해 어느 정도 지식이 있기에 상대성 이론이 어렵다는 것을 아는 거겠지요..
내가 보기엔 당신은 저런 최소한의 지식도 못 갖춘 사람 같소이다..

익명 사용자의 이미지

당신은 바른 추론 능력이 없는 것 같소?
이런 경우는 방법이 없지요

저야 최소한의 지식이 없다니 쌓으면 되겠지만

익명 사용자의 이미지

대체 윗/윗글의 어느부분으로 추론능력이 없다는 결론이 나오는지 당신의 추론을 듣고 싶구만 :)
자기도 남의 권위에 의존하지 않고선 얘기도 못하는 주제에 깔아뭉개긴
괴델? 풉

익명 사용자의 이미지

완전성이 아니고 불완전성임..
그리고 그렇게 잘났으면 어디어디에 적용이 되는지도 말해줄래요?

익명 사용자의 이미지

돌대가리야! 논리의 완전성이다.
그리고 이것을 수학에 적용해서 해결한 문제가 수학의 불완전성이다.
Are you understand?
그리고 종교에 대입하면 지금 종교싸움이 무의미해지지
한마디로 평화가 온다 이거야 알간?

익명 사용자의 이미지

저, 사실은 are you understand? 보다는
do you understand? 가 올바른 문장인것 같네요 -_-;

익명 사용자의 이미지

미안하다.
영어가 딸려서

익명 사용자의 이미지

근데 이것은 내 잘못이 아니고 이 엿같은 게시판 잘못이라오
틀린 것을 보고도 고칠수가 있어야지?
내가 혹시 이 게시판 사용법을 모르는 것인가?

익명 사용자의 이미지

논리의 완전성인지 뭔지.. 모르겠지만..
그렇게 잘난거면..
지금 종교싸움은 왜 있는건지..
종교에 대입을 못해서 그런건가???
어디서 어줍잖게 논문 한편 읽어와서 너무 잘난체 하는거 아닌지...
사람이 잘났으면 겸손할줄도 알아야 하는거 아닌가요??..

각설하고...
전 알고리즘에 대해 잘 아는것은 없어도...
가장 기억에 남는 순간은...
대학교 1학년때..처음으로 Linked list에 대해 알았을때 입니다.
일종의 사고의 전환이 있었던거 같아요..

익명 사용자의 이미지

괴델이 무신론자 걸랑
그래서 서구 사회에서 이단아 취급받지.
그리고 서구사회는 기독교라는 마약에 빠져 있고
이슬람권은 이슬람교라는 마약에 빠져 있기 때문이지
이 두놈들 화해시키는 방법은 압도적인 힘을 가진 제삼자가 그 힘으로 이들을 이끌어 줄때만이 가능하지
하지만 현재 누가 이런역할을 할 수 있지?

비유를 들자면 마약 중독자들을 갱생시키기 위해 제삼자인 국가기관이 그 강력한 힘으로 그 사람을 갱생시키는 것 외에는 방법이 없는 것과 비슷하지.

익명 사용자의 이미지

돌에게 간략히 설명하지요.
논리의 완전성을 간단히 말하면 결론은 바른 추론과정을 통해 전제가 결론을 보장한다는 소린데 넘 당연한 소리고 그래서 전제의 진실 여부가 중요하지. 이점이 수학의 공리를 선정하는데 심혈을 기울여야 하는 이유이기도 하고 마찬가지로 수학이 불완전한 이유이기도 하다.
그러면 종교를 본다면 불교-연기론 기독교-신의존재 회교-신의존재 기타등등 이런 전제들을 인정하면 거기서 추론된 결론들이 추론과정만 바르다면 부정할 방법이 없다. 따라서 네놈들이 신을 믿고 연기론을 믿는다면 네놈들이 정신 박약아가 아닌 다음에야 옳은 것만 따른다면 옳은것이니 니들 좆대로 살거라 하는 논리가 성립되거든 싸울 이유가 뭔가? 없쟎아!
근데 문제는 종교한다는 새끼들 바른 추론과정을 무시하고 무조건 집단의 이익만을 우선시하는 경향이 강하거든 더구나 종교를 아래로 놓고 위에서 공평히 바라보기에는 종교라는 마약에 너무 빠져서 불가능해!
현 상황에서 가장 좋은 방법은 판단능력이 부족한 어린이에게 종교가 접근하는 것을 막는 것이 급선무지
그렇지만 이것은 절대 불가능하기 때문에 결국에는 다투다가 모두 사라지는 걸 막을 수 없어
인간이 얼마나 한심한 동물인지는 이쪽에 종사하는 인간들만 보아도 알수 있지 이만 끝

익명 사용자의 이미지

아씨..졸라 어렵다!!!!

익명 사용자의 이미지

남들에게 인정받고 싶은 욕구..
똑똑한 나를 인정안하는 니네들은 모두 한심한 돌대가리다!

하고싶은 말은 결국 이거겠지.

익명 사용자의 이미지

너같은 반응을 보이는 녀석이 머리는 작고 자존심만 센 전형이지
너같은 돌에게 인정받아서 어디다 써먹지?

익명 사용자의 이미지

나도 한심하다. 그러니 리플 달지마라. 등신들아

slayer의 이미지

이 사람은 무슨 횡설수설을 하는 것인지..
헛소리 하려거든 로그인 해서 쓰시구려..-_-

익명 사용자의 이미지

ID : lamp
됐냐?

익명 사용자의 이미지

아하~ 누구신가 했네
자기가 짠 C++프로그램이 C보다 100배 느리다고 자랑하던 분이시구만 :)

익명 사용자의 이미지

요즘엔 C++로 그냥 짜도 C 보다 한 10배쯤 느리지 않나요?

익명 사용자의 이미지

학교 숙제 알고리즘 문제였다던데요
삽질하지 않는 이상 그렇게 차이나진 않죠
물론 C는 0.000x초 걸리고 C++은 0.0x초 걸렸다는 식의 수치를 대던걸로 봐선
제대로 된 측정도 아니었겠지만

익명 사용자의 이미지

후후 나 스타됐군

익명 사용자의 이미지

Rough set
요즘 요걸 공부하는데...
재미있으면서도 어렵네요.. ㅡ.ㅡ
이걸로 좋은 검색엔진이나 만들면 좋을텐데.. ^^

익명 사용자의 이미지

최강의 알고리즘인

시뮬레이티드 어닐링 and randomization -_-;;

clhitter의 이미지

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

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

2. Splay Tree

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

익명 사용자의 이미지

Stridar는 씁니다.

종이는 그 컴퓨터 과학이 500가지 깊은 알고리듬을 가지고 있는 것을 말하는 것으로써 최근 품목 인용구들 Donald Knuth에 제시되였습니다.

그는 Euclid의 알고리듬이 중요한 최대량중의 하나인 것을 언급합니다, 그리고 그는 CS가 그것이 1000가지 깊은 알고리듬을 가지고 있을 때 익을 것이다라는 생각과 일치하는 것처럼 보입니다.

내가 Slashdot를 물어보고 싶는 것은 다음에 말하는 것입니다.

그 가장 중요한 알고리듬은 CS에 무엇입니까?

당신의 흥미있는 알고리듬은 무엇입니까?

그리고, 마침내, 알고리듬이 수석 1000 범주에 즉시 놓일 것인 뛰어난 문제인 것 .
..

bootflag_의 이미지

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

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

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

유진호의 이미지

Lebenberg-Marquardt optimization method.

논문 작업하면서 너무나도 큰 일을 해결해 주었지요.

익명 사용자의 이미지

stl ㅋㅋ 정말 좋죠 아래 어떤 분의 말처럼. 직접작성한 허접한 알고리즘보다 검증된 알고리즘. ㅡㅡ^ 난 언제 이런거 뛰어넘나. . . ㅡㅡ^

cjh의 이미지

red-black tree랑 b+ tree...

뭐... 만들어진 것 보면 대단한데 처음에는 어떤 생각으로
만들게 되었을까 궁금한 것들이 있죠. 그런 걸 만든 사람들은
정말 천재라는 생각을 해 봅니다.

--
익스펙토 페트로눔

익명 사용자의 이미지

b+ tree .. 정말 대단하죠..

자료구조 공부하던 당시..
이부분에서 감동과 흥분으로 몸에 전율을 느꼈었죠..
피가 거꾸로 흐르는 듯한 짜림함 같은... 지금 생각해두 소름(-_-)끼칩니다.

praise의 이미지

quick sort 알고리즘 정말 멋지지 않나요?
그리고 counting sort 알고리즘 역시 정말 기발하죠... 특정 조건하에서 O(n) 시간에 소트할 수 있다는 사실에 너무 감동했었죠...

익명 사용자의 이미지

counting sort 가 혹시 bitmap sort 라고도 불리우는 거랑 같은건가요?

liberta의 이미지

이런 저런 멋진 알고리즘이 있지만...

특히 random number generator 알고리즘들... 자주 쓰면서도
고마움을 깜빡하곤 합니다. ;-)

익명 사용자의 이미지

Simplex 정말 편합니다.

bookworm_의 이미지

infinite state machine........ ^_^

Bookworm

cedar_의 이미지

"어설프게 손으로 작성한 알고리듬보다는 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

lovehis의 이미지

별로 잘 이해 하지는 못하지만...
그리고 도저히 내 실력으로는 완벽한 코딩이 불가능 할 것도 같지만...

LR 파싱 알고리즘....

그게 없었으면... 정말 고생 많이 했을꺼에요...
사실 그 알고리즘 보다는 yacc이 없었다면...
당연.. yacc는 LR이니까...

만일 yacc과 LR이 없었다면... 생각만 해도 끔찍...
아직도... 지금 우리가 쓰는 컴파일러가 아니라 우리가 15년 전쯤에 쓰던 것을 지금도 쓰고 있을지도... 10년 더 전일까...

암튼... D. E. Knuth 대단한 사람 임니다.
--
늘...

kils_의 이미지

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

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

익명 사용자의 이미지

상화에 맞는 널리 쓰이는 알고리듬이 있다면 사용하는게 좋지 않은가요?
이미 검증된게 안전하죠. (물론, 저 같은 허접만 해당될지도... ^^;)

kils_의 이미지

상황에 맞는 알고리즘을 쓰는 것이 가장 좋겠죠. 하지만, 실제 상황에
들어가다 보면 종종 경험하는 것이지만, 분명히 확신할 수 있는 알고리즘을
쓰는 경우에도 이상하게 작동하는 경우가 생기는 일이 발생하곤 합니다.

특히나 다음과 같은 경우가 하나씩 덧붙여 질때마다 그럴 확률이 기하급수적으로 늘어납니다.

- 프로젝트 규모가 큰 경우 (ex. 모듈하나에 만라인이상, 수백개 이상의 모듈..)
- 작업기간이 길 수록 (ex. 최소 1년 이상)
- 팀내에서 많은 사람들이 공동 작업을 하는 경우 (ex. 수십명 이상)
- 여러회사가 같이 작업할 때에
- 대규모 다양한 시스템의 공동 운영이 요구되는 경우에는
- 비표준화된 하드웨어에 탑재되는 경우 (ex. embedded virgin system)
- 기간산업과 연계성이 큰 곳에 적용되기 때문에, 한번의 에러가 심각한 (너무도 심각한) 파급효과를 낳는 경우

이러한 시스템에서는 자신의 선호도 대로 프로그램하기가 매우 겁이 나지요. T_T

때로는 메모리 할당 (heap) 하나 하는 것도 손이 부들부들 떨립니다. 하다못해 함수 호출 또한 요구되는 stack 사이즈의 overflow 가 나지 않을까 두려워 질때가 있습니다.

학교에서 배운 많은 것들이 회사에서는 거의 안쓰이는 경우가 흔히들 있는데, 이상적인 케이스들이 현실상황에 와서 미처 고려하지 못한 것 들 때문에 못쓰게 되는 상황이 많습니다. 뭐 이런 것이 짬밥이라고 회사선배들은 말하곤 합니다만..

익명 사용자의 이미지

자주 쓰지는 않지만 그냥 좋아하는 알고리즘? 자료구조인가?

binary search

log n 의 환상적인? 속도를 자랑함..