자릿수가 N개인 숫자로 이루어진 비밀번호를 어떻게 찾을까? 비밀번호가 아니다 틀리다만 알 수 있기 때문에 시스템 결함이 있지 않는 이상 10^N번 다 해봐야한다. 만약 영문자 조합이라면? 특수문자도 있다면? 심지어 어떤 조합인지도 모르고 자릿수도 모른다면? 그 복잡도는 어마어마할 것이다.
소인수분해를 할 때도 마찬가지이다.
100을 소인수 분해 한다면 2로 나눠보고 3으로 나눠보고 ... 해서 100 = 2*2*5*5 라는 것을 찾는다. 하지만 숫자가 28,392,749,719,070,274,017,094,729,749,071,974,729,477,294 같이 무지막지하다면 엄청난 시간이 걸린다. '그러면 더 쉬운 방법으로 하면 되지'라고 생각이 들지만 현재까지 일반적으로 N자리가 주어졌을때 10^N 보다 더 빨리 찾는 방법은 없다고 한다.
'Computer Science > 컴퓨터 과학이 여는 세계' 카테고리의 다른 글
| 컴퓨터과학이 여는 세계_9.1 튜링증명 리뷰, 시간복잡도의 개념_이광근 (0) | 2017.05.13 |
|---|---|
| 컴퓨터과학이 여는 세계_8.3 알고리즘의 예와 복잡도_이광근 (1) | 2017.05.08 |
| 컴퓨터과학이 여는 세계_8.2 알고리즘과 언어_이광근 (1) | 2017.05.07 |
| 컴퓨터과학이 여는 세계_8.1 소프트웨어를 잘 짜기위한 두개의 축_이광근 (0) | 2017.05.06 |
| 컴퓨터과학이 여는 세계_7.3 여러가지 재료로 컴퓨터 만들기_이광근 (0) | 2017.05.05 |
