FreeTalk
2014.03.20 13:22
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
조회 수 2325 댓글 0
첨부 '8' |
|
---|
컴퓨터 진화를 이끈 위대한 알고리즘(Algorithms)에는 어떤 게 있을까. IT 기술은 놀라운 진화 속도를 보여 왔다. 이를 뒷받침하는 요소 가운데 하나는 알고리즘이라고 불리는 처리 방법이다. 알고리즘은 컴퓨터 진화에 지대한 영향력을 보였다고 해도 과언이 아니다. 이런 위대한 알고리즘에는 어떤 게 있을까.
![quake3_140313_1.jpg](https://www.hooni.net/xe/files/attach/images/2909/934/037/5468b700bcd319e1d6d2e10ad2e3bd69.jpg)
먼저 허프만 코딩(Huffman Coding). 허프만 코딩은 지난 1951년 데이비드 허프만(David Huffman)이 개발한 알고리즘이다. 빈출빈도에 따라서 자주 이용하는 문자에 대해선 적은 수 비트를 쓰는 걸 말한다. 반대로 빈도수가 적으면 긴 부호를 부여한다.
모든 문자가 같은 빈도로 전송되지 않는다는 점을 이용한 것으로 빈도수에 따라서 길이가 가변인 코드를 만들기 때문에 고정 길이를 쓸 때보다 데이터양을 줄이는 압축 효과를 준다. 허프만 코딩은 JPEG나 MP3 같은 압축 기술에 활용되고 있다.
![Huffman_Coding.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/b0de0d7d02d91a1cda5cfbe51c54940a.gif)
다음은 공개키 암호화 방식(Public-key Cryptography). 암호화는 통신 기밀성을 높이지만 해독을 위한 키 전달 과정에서 도청될 위험이 있다. 이를 해결한 것이 공개키 암호화 방식이다. 개인키 뿐 아니라 공개키 2가지 암호화키를 제공해 도청 위험을 해소한 것이다.
다익스트라 알고리즘(Dijkstra’s Algorithm)은 지난 1956년 에드거 W 다익스트라가 고안한 것으로 최단 경로를 탐색하는 알고리즘이다. 통신간 최단 경로를 결정하기 위해 경로 길이를 계산하는 것으로 이 알고리즘의 가장 큰 장점은 불필요한 경로를 생략할 수 있게 해줬다는 것이다. 다익스트라 알고리즘은 자동차 내비게이션 같은 기기에서 경로 탐색 등에 활용되고 있다.
![Dijkstra_Algorithm.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/a5227ec3a7f421c89876d9107d0d7c97.gif)
이진 검색 알고리즘(Binary Search Algorithm)은 정렬되어 있는 목록을 2개로 분할하면서 탐색해 탐색 범위를 짜 넣으면서 효율적으로 목표에 도달할 수 있게 해주는 알고리즘이다. 전화번호부 검색 기술 등에 응용되고 있다.
![Binary_Search_Algorithm.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/e68aa25f91d4eb67dfea63b41298a2bb.gif)
빠른 정렬(Quicksort)은 지난 1960년 토니 호어(Tony Hoare)가 발명한 알고리즘. 유닉스(UNIX)의 디폴트 정렬 기능으로 채택되면서 일약 유명세를 타게 되기도 했다. 주어진 파일에서 특정키 값보다 작은 값을 갖는 레코드와 큰 값을 가진 레코드를 분리해서 파일 1개를 논리적으로 부파일 2개로 재배열한다. 이런 부파일에 순환해서 같은 빠른 정렬을 적용해 파일을 정렬하는 방식을 말한다.
빠른 정렬의 가장 큰 장점은 데이터 비교와 교환 횟수가 적은 알고리즘이라는 것이다. 덕분에 임의로 흩어져 있는 데이터를 효율적으로 정렬할 수 있는 가장 빠른 정렬 알고리즘으로 평가받고 있다.
![Quick_Sort.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/05808a869784dc78a4b985f7122f1329.gif)
다음은 카라슈바 알고리즘(Karatsuba Algorithm). 큰 수를 곱셈할 때 가감 횟수를 늘려서 곱셈 횟수를 줄이는 것이다. 쉽게 말하자면 두 자릿수 곱셈을 한다면 일반 방식을 이용한다면 핫 자릿수 곱셈을 4번 해야 한다. 하지만 카라슈바 알고리즘은 한 자릿수 곱셈은 3번 하고 나머지는 덧셈과 뺄셈으로 결과를 구하는 것이다.
이런 방식을 쓰는 이유는 곱셈보다 가감 쪽이 계산 처리속도가 훨씬 빠르기 때문. 결국 계산 속도를 고속화할 수 있다는 게 이 알고리즘으로 얻을 수 있는 장점인 것이다.
![Karatsuba_Algorithm.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/4b55f2ea118ac1a972bc43c5ace28bc7.gif)
다음은 유클리드 호제법(Euclidean Algorithm)이다. 유클리드는 기전 전 330년 그리스의 고대 수학자다. 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 자연수의 최대공약수를 간단하고 재빠르게 찾아낼 수 있는 이 알고리즘은 공개키 암호화가 요구하는 계산에 활용되는 등 현대 컴퓨터 기술에서도 여전히 활동 중인 현역 알고리즘이다.
![Euclidean_Algorithm.gif](https://www.hooni.net/xe/files/attach/images/2909/934/037/931900163793683ee30f815e5a35f108.gif)
브레젠험 라인 알고리즘(Bresenham’s Line Algorithm)은 지난 1962년 IBM에 근무하던 잭 앨튼 브레젠험이 개발한 알고리즘이다. 컴퓨터 스크린에서 직선을 그리는 데 사용하며 확장해 원을 그릴 수도 있다. 브레젠험 라인 알고리즘은 실수를 이용하지 않고 정수만으로 선을 그린다. 정수 가감법과 비트 시프트만 이용하는 간단한 방법이었기 때문에 수많은 컴퓨터에서 쓰일 수 있었다. 컴퓨터 그래픽 초기에서 가장 혁명적인 알고리즘으로 꼽힌다. 또 이런 간결함 덕에 요즘 그래픽카드에서도 쓰이고 있다고 한다.
![Bresenham_line_Algorithm.png](https://www.hooni.net/xe/files/attach/images/2909/934/037/4e5315407f0f7b3160774cd9e7f8716b.png)
마지막은 빠른 역 제곱근 알고리즘(Fast Inverse Square Root)이다. 1999년 출시된 FPS 게임인 퀘이크Ⅲ 아레나(QuakeⅢ Arena)에서 채택한 알고리즘이다. 3D 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
번호 | 분류 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|---|
197 | FreeTalk |
아프리카 기니 사람들이 밤에 공항을 가는 이유
![]() |
hooni | 2014.04.07 | 3024 |
196 | FreeTalk |
사기꾼 특징 (관상, 말투, 하는 말)
![]() |
hooni | 2014.03.21 | 4497 |
195 | FreeTalk |
자신의 일을 중국 개발자에게 아웃소싱한 개발자(미국)
![]() |
hooni | 2014.03.21 | 2746 |
194 | FreeTalk | 창의적인 사람들이 일반인들과 달리 하는 18가지 행동 | hooni | 2014.03.20 | 2326 |
» | FreeTalk |
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
![]() |
hooni | 2014.03.20 | 2325 |
192 | FreeTalk |
부모가 된 지 1년
![]() |
hooni | 2014.03.12 | 3240 |
191 | FreeTalk |
[펌글] 대기업 인사팀 18年차의 조언
![]() |
hooni | 2014.03.05 | 2161 |
190 | FreeTalk |
안드로이드폰의 몰랐던 진실.. 이런 위험이
![]() |
hooni | 2014.03.05 | 2675 |
189 | FreeTalk | "세금 더 내기 싫다.." 월세 집주인 꼼수 백태 | hooni | 2014.03.05 | 2825 |
188 | FreeTalk | 지하철이 역에 도착하면 놀랍게 변하는 디지털 스크린 옥외광고 | hooni | 2014.03.04 | 2918 |
187 | FreeTalk |
대학가라고 차마 말하지 못하는 이유
![]() |
hooni | 2014.03.04 | 2306 |
186 | FreeTalk |
부모나래. 아이와 놀아줄 때 어떤 부모입니까?
![]() |
hooni | 2014.02.28 | 3142 |