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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
컴퓨터 진화를 이끈 위대한 알고리즘(Algorithms)에는 어떤 게 있을까. IT 기술은 놀라운 진화 속도를 보여 왔다. 이를 뒷받침하는 요소 가운데 하나는 알고리즘이라고 불리는 처리 방법이다. 알고리즘은 컴퓨터 진화에 지대한 영향력을 보였다고 해도 과언이 ... -
No Image
창의적인 사람들이 일반인들과 달리 하는 18가지 행동
창의적인 사람들은 일반인들과 생각하는 패턴 자체가 매우 다르다고 하죠. 1) 그들은 꿈을 꾼다 (They daydream) 학창 시절때 수업시간에 공부는 안하고 멍~ 때리면서 딴 생각을 하는 학생들이 있죠. 남들이 봤을땐 그건 매우 시간 아까운 쓸떼없는 일이라고 ... -
자신의 일을 중국 개발자에게 아웃소싱한 개발자(미국)
자신의 일을 중국 개발자에게 아웃소싱한 미국의 개발자 요약된 기사는 여기[링크]서 볼 수 있고 원 기사는 여기[링크] 1월 14일에 나온 내용이다. 이 사건은 이러하다. 미국에 있는 한 회사의 IT 관리자가 VPN 접속 로그를 살펴보고 있는데, 이상하게 중국 선... -
사기꾼 특징 (관상, 말투, 하는 말)
1. 말이 많다. 경청을 하지 않고 자기 말만 계속해서 세뇌가 되게 만든다. 2. 처음에는 자기 사비를 털어 밥도 사주고 이것저것 인간적으로 잘해준다. 3. 뭐든지 다 잘아는 척, 인맥이 넓은 척, 말만 들어보면 모르는 것이 없고 모르는 사람이 없다. 4. 옷을 ... -
아프리카 기니 사람들이 밤에 공항을 가는 이유
아프리카 기니 사람들이 밤에 공항을 가는 이유.. -
‘교육적’이라는 단어가 가장 겁난다.
‘교육적’이라는 단어가 가장 겁난다. 한국의 교육은 철저하게 ‘교육을 위한 교육’이다. 자식을 해병대 캠프에 보낼 때처럼 ‘교육적’이라는 말만 붙이면 정당화된다. 지난번 한 지방에 강연을 갔을 때다. 기차역으로 마중을 나온 학부모와 ‘체험 학습’과 관련된... -
뇌운동.. 좌뇌? 우뇌? 어느쪽을 사용하십니까?
여인이 어느 방향으로 돌고 있습니까 ? 위 애니메이션은 자신이 평소에 오른쪽 뇌를 주로 쓰는 사람인지, 아니면 왼쪽 뇌를 많이 쓰는 사람인지 판별해주는 기능을 한다. 여인이 시계 반대 방향으로 돌고 있는 모습이 보이는 사람은 평소에 왼쪽 뇌를 사용하는... -
왜 프로그래머는 계속 공부하는데도 모자른걸까?
프로그래머가 아무리 공부를 해도 쏟아지는 지식을 다 알순 없습니다. 그렇다면 무엇을 배울지 선택을 해야 합니다. 그런데 학계보다는 업계가 분야를 주도하다보니, (학계는 좀 수비적이죠) 공격적인 개발이 이뤄지고 있고 그 아래에 개발자들은 넘쳐나는 정... -
엔지니어(개발자)와 일하는 방법
엔지니어(개발자)와 일하는 방법 by Julie Zhuo (페이스북 디자인 디렉터 / Product design director @ Facebook. ) 원문 url 링크 : https://medium.com/the-year-of-the-looking-glass/a3163ff1eced (앞 문장은 똑같아서 생략) 엔지니어(이하 개발자)는 팀의... -
라인 레인저스(LINE Rangers)를 그만 두게 된 이유
라인 레인저스(LINE Rangers) [기사] http://www.hankyung.com/news/app/newsview.php?aid=201403037509v 게임 스토리는 샐리가 외계인에게 납치되어 구해내는 것이다. 샐리를 구할 생각에 한참을 재밌게 하다가 어느 순간.. 과연.. 정말 샐리가 납치됐을까? ... -
위기상황에서의 리더의 중요성
“처음부터 끝까지 다 잘못된듯한” 세월호의 참극을 보면서 나는 5년여전인 2009년 1월15일 뉴욕 허드슨강에 불시착한 US Airways 1549편을 떠올렸다. 라과디아공항에서 비행기가 이륙한뒤 새가 엔진에 충돌해 양쪽 엔진이 다 멈추고 설렌버거 기장이 허드슨강... -
'고객은 항상 옳다'라는 말이 옳지 않은 5가지 이유
허핑턴포스트US의 블로거인 '알렉산더 셰룰프(Alexander Kjerulf)'는 (IBM, 레고, 힐튼, HP, 이케아등을 상대로)직장환경과 리더쉽에 대해 강의하는 유명강사다. 그가 최근 '고객이 항상 옳다'라는 말이 옳지 않은 5가지 이유에 대해 정리했다. 이야기는 사우...