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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
2017년을 뜨겁게 달군 미래기술 10가지
2016년 3월 전세계의 이목이 대한민국 서울의 바둑판에 쏠렸다. 구글이 인수한 영국 인공지능 기술 기업 딥마인드의 인공지능(AI) 바둑 프로그램 알파고(Alpha Go)와 세계 최정상급 프로 기사인 이세돌 9단의 빅 매치가 열렸다. 인간과 컴퓨터의 대결은 이미 ... -
30대가 되면 당신에게 일어날 30가지
30대가 되면 당신에게 일어날 30가지 이 글은 허핑턴포스트US 블로거이자 칼럼니스트 웬디 애터버리의 글을 번역, 편집한 것입니다. 9월이 되면 난 만으로 38살이 된다. 누가 몇 살이냐고 물으면 잠깐 생각해야 하는 나이에 도달했다. 37번의 해를 맞이했다는 ... -
나의 영어 실력은..
현지인과 대화할 때마다 내가 처음 컴퓨터를 배울 때가 생각난다. 검은 화면의 MS-DOS 콘솔에서 명령어와 옵션을 입력해서 프로그램을 실행했던 시절이다. 주로 게임을 하는 용도였지만 그 게임을 얻어와서 복사하고 압축을 풀고 하는 과정은 당시 나로써는 어... -
늑대 무리의 행렬
(원본과 편집본 사진 같이 업로드 함) # A wolf pack The first 3 are the old or sick, they give the pace to the entire pack. If it was the other way round, they would be left behind, losing contact with the pack. In case of an ambush they woul... -
이 세상의 모든게 잘못되었다는 것을 느끼게 해줄 29개의 그림들
천개의 문장보다 한장의 그림의 메시지 전달력은 강력합니다. [출처] http://www.pawelkuczynski.com/ -
“아이패드로 전화 받는다?” iOS8 핸드오프 활용하기
아이폰을 쓰는 사람 중에는 아이패드를 비롯해 맥, 아이팟과 같은 애플 제품들을 함께 구입해서 사용하는 경우가 많은데요. 이들 제품간의 연계가 매우 강력하기 때문입니다. iOS8에서는 이러한 기기간 연계가 새롭게 추가된 ‘핸드 오프(Hand off)’ 기능을 통... -
직원을 기계처럼 다뤄야 하는 이유
어느 일본 사람이 쓴 글인데 공감이 돼서 퍼옴 처음엔 이 사람 뭐지? 했는데 반전이 있었어 ㅋㅋ;; # 번역 인간은 의외로 기계와 비슷하다. 공장집 딸이라 그런지는 몰라도 나는 항상 그렇게 생각해왔다. 흔히 '인간은 기계가 아니야!' 라고 하며 인간을 기계... -
'터키'가 형제국인 이유 ?
'터키'가 형제국인 이유 ? '터키'라는 국가를 말하자면 우리는 이스탄불, 지중해의 나라, 형제의 나라 등 여러 수식어를 떠올리지만, 정작 우리나라와 터키가 "왜 '형제의 나라'라고 불리워지는가.." 그 이유를 알고 있는지요? 그 이유를 아느냐? 물으면, 대... -
더 똑똑해진 IOS8 ‘시리’ 이제는 말로 부른다
애플이 IOS8에서 시리를 좀 더 쉽게 불러 낼 수 있는 기능을 추가했는데요. 홈버튼을 꾹 누르지 않아도 음성으로 시리를 불러낼 수 있는 기능입니다. 그 마법의 주분은 영어로 “Hey, Siri” 이고, 우리 말로는 ‘시리야’ 입니다. 이 기능을 사용하기 위해서는 ... -
내가 안경을 쓰는 이유..
구글 이미지 검색에 안경을 쓴/안쓴 사진을 업로드.. 라섹 수술을 했지만 안경을 쓰고 다녀야 할 이유가 생겼다. - 안경을 안쓰면.. "man, 남자, 인간의 수컷, ..." - 안경을 쓰면.. "gentleman, 젠틀맨, 귀족을 총칭하는 말, ..." # 안경 벗은 사진을 올렸을 ... -
100년전 사람들이 상상했던 "21세기"는 어떤 모습 일까?
100년전 사람들이 상상했던 "21세기"는 어떤 모습? 100년 전에 살았던 사람들은 100년 후인 지금의 세상을 어떻게 상상했을까? 문학예술 전문 온라인 매체인 <퍼블릭 도메인 리뷰>(The Public Domain Review)가 이를 보여주는 그림들을 공개해 화제를 모았다. ... -
가슴 깊이 새겨야 할 달라이 라마의 16가지 인생 명언
달라이 라마는 티베트의 실질적인 지도자이자 정신적 지주가 되는 인물을 뜻합니다. 가장 처음 달라이 라마는 관세음보살이 사람으로 환생했다고 알려져 있습니다. 수백 만의 티베트 승려들은 그에게서 종교적인 길을 찾습니다. 여기에 사랑과 연민을 담아 깨...