FreeTalk
2014.03.20 13:22
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
조회 수 2308 댓글 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 그래픽에서 빛 반사를 빠르게 계산할 수 있게 해준다. 정밀도보다는 속도가 요구되는 장면에서 주로 활용된다. 관련 내용 원문은 이곳 [링크]에서 볼 수 있다.
-
코끼리도 그러는데..
한 연구팀이 재밌는 연구를 했다고 합니다. 코끼리 두 마리가 있는데, 한 마리에게는 맛있는 포도를 주고 다른 한 마리에게는 밍밍한 오이를 주었습니다. 그러자 오이를 받은 코끼리가 화를 냈다고 합니다. 어쩔 수 없이 포도를 빼앗아버리고 두 코끼리 모두... -
컴퓨터가 없었던 때의 즐거움..
나도 예전엔 저렇게 놀았었는데.. 라고 할만한 사람들은 이제 다 어른이 되고.. 아빠, 엄마가 되서 지금 자라고 있는 아이들에게.. 엄마 아빠 어렸을 땐 말이지.. 라고 말해주면 아이들은 공감대가 없을 것이다. 우리가 자랄 때 우리 부모님의 추억이 먼~ 과... -
컴퓨터가 밥 먹여주냐?
컴퓨터에 빠져있던 시절 아버지는 종종 말씀하셨다. "컴퓨터가 밥 먹여주냐?" 그 당시는 속상했던 말이었지만 지금은 내가 힘을 얻는 주문처럼 돼 버렸다. 힘들고 지칠 때나 미래가 두렵고 우울할 때 마다 그 시절 그 때를 생각해 본다. 1990년대 중반, 고등... -
컴퓨터 진화를 이끈 ‘위대한 알고리즘 9’
컴퓨터 진화를 이끈 위대한 알고리즘(Algorithms)에는 어떤 게 있을까. IT 기술은 놀라운 진화 속도를 보여 왔다. 이를 뒷받침하는 요소 가운데 하나는 알고리즘이라고 불리는 처리 방법이다. 알고리즘은 컴퓨터 진화에 지대한 영향력을 보였다고 해도 과언이 ... -
컴퓨터 PC 사용한 시간을 알려주는 프로그램, 컴퓨터를 켜놓고 꺼진 시간량을 파악
얼마나 컴퓨터 사용량이 되는지 함 인터넷 구글링을 해보니 ...요런 프로그램도 있습니다 컴퓨터를 켜고 꺼진시간을 그래프로 알려주는데요 최근 3주일 가량만 그래프로 보여주는 무료 컴퓨터 사용량 프로그램입니다 누가 내 컴을 켜서 얼마 동안 사용했는지 ... -
캠릿브지 대학의 연결구과에 따르면
이러하다. 함 읽어 보시라.. 좀 오래된거.. 옛날 홈페이지에서 퍼옴 ㅋㅋ http://old.hooni.net/theme4/bbs/view.php?pid=3&id=media&no=839 지금까지 읽은 위의 내용을 다시 천천히 보자. 내가 그런 줄 알고 읽었던 단어가 잘못된 게 없는지.. # 관련... -
캐나다인에게: “우리나라 정치도 자랑할 거 많다고!”
캐나다인:우리 총리는 SF소설 광이야. 한국인: 우리 대통령은 독재자의 딸이야. 사실 그건 별 문제가 아닌데, 자꾸 독재자이던 아빠의 시대로 돌아가려고 해서 문제지. 캐나다인: 우리나라 내각의 절반은 여성이고, 절반은 남성이지. 한국인: 캐나다는 5:5 성... - Read More
-
카메라 조리개, 셔터, ISO 설명
명쾌한 조리개, 셔터 속도, ISO 감도에 대한 내용. 자꾸 헷갈렸던 것들이 완전 정리가 됨. 압도적인 감사. -
취약점, 백도어, 스파이웨어 없이 해킹할 수 있는 신개념 해킹기법 등장
대부분의 해킹은 웹/시스템 취약점을 이용하거나 백도어, 스피아웨어를 설치하는 것으로 이루어 집니다. 하지만 이런 전통적인 방법과는 차원이 다른 해킹기법이 한 대학의 연구결과에서 공개됐는데요. 이 방법을 사용하면 네트워크 연결 없이도 원격에서 컴... - Read More
-
출발선은 누구에게나 똑같다고?
선생님은 말씀하셨다. 출발선은 누구에게나 똑같다고.. 그래서 세상은 공평하고 공정하다고..? [관련자료] 멜랑꼴리. 인생계주 https://hooni.net/80338 특권에 대한 짧은 이야기 https://hooni.net/66270 현대판 개미와 베짱이 모음 https://hooni.net/100143...