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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
애플, 아이폰 성능 제한 관련해 소송 잇달아..
지난 주 애플은 아이폰 성능 유지와 배터리 보호를 위해 아이폰6, 아이폰6s, 아이폰 SE, 아이폰 7 등 일부 모델에 성능 제한 소프트웨어 업데이트를 적용했다고 성명을 발표했다. 이것에 대해 애플이 신형 아이폰으로 구입을 유도하기 위해 고의적으로 구형 ... -
애플, 일부 아이폰 성능 제한 인정. 성능 유지와 안전 때문..
‘애플이 신형 아이폰 구입을 유도하기 위해 구형 아이폰의 성능을 느리게 만들었다.’ 애플이 구형 아이폰을 일부러 느리게 만든다는 의혹은 이달 초 온라인 커뮤니티 레딧의 한 사용자가 먼저 제기했다. 사용하던 구형 아이폰의 배터리를 교체한 후 벤치마크 ... -
애플워치·애플페이, 역시 '물건'인가
베일 벗은 '잡스 이후' 애플의 전략… 삼성은 2007년 아이폰 충격에서 교훈 얻었나 애플은 9월 9일(현지시간) 미국 캘리포니아 쿠퍼티노 플린트 센터에서 열린 키노트 행사에서 아이폰6와 아이폰6플러스, 그리고 애플페이, 애플워치를 발표했다. '부자가 망해도... - Read More
-
야단친 뒤 30분 법칙
맘&앙팡 - 2015년 03월 야단친 뒤 30분 법칙 24~36 months 아이를 혼내는 것보다 야단치고 나서 엄마의 대처가 중요하다. 30분 이내 스마트하게 대처하는 법. # 왜 30분 이내의 대처가 중요할까? "정서조절 능력과 관련 있는 뇌신경은 적절한 각성상태에 ... -
No Image
약속 시간에 늦는 사람하고는 동업하지 말거라. 좋은글
1.아들아 약속시간에 늦는 사람하고는 동업하지 말거라. 시간 약속을 지키지 않는 사람은 약속을 지키지 않는다. 2.아들아 어려서부터 오빠라고 부르는 여자 아이들을 많이 만들어 놓거라, 그중에 하나, 둘은 말도 붙이기 어려울 만큼 예쁜 아가씨로 자랄 것이... -
얀테의 법칙
얀테의 법칙은 북유럽사람이 삶을 살아가는 사회규범, 관습이자 불문율 같은 삶의 철학이다. 덴마크계 노르웨이 작가인 악셀 산데모세가 1933년에 쓴 소설 '도망자'에 등장하는 가상마을 '얀테'를 소개하면서 지어진 법칙이다. 악셀 산데모세는 10가지 규칙을... -
어느 개발자의 개발자 뽑기
[펌] 어느 개발자의 개발자 뽑기다음은 제가 10여년 동안 게임 개발자로 있으면서 게임 개발자를 뽑으면서 생겼던 일들을 정리해 봅니다. 만약 이글을 읽는 분이 회사에 들어간다거나 팀장급이라 직원을 뽑고자 할때 어느정도 참고를 하셨으면 좋겠습니다. 내... -
어느 교수의 강의 시작 전 이야기
어느 교수의 강의 시작 전 이야기 행복은 금요일 아침 같은 것.. 완전 공감.. #원문 <교수님이 말해주신 행복의 정의와 공부를 하면서 행복할 수 있는 이유..> 여러분 금요일이 좋아요, 일요일이 좋아요? 이것만 얘기해 보세요. (금요일이요) 학교가는데? 금요... -
어느 날 저녁, 나는 그 날을 잊을 수 없다.
모두가 힘든 하루를 보냈고 특히 아빠도 녹초가 되어 퇴근하셨다. 저녁식사로 따뜻한 스튜와 직접 만든 토스트, 그 위에 발라먹는 허브버터가 있었다. 하지만 내 눈에는 빵조각이 아니라 새까만 석탄조각처럼 보였다. 빵이 토스터 기계에서 완전히 타버린 것이... -
어느 발명가의 아내..
두 분 다 멋지네~ 완전 조강지처구만 ㅋㅋ 마지막 말에 아저씨 눈물 빵~ 터지실 듯.. -
어느 아버지의 재산 상속 - 실화
어느 아버지의 상속 재산 (실화) S시에 거주하는 한 아버지가 4남매를 잘키워 모두 대학을 졸업시키고 시집, 장가를 다 보내고.. 한 시름 놓자 그만 중병에 걸린 사실을 알고 하루는 자식과 며느리, 딸과 사위를 모두 불러 모았다. 내가 너희들을 키우고, 대...