당신이 좋아하는 알고리즘과 그것이 당신에게 가르쳐 준 교훈 [닫힘]

https://stackoverflow.com/questions/26301

09-06-2019
|

문제

프로그래밍 또는 특정 언어 기능에 대해 가장 많이 배운 알고리즘은 무엇입니까?

우리 모두는 갑자기 프로그래머가 작성한 알고리즘을 이해하고 진화 적 사다리를 몇 단계 올라간 것을 바탕으로 미래에 대한 중요한 교훈을 배웠습니다.누구의 아이디어와 코드가 당신에게 마법의 영향을 주었습니까?

해결책

"반복하는 것은 인간이고, 재귀하는 것은 신이다"-1989 년 대학에서 인용.

추신가입 초대를 기다리는 동안 Woodgnome에 의해 게시 됨

다른 팁

일반 알고리즘 :

Quicksort (및 평균 복잡성 분석)는 입력을 무작위 화하는 것이 좋은 일이 될 수 있음을 보여줍니다!;
균형 트리 (예 : AVL 트리 ), 검색 / 삽입 비용의 균형을 잡는 깔끔한 방법 ;
Dijkstra 및 Ford-Fulkerson 알고리즘 (두 번째 알고리즘에 많은 응용 프로그램이 있다는 사실이 마음에 듭니다)
LZ * 압축 알고리즘 제품군 (예 : LZW ), 데이터 압축은 일종의 내가 그것을 발견 할 때까지 나에게 마술 (오래 전에 :));
유비쿼터스 인 FFT (다른 많은 알고리즘에서 재 사용됨)
유비쿼터스 인 단순 알고리즘
수치 관련 :
- 두 정수의 gcd를 계산하는 Euclid의 알고리즘 : 첫 번째 알고리즘 중 하나 인 간단하고 우아하고 강력하며 많은 일반화가 있습니다.
- 빠른 정수 곱셈 (예 : Cooley-Tukey );
- 매우 강력한 메타 알고리즘 인 루트를 반전 / 찾기위한 뉴턴 반복
  수론 관련 :
  - AGM 관련 알고리즘 ( 예 ) : 이론은 상당히 심오하지만 (Gauss는 타원체를 도입했습니다.) pi를 계산하는 매우 간단하고 우아한 알고리즘으로 이어집니다. 함수와 모듈 형식을 사용하므로 대수 기하학이 탄생했다고 말할 수 있습니다 ...);
  - 숫자 필드 체 (정수 분해 용) : 매우 복잡하지만 상당히 좋은 이론적 결과 ( AKS 알고리즘에도 적용됩니다. 이는 PRIMES P)에 있습니다.
    양자 컴퓨팅 ( Shor 및 Deutsch-Josza 알고리즘) : 이것은 상자에서 생각할 수 있도록 가르칩니다.
    보시다시피 저는 수학 지향 알고리즘에 약간 편향되어 있습니다. :)

Floyd-Warshall 모든 쌍 최단 경로 알고리즘 라코 디스

이것이 멋진 이유입니다. 그래프 이론 과정에서 최단 경로 문제에 대해 처음 배울 때 아마도 단일 소스 최단 경로를 해결하는 Dijkstra의 알고리즘으로 시작할 것입니다. 처음에는 상당히 복잡했지만, 그 다음에는 극복하고 완전히 이해했습니다.

그런 다음 교사는 "이제 모든 소스에 대해 동일한 문제를 해결하고 싶습니다."라고 말합니다. "이런, 이건 훨씬 더 어려운 문제가 될거야! Dijkstra의 알고리즘보다 적어도 N 배 더 복잡 할 것입니다 !!! "라고 생각합니다.

그런 다음 선생님이 Floyd-Warshall을 제공합니다. 그리고 당신의 마음은 폭발합니다. 그런 다음 알고리즘이 얼마나 아름답게 간단한 지 깨지기 시작합니다. 그것은 단지 삼중 중첩 루프 일뿐입니다. 데이터 구조에 간단한 배열 만 사용합니다. <시간>

나에게 가장 눈을 뜨게하는 부분은 다음과 같은 깨달음입니다. A 문제에 대한 해결책이 있다고 가정합니다. 그러면 문제 A를 포함하는 더 큰 "초 문제"B가 있습니다. 문제 B에 대한 해결책은 실제로 다음보다 간단 할 수 있습니다. 문제 A에 대한 해결책.

빠른 정렬 .재귀가 강력하고 유용 할 수 있음을 보여주었습니다.

이건 사소하게 들릴지 모르지만 그 당시 저에게는 계시였습니다. 저는 첫 번째 프로그래밍 수업 (VB6)에 있었고 교수님이 방금 난수에 대해 가르쳐 주셨고 그는 다음과 같은 지시를하셨습니다. "가상 복권 기계를 만드십시오. 0에서 99까지 표시된 100 개의 탁구 공으로 가득 찬 유리 공을 상상해보십시오. 무작위로 선택하고 모두 선택 될 때까지 번호를 표시합니다. 중복은 없습니다. "

