[영상리뷰] 우아한테크_제이 : 시간복잡도

https://www.youtube.com/watch?v=IEH3YA2Nn4Q 

영상의 리뷰라고 하기 보다는 영상에서 다룬 제이님의 발표 내용을 한 번 정리하며 곱씹어보았다는 표현이 더 적절할 것 같다. 해당 영상에 나오는 단어 중 본인이 핵심 키워드라고 정리한 것은 아래와 같이 총 다섯개로 추릴 수 있다. 키워드 별로 아래에 설명을 달아 풀어서 정리해보도록 하였다.

 

1. 알고리즘

 : 문제를 해결하기 위한 방법

 

1) 건너뛰기 혹은 살펴보기 전략을 통한 문제 해결 성공도

선택지(n)가 100에서 무한대로 갈수록 살펴보기 수가 37에 수렴 되고, 성공확률은 37%로 가장 합리적이라는 통계 결과가 있다. 즉, 10개의 선택지 중 처음의 3개는 무조건 제외, 4번째부터 앞의 기준이 되는 3개보다 더 좋은 선택지를 pick하게 되면 만족도가 가장 높을 수 있다는 의미이다. 이러한 내용은 자취방 구하기, 맛집 찾기, 옷 쇼핑 등등 여러가지의 선택 상황에서 적용 될 수 있다.

 

2. 시간복잡도

 : 문제를 해결하는데 걸리는 시간과 입력의 함수관계

일반 계산식에서 계산방법은 핵심이 되는 연산을 찾는 것이다.

알고리즘 평가를 통해 시간복잡도를 나타낼때는 최선의 경우, 최악의 경우, 평균적인 경우 중 보통 최악의 경우로 표시한다. 이외의 경우는 여러가지의 사례들 대비해서 비교를 하기에 적합한 결과가 아니기 때문이다. 

 

3. 현실적 알고리즘(Polynomial complexity)

 : 다항시간 안에 풀리는 알고리즘. 즉, 상식선에서 풀 수 있는 문제

예시로는 sorting, dp, 정렬 등을 들 수 있다.

 

4. 비현실적 알고리즘(Nondeterministic Polynomial complexity)

 : 복잡도가 팩토리얼 혹은 지수 형태로 올라가는 알고리즘. 즉, 상식선에서 풀 수 없는 문제

예시로는 해밀턴 경로문제를 들 수 있다.

 

5. p와 np의 관계성

 '비현실적 알고리즘을 다항시간안에 풀 수 있을까?' 라는 문장은 P = NP?와 같은 식으로도 표현하여 나타낼 수 있다. 정답은 아직 정의되지 않았으며 이를 증명하는 사람에게는 튜링상이 수여된다.

 

확실한 NP의 예시로 들자면 소인수분해가 있다. 3X7=21은 해결이 쉽지만 21=3X7의 해결은 쉽지 않다. 이런 소인수분해의 어려움(비현실적 시간 복잡도)을 이용하여 공인인증서가 사용되고 있다.

p X q = n이라고 했을때 공개키로 n을 설정, 만약 n이 2857928347598273614896329587195872094865109832947981723948701와 같은 터무니없는 숫자일때 p와 q를 찾는 것은 굉장히 어렵다. 그렇기 때문에 p와 q를 이용하여 비밀키를 설정한다. 이런 예시를 통해 P != NP이지 않을까 하는 추측을 하고 있다