FreeTalk
2014.03.20 13:22
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
조회 수 2323 댓글 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가지 이유
허핑턴포스트US의 블로거인 '알렉산더 셰룰프(Alexander Kjerulf)'는 (IBM, 레고, 힐튼, HP, 이케아등을 상대로)직장환경과 리더쉽에 대해 강의하는 유명강사다. 그가 최근 '고객이 항상 옳다'라는 말이 옳지 않은 5가지 이유에 대해 정리했다. 이야기는 사우... -
세월호 추돌, 한국 잠수함 가능성 높아
인터뷰어: 굳모닝런던 편집부 인터뷰이: 굳모닝런던 박필립 발행인 세월호 침몰 사고에 따른 대규모 희생자 발생으로 한국이 요동치고 있다. 지난 인터뷰에서 잠수함 추돌이라는 내용이 나가자 그 파장이 엄청났다. 지금은 어떻게 보고 있는가. 우선 세월호 침... -
2017년을 보내며..
미국 생활이 벌써 6개월이 지나간다. 지난 몇 개월 동안 정착하느라 몸도 마음도 바빴나 보다. 그 때는 느끼지 못하고 흘려 보냈던 감정들이 요즘에서야 조금씩 되새겨진다. 돌이켜보니 "무식한게 용감하다"는 말이 맞나보다. 낯선 곳에 와서 뭘 모르는지도 ... -
한국군과 미군의 차이
비단 군대의 차이가 아니라, 전반적인 한국과 미국 사회의 차이가 아닐까 싶다. 한국의 계급에 대한 "특권"을 우선시 하는 잘못된 인식과, 선진국의 계급에 대한 "권한"과 책임"을 우선시 하는 올바른 인식.. [출처] http://www.podbbang.com/ziksir/view/593 ... -
사람들은 누구나 자기가 살아온 인생에 따라 생각하고 얘기하고 조언한다.
사람들은 모두 자기 인생 속에서 살아간다. 사람들은 누구나 자기가 살아온 인생에 따라 생각하고 얘기하고 조언한다. 적어도 자신의 인생 경험이나 생각을 다른 사람에게 강요하는 어리석은 사람이 되지 말아야겠다. [출처] https://www.facebook.com/dydqkad... -
엄마학교 서형숙 망언
이런 사람이 엄마 학교?.. 본인이 사람부터 돼야겠그만.. 2014년 05월 22일 일본에서 한국엄마들을 상대로 강연회를 가졌던 엄마학교의 저자 서형숙 육아얘기 잘 하다가 막판에 배가 가라앚는 그 상황에 문자질이나 하는 생각없는 세월호 아이들이라고 비난, ... -
No Image
창의적인 사람들이 일반인들과 달리 하는 18가지 행동
창의적인 사람들은 일반인들과 생각하는 패턴 자체가 매우 다르다고 하죠. 1) 그들은 꿈을 꾼다 (They daydream) 학창 시절때 수업시간에 공부는 안하고 멍~ 때리면서 딴 생각을 하는 학생들이 있죠. 남들이 봤을땐 그건 매우 시간 아까운 쓸떼없는 일이라고 ... -
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
컴퓨터 진화를 이끈 위대한 알고리즘(Algorithms)에는 어떤 게 있을까. IT 기술은 놀라운 진화 속도를 보여 왔다. 이를 뒷받침하는 요소 가운데 하나는 알고리즘이라고 불리는 처리 방법이다. 알고리즘은 컴퓨터 진화에 지대한 영향력을 보였다고 해도 과언이 ... -
대학가라고 차마 말하지 못하는 이유
대학 가라고 차마 말하지 못하는 이유 지금 대학은 어떤 곳인가. 문화 권력이 될 수 있는 대학은 극소수이고, 기회비용 문제가 대학의 목줄을 죄고 있다. 대학은 공동화되었다. 얼마 전 한 지방의 강연에서 만난 아버지는 아들에 대한 걱정이 태산이었다. 중학... -
'일'처럼 느껴지지 않는다는 것.
유명해져라 그러면 니가 똥을 싸도 사람들이 박수를 쳐줄것이다. [출처] https://www.facebook.com/Saramvirus -
엔지니어(개발자)와 일하는 방법
엔지니어(개발자)와 일하는 방법 by Julie Zhuo (페이스북 디자인 디렉터 / Product design director @ Facebook. ) 원문 url 링크 : https://medium.com/the-year-of-the-looking-glass/a3163ff1eced (앞 문장은 똑같아서 생략) 엔지니어(이하 개발자)는 팀의... -
코이의 법칙, 당신은 어떤 꿈을 꾸고 있습니까?
코이(Koi)의 법칙 관상어 중에 '코이(Koi)'라는 잉어가 있습니다. 이 코이(Koi)는 작은 어항에 넣어두면 5~8cm 밖에 자라지 않지만, 커다란 수족관이나 연못에 넣어두면 15~25cm까지 자랍니다. 그리고 강물에 방류하면 90~120cm 까지 성장합니다. 같은 물고기...