읽고 있는 '프로그래밍은 상상이다(임백준, 2008)' 의 책의 5번째 이야기에 나오는 '05_게임의 발견과 알고리즘의 완성'이라는 글을 읽다가 나온 알고리즘에 대해서 궁금증이 생겨 살짝 찾아보았다. 알고리즘이라는 것은 단순히 컴퓨터의 소프트웨어에만 국한된 것은 아니다. 우리의 생활 속에서도 다양한 모습의 알고리즘들을 찾아볼 수 있다. 우리가 매일 지나치는 도로의 신호등, 출퇴근 길에 사용하는 지하철, 전철, 기차 등.
내가 살아가면서 겪게 되는 많은 경험과 사건들 속에서, 그것들을 해결하기 위한 내 나름의 알고리즘들을 세워간다. 나만의 알고리즘이라는 것이 다른 사람이 보기에는 투박하기도 하고, 간단하기도 하고, 복잡하기도 하다. 그건 내가 다른 사람의 알고리즘을 봤을 때도 마찬가지다. '왜 저렇게 할까?'라는 생각을 하며 그 사람의 알고리즘을 분석해보려고 노력하지만, 암호화가 철저히 되어 있는 탓에 그 알고리즘에 대처할 수 없는 경우가 자주 있다. 하지만, 그 사람들의 알고리즘보다 우선하는 것은 내 자신의 알고리즘이다.
인간은 사회적 동물(호모 사피엔스)이지만, 그 중심은 자기 자신이다.
무슨 소리를 하고 있는거냐!! 나는!!!??
알고리즘(algorithm)이란 어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임이다.
알고리즘의 조건
알고리즘은 일반적으로 다음의 조건을 만족해야 한다.
- 입력: 외부에서 제공되는 자료가 0개 이상 존재한다.
- 출력: 적어도 1개 이상의 결과를 내어야 한다.
- 명확성: 각 명령어들은 명확하고 모호하지 않아야 한다.
- 유한성: 알고리즘의 명령어들은 유한번의 수행후에 종료되어야 한다. 이것은 수행 시간의 현실적인 유한성을 의미한다.
- 효과성: 모든 명령어들은 원칙적으로 종이와 연필만으로 수행될 수 있는 기본적인 것이어야 한다.
알고리즘의 연구 분야
- 고안: 완벽한 자동화를 통한 알고리즘의 개발은 거의 불가능하다. 따라서 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리즘을 개발하는데 그 의미가 있다.
- 검증: 고안된 알고리즘이 합당한 입력값에 대하여 올바른 결과를 계산해 내는지를 밝히는 절차가 필요하다. 알고리즘 검증은 고안된 알고리즘이 프로그래밍 언어와는 독립적으로 올바르게 작동할 수 있음을 보여주는데 그 목적이 있다.
- 분석: 고안된 알고리즘을 실행하기 위해 필요한 실행시간과 필요로 하는 기억장치를 결정하는 것이다.
- 테스트: 디버깅, 성능분석
알고리즘의 분석 기준
- 정확성: 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
- 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
- 기억 장소 사용량
- 단순성
- 최적성: 그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다.
평균과 최악의 경우 분석
- O(1): 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
- O(log N): 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형
- O(N): 입력 자료에 따라 선형적으로 실행 시간이 걸리는 경우
- O(N log N): 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타남.
- O(N2): 이중 루프 내에서 입력 자료를 처리하는 경우에 나타남.그러나 N의 크기가 작을 때에는 N2이 NlogN보다 작을 수 있음.
- O(N3): 삼중 루프.
- O(2n): 가끔씩 알고리즘을 처음 개발할 때 나타날 수 있는 수행시간..
'허니몬의 IT 이야기' 카테고리의 다른 글
| 노트북에 설치한 ubuntu 에서 한글키 사용하기 (0) | 2008.11.16 |
|---|---|
| Linux Bin 설치방법 (2) | 2008.11.15 |
| 웹페이지 네비게이션 플래시 클릭안됨 (4) | 2008.05.06 |
| USB 이동형 저장치를 통해 전파되는 악성코드 (0) | 2008.04.23 |
| [본문스크랩] IPv6 (1) | 2008.02.05 |
