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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
[펌글] 대기업 인사팀 18年차의 조언
대기업 인사팀 18年차의 조언 전 대기업에서 인사업무만 18年 가까이 하고 퇴직하고 지금은 자영업하고 있습니다. 사실 제가 하는게 아니라 와이프 미용실 셔터맨인 셈이지요 오늘은 한가한 시간을 이용해서 진심으로 여러분께 조언드리고자 합니다. 인사담당... -
노무현 대통령에게 배우는 글쓰기의 정수
강원국 메디치미디어(출판사) 편집주간이 집필한 '대통령의 글쓰기'라는 책 속에 등장하는 내용을 정리했습니다. 출판인강원국 씨는 서울대 외교학과를 졸업하고 대우증권 홍보실에 입사했습니다. 기업 20년 사사 정리 작업을 하다 글쟁이로 이름을 날렸고 당... -
아끼던 Mavic Air 바다에 빠진 날 ㅠㅠ
Newport Beach 근처에 전기 보트를 빌려주는 곳이 있다. 그 보트를 타고 직접 운전하면서 인근 지역을 구경하러 다닐 수 있다. 지도에서 보는 것 처럼 리도, 발보아 섬은 이미 경치가 좋기로 유명하고, 주변 집들의 개인 해변과 보트가 정박해 있는 모습은 그... -
법륜 스님의 명언 모음
넘어졌을 때 일으켜달라고 아우성치는 것은 어린아이들이나 하는 짓입니다. 용서해 준다는 말은 내가 옳다는 말입니다. 본래 옳고 그름이 없으므로 용서할 게 없습니다. 간절한 마음이 없다는 건 큰 고통이 없다는 말입니다. 그러니 지금 내 상태가 행복한 줄... -
세월호와 하인리히 법칙
세월호와 하인리히 법칙 노응근의 '여적' 대형 사고가 발생하기 전에는 크고 작은 조짐이 나타나기 마련이다. 이런 현상을 설명하는 이론이 ‘1 대 29대 300 법칙’, 또는 ‘하인리히 법칙’이다. 대형 사고가 한 건 터지기 전 경미한 사고가 29회 발생하고, 이런 ... -
코이의 법칙, 당신은 어떤 꿈을 꾸고 있습니까?
코이(Koi)의 법칙 관상어 중에 '코이(Koi)'라는 잉어가 있습니다. 이 코이(Koi)는 작은 어항에 넣어두면 5~8cm 밖에 자라지 않지만, 커다란 수족관이나 연못에 넣어두면 15~25cm까지 자랍니다. 그리고 강물에 방류하면 90~120cm 까지 성장합니다. 같은 물고기... -
엔지니어(개발자)와 일하는 방법
엔지니어(개발자)와 일하는 방법 by Julie Zhuo (페이스북 디자인 디렉터 / Product design director @ Facebook. ) 원문 url 링크 : https://medium.com/the-year-of-the-looking-glass/a3163ff1eced (앞 문장은 똑같아서 생략) 엔지니어(이하 개발자)는 팀의... -
'일'처럼 느껴지지 않는다는 것.
유명해져라 그러면 니가 똥을 싸도 사람들이 박수를 쳐줄것이다. [출처] https://www.facebook.com/Saramvirus -
대학가라고 차마 말하지 못하는 이유
대학 가라고 차마 말하지 못하는 이유 지금 대학은 어떤 곳인가. 문화 권력이 될 수 있는 대학은 극소수이고, 기회비용 문제가 대학의 목줄을 죄고 있다. 대학은 공동화되었다. 얼마 전 한 지방의 강연에서 만난 아버지는 아들에 대한 걱정이 태산이었다. 중학... -
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
컴퓨터 진화를 이끈 위대한 알고리즘(Algorithms)에는 어떤 게 있을까. IT 기술은 놀라운 진화 속도를 보여 왔다. 이를 뒷받침하는 요소 가운데 하나는 알고리즘이라고 불리는 처리 방법이다. 알고리즘은 컴퓨터 진화에 지대한 영향력을 보였다고 해도 과언이 ... -
No Image
창의적인 사람들이 일반인들과 달리 하는 18가지 행동
창의적인 사람들은 일반인들과 생각하는 패턴 자체가 매우 다르다고 하죠. 1) 그들은 꿈을 꾼다 (They daydream) 학창 시절때 수업시간에 공부는 안하고 멍~ 때리면서 딴 생각을 하는 학생들이 있죠. 남들이 봤을땐 그건 매우 시간 아까운 쓸떼없는 일이라고 ... -
엄마학교 서형숙 망언
이런 사람이 엄마 학교?.. 본인이 사람부터 돼야겠그만.. 2014년 05월 22일 일본에서 한국엄마들을 상대로 강연회를 가졌던 엄마학교의 저자 서형숙 육아얘기 잘 하다가 막판에 배가 가라앚는 그 상황에 문자질이나 하는 생각없는 세월호 아이들이라고 비난, ...