FreeTalk
2014.03.20 13:22
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
조회 수 2322 댓글 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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
위기상황에서의 리더의 중요성
“처음부터 끝까지 다 잘못된듯한” 세월호의 참극을 보면서 나는 5년여전인 2009년 1월15일 뉴욕 허드슨강에 불시착한 US Airways 1549편을 떠올렸다. 라과디아공항에서 비행기가 이륙한뒤 새가 엔진에 충돌해 양쪽 엔진이 다 멈추고 설렌버거 기장이 허드슨강... -
한글이 우수한 10가지 이유
1. 한글 사용 인구수는 세계 12위 한국어를 모국어로 삼아 쓰는 이의 수는 표준중국어, 에스파냐어, 벵갈어, 영어, 힌디어, 포르투갈어, 러시아어, 일본어, 중국어, 자바어 다음 프랑스어 앞 12위에 해당한다. 2. 한글은 세계에서 가장 많은 발음을 표기할 수... -
엑셀도 모르는 KBS의 선거 그래프를 바로잡아 보자
KBS에서 마지막 여론조사 결과를 발표했다. 그런데 그래프가 이상했다. 아래 새정치민주연합의 박원순 후보가 앞서는 그래프는 13.8%의 차이를 보이고 있다. 오차 범위를 훌쩍 뛰어넘는다. 하지만 그래프 높이의 차이는 매우 적다. (지금은 그래프를 잠시 삭... -
기회의 신 카이로스(Kairos)
기회의 신 카이로스의 뒷머리가 대머리인 이유 "기회의 신 카이로스(Kairos)" 그리스 신화에 나오는 제우스의 아들 카이로스의 모습은 무척이나 독특하다. 앞머리는 숱이 무성한 대신 뒷머리는 대머리이며, 어깨와 양발 뒤꿈치에는 날개가 달려있을 뿐만 아니... -
[펌글] 대기업 인사팀 18年차의 조언
대기업 인사팀 18年차의 조언 전 대기업에서 인사업무만 18年 가까이 하고 퇴직하고 지금은 자영업하고 있습니다. 사실 제가 하는게 아니라 와이프 미용실 셔터맨인 셈이지요 오늘은 한가한 시간을 이용해서 진심으로 여러분께 조언드리고자 합니다. 인사담당... -
노무현 대통령에게 배우는 글쓰기의 정수
강원국 메디치미디어(출판사) 편집주간이 집필한 '대통령의 글쓰기'라는 책 속에 등장하는 내용을 정리했습니다. 출판인강원국 씨는 서울대 외교학과를 졸업하고 대우증권 홍보실에 입사했습니다. 기업 20년 사사 정리 작업을 하다 글쟁이로 이름을 날렸고 당... -
아끼던 Mavic Air 바다에 빠진 날 ㅠㅠ
Newport Beach 근처에 전기 보트를 빌려주는 곳이 있다. 그 보트를 타고 직접 운전하면서 인근 지역을 구경하러 다닐 수 있다. 지도에서 보는 것 처럼 리도, 발보아 섬은 이미 경치가 좋기로 유명하고, 주변 집들의 개인 해변과 보트가 정박해 있는 모습은 그... -
법륜 스님의 명언 모음
넘어졌을 때 일으켜달라고 아우성치는 것은 어린아이들이나 하는 짓입니다. 용서해 준다는 말은 내가 옳다는 말입니다. 본래 옳고 그름이 없으므로 용서할 게 없습니다. 간절한 마음이 없다는 건 큰 고통이 없다는 말입니다. 그러니 지금 내 상태가 행복한 줄... -
세월호와 하인리히 법칙
세월호와 하인리히 법칙 노응근의 '여적' 대형 사고가 발생하기 전에는 크고 작은 조짐이 나타나기 마련이다. 이런 현상을 설명하는 이론이 ‘1 대 29대 300 법칙’, 또는 ‘하인리히 법칙’이다. 대형 사고가 한 건 터지기 전 경미한 사고가 29회 발생하고, 이런 ... -
코이의 법칙, 당신은 어떤 꿈을 꾸고 있습니까?
코이(Koi)의 법칙 관상어 중에 '코이(Koi)'라는 잉어가 있습니다. 이 코이(Koi)는 작은 어항에 넣어두면 5~8cm 밖에 자라지 않지만, 커다란 수족관이나 연못에 넣어두면 15~25cm까지 자랍니다. 그리고 강물에 방류하면 90~120cm 까지 성장합니다. 같은 물고기... -
플랩버디! 재미난 게임 한 번 해보세요~
한번 해보세요~ ㅎㅎ https://itunes.apple.com/app/id867666983?mt=8 플랩버디! 언제나 쉽고 간편하게 즐길 수 있는 게임. 귀여운 캐릭터들을 선택할 수 있어 더욱 재미가 있는 플랩버디! FlapBuddy! The game is easy to enjoy any time. You can choose cut... -
엔지니어(개발자)와 일하는 방법
엔지니어(개발자)와 일하는 방법 by Julie Zhuo (페이스북 디자인 디렉터 / Product design director @ Facebook. ) 원문 url 링크 : https://medium.com/the-year-of-the-looking-glass/a3163ff1eced (앞 문장은 똑같아서 생략) 엔지니어(이하 개발자)는 팀의...