다른 사람들은 모두 다음과 같이 프로그램을 작성했습니다. 공을 골라 "이미 선택한 목록"에 번호를 넣은 다음 다른 공을 선택합니다. 이미 선택되어 있는지 확인하고, 그렇다면 다른 공을 선택하고, "이미 선택한 목록"등에 번호를 넣지 않으면 ...

물론 그들은 아직 선택되지 않은 몇 개의 공을 찾기 위해 수백 번의 비교를했습니다. 공을 고른 후 항아리에 다시 던지는 것과 같았습니다. 나의 계시는 골라 낸 후에 공을 버리는 것이었다.

이것이 너무나 당연한 것처럼 들리지만이 순간이 "프로그래밍 스위치"가 제 머릿속에서 뒤집힌 순간이었습니다. 이것은 프로그래밍이 이상한 외국어를 배우는 것에서 재미있는 퍼즐을 알아 내려고하는 순간이었습니다. 프로그래밍과 재미 사이에 정신적 연결을 한 후에는 정말 저를 막을 수 없었습니다.

Huffman 코딩은 내 것이 될 것입니다. 원래는 텍스트를 인코딩하는 비트 수를 8 개에서 그 이하로 최소화하여 나만의 멍청한 버전을 만들었지 만 주파수에 따라 다양한 비트 수에 대해 생각하지 않았습니다.그런 다음 잡지의 기사에 설명 된 허프만 코딩을 발견하고 많은 새로운 가능성을 열었습니다.

Bresenham의 선 그리기 알고리즘 은 실시간 그래픽 렌더링에 관심을 갖게했습니다.3D 모델 렌더링과 같은 작업을 위해 삼각형과 같은 채워진 다각형을 렌더링하는 데 사용할 수 있습니다.

재귀 하강 파싱 -이러한 간단한 코드가 어떻게 그렇게 겉보기에 뭔가를 할 수 있는지에 대해 깊은 인상을 받았던 것을 기억합니다.복잡한.

Haskell의 Quicksort : 라코 디스

당시 Haskell을 작성할 수는 없었지만이 코드와 재귀 및 퀵 정렬 알고리즘을 이해했습니다.방금 클릭을했고 거기에 ...

피보나치의 반복 알고리즘은 가장 우아한 코드 (이 경우에는 재귀 버전)가 반드시 가장 효율적인 것은 아니라는 사실을 잘 보여주었습니다.

정교하게하기- "fib (10)= fib (9) + fib (8)"접근 방식은 fib (9)가 fib (8) + fib (7)로 평가됨을 의미합니다.따라서 fib (8) (그리고 fib7, fib6)의 평가는 모두 두 번 평가됩니다.

반복적 인 방법 (forloop의 curr= prev1 + prev2)은 이런 방식으로 트리 아웃되지 않으며 재귀 스택의 n 프레임이 아닌 3 개의 일시적 변수이기 때문에 메모리를 많이 차지하지 않습니다.

저는 프로그래밍 할 때 간단하고 우아한 코드를 추구하는 경향이 있지만 이것이 좋은 소프트웨어를 작성하기위한 모든 것이 아니라는 것을 깨닫게 해준 알고리즘입니다.사용자는 코드가 어떻게 보이는지 신경 쓰지 않습니다.

어떤 이유로 Schwartzian 변환 을 좋아합니다. 라코 디스

여기서 foo ($ )는 $ (목록의 각 항목)를 가져 와서 비교 될 해당 값을 생성하는 계산 집약적 인 표현식을 나타냅니다.

Minimax 는 체스 프로그램이 영리하지 않고 더 많은 움직임을 생각할 수 있다고 가르쳐주었습니다.당신보다 앞서.

이게 알고리즘인지 아니면 고전적인 해킹인지 모르겠습니다.두 경우 모두 상자 밖에서 생각할 수있게 해주었습니다.

중간 변수를 사용하지 않고 정수 2 개 교체 (C ++) 라코 디스

Quicksort : 대학에 가기 전까지는 무차별 대입 버블 정렬이 가장 효율적인 정렬 방법인지에 대해 질문 한 적이 없었습니다.직관적으로 분명해 보였습니다.하지만 Quicksort와 같은 분명하지 않은 솔루션에 노출되어 더 나은 것이 있는지 알아보기 위해 분명한 솔루션을 지나쳐 보도록했습니다.

저에게 이것은 약한 힙 소트 알고리즘입니다. 왜냐하면 (1) 현명하게 선택한 데이터 구조 (그리고 그 구조에서 작동하는 알고리즘)가 성능에 얼마나 영향을 미칠 수 있는지, (2) 오래된 것에서도 매혹적인 것을 발견 할 수 있다는 것을 보여주기 때문입니다.잘 알려진 것들.(weak-heapsort는 모든 힙 정렬의 가장 좋은 변형이며 8 년 후 입증되었습니다.)

느린 것입니다. :)

Duffs Device 를 이해하고 일반적으로 C와 컴퓨터에 대해 많은 것을 배웠습니다. XOR 스왑

수정 :

@ Jason Z ,내 XOR 스왑 :) 멋지지 않나요?

어떤 이유로 Bubble Sort는 항상 저에게 눈에 띄었습니다.이름이 멍청해서 우아하거나 좋기 때문이 아닙니다.

좋아하는 항목은 없습니다. 선택할 수있는 아름다운 항목이 너무 많습니다.하지만 항상 흥미로운 것은 Bailey–Borwein–Plouffe (BBP) 공식 : 임의의 숫자를 계산할 수 있습니다.앞자리에 대한 지식없이 pi의.

RSA 는 모듈 식 산술의 세계를 소개했으며 해결 a 놀라운 번호 of 흥미로운 문제 !

많이 가르쳐주지는 않았지만 Johnson–Trotter Algorithm 은 결코 내 마음을 날려 버립니다.

바이너리 결정 다이어그램 , 공식적으로는 알고리즘이 아니라 데이터 구조이지만 우아하고 최소한의다양한 종류의 (부울) 논리 문제에 대한 솔루션.그들은 칩 설계에서 게이트 수를 최소화하기 위해 발명되고 개발되었으며 실리콘 혁명의 기초 중 하나로 볼 수 있습니다.결과 알고리즘은 놀랍도록 간단합니다.

배운 내용 :

모든 문제를 간결하게 표현하는 것이 중요합니다.작은 것이 아름답습니다
이를 수행하기 위해 재귀 적으로 적용된 작은 제한 / 감소 세트를 사용할 수 있습니다.
대칭 문제의 경우 표준 형식으로의 변형을 고려해야합니다.
모든 문헌을 읽지는 않습니다.Knuth는 BDD가 발명 / 도입 된 지 몇 년 후에 알게되었습니다.(그리고 거의 1 년을 조사했습니다)

저에게 Kelly & Pohl의 A Book on C 에서 참조 별 호출을 시연하기위한 간단한 교체는 처음 보았을 때 저를 뒤집 었습니다.나는 그것을 보았고 포인터가 제자리에 고정되었습니다.축 어적입니다... 라코 디스

하노이의 탑 알고리즘 은 가장 아름다운 알고리즘 중 하나입니다.반복적 인 방법보다 훨씬 더 우아한 방식으로 문제를 해결하기 위해 재귀를 사용할 수있는 방법을 보여줍니다.

또는 피보나치 수열에 대한 재귀 알고리즘과 숫자의 거듭 제곱 계산은 좋은 값을 제공하는 대신 재귀를 위해 사용되는 재귀 알고리즘의 반대 상황을 보여줍니다.

<인용구>

피보나치의 반복 알고리즘은 가장 우아한 코드 (이 경우에는 재귀 버전)가 반드시 가장 효율적인 것은 아니라는 사실을 잘 보여주었습니다.

피보나치에는 고정 된 수의 단계에서 결과를 직접 계산할 수있는 폐쇄 형 솔루션이 있다는 것을 알고 있습니다. 맞죠?즉, (phi ^{n -(1-phi) ^{n ) / sqrt (5).이것이 정수를 산출해야한다는 사실은 항상 저에게 다소 놀랍지 만 실제로는 그렇습니다.}}

파이는 물론 황금 비율입니다.(1 + sqrt (5)) / 2.

각 숫자를 현재 소수 목록과 비교하고, 찾을 수없는 경우 추가하고, 끝에 소수 목록을 반환하여 소수 목록을 생성하는 알고리즘입니다.여러 가지 방법으로 마음을 구부립니다. 그 중에서도 부분적으로 완성 된 출력을 기본 검색 기준으로 사용한다는 아이디어가 있습니다.

이중 연결 목록을 위해 한 단어에 두 개의 포인터를 저장하면 C로 매우 나쁜 일을 할 수 있다는 교훈을 얻었습니다 (보수적 인 GC에는 많은 문제가 있음).

가장 자랑스러운 솔루션은 DisplayTag 패키지와 매우 유사한 것을 작성하는 것이 었습니다.코드 디자인, 유지 관리 및 재사용에 대해 많은 것을 배웠습니다.DisplayTag 이전에 잘 썼고 NDA 계약에 빠졌기 때문에 오픈 소스를 만들 수 없었지만 여전히 면접에서 그 부분에 대해 분주하게 말할 수 있습니다.

Map/Reduce. Two simple concepts that fit together to make a load of data-processing tasks easier to parallelize.

Oh... and it's only the basis of massively-parallel indexing:

http://labs.google.com/papers/mapreduce.html

Not my favorite, but the Miller Rabin Algorithm for testing primality showed me that being right almost all the time, is good enough almost all the time. (i.e. Don't mistrust a probabilistic algorithm just because it has a probability of being wrong.)

@Krishna Kumar

The bitwise solution is even more fun than the recursive solution.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow