[10분 테코톡] 제이의 시간복잡도 영상정리

시간복잡도(동영상 시청)
영상 : https://www.youtube.com/watch?v=IEH3YA2Nn4Q

- 알고리즘이란?
      : 문제를 해결하기 위한 방법
    ex ) 
        - 온라인 코딩 테스트로 알고리즘 풀기
        - 아침에 일어나서 코리아IT아카데미로 가는 방법
        - 과제를 빨리 끝내는 방법
        - 점심 메뉴를 고르는 방법
        - 제일 마음에 드는 배우자 찾는 방법
             가상 시나리오 : 배달이가 배우자를 찾으려고 함
                                  평생 세명의 남자를 찾으려고 함(가상 인물)
                                  시유, 제이손, 존이 있는데 우선순위가 있음..
                                  시유 > 제이손 > 존(세명 중에 한명(외도X 양다리X)
                                  시유를 선택하는게 목표
                        배우자를 찾을 때 방법이 필요
                        : 건너뛰기 혹은 살펴보기 전략
                        : 0명 살펴보기 전략!(확률 30%)
                              순번       1번 만남     성공 유무
                                1            시유           성공
                                2           제이손         실패
                                3              존            실패
                        : 1명 살펴보기 전략!(첫번째 사람 선택을 아예 안함!  
                                                    두번째 만난 사람이 첫번째보다 좋으면 바로 선택)(50%)
                              순번       1번 만남   2번만남   3번만남  성공 유무
                                1            시유       제이손        존         실패
                                2           제이손        존        제이손      실패
                                3           제이손       시유         존         성공
                                4           제이손        존         시유        성공 
                                5              존          시유      제이손      성공
                                6              존        제이손      시유        실패       
                        : 인원수가 늘어나면서 성공확률이 수렴되는 확률을 찾으니
                          37%이더라.. 수학적으로 증명된다
                          그만큼 만족도가 높아지더라

             이런 전략을 사용할 수 있는 곳
                   : 자취방 구하기
                   : 맛있어보이는 음식점 찾아다니기
                   : 마음에 드는 옷 고르기

      알고리즘에는 시간복잡도라는 것이 존재
      시간복잡도란?
           : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계(위키)
           : 알고리즘을 푸는데 걸리는 시간
           : 시간복잡도를 계산하는데 있어 중요한 것은 핵심이 되는 연산을 찾는 것
           ex ) n² + 2n -> 0(n²)
                 2n⁴ + 3n -> 0(n⁴)(계수도 무시하고 핵심이 되는 연산)
                   
                 for( int i = 0; i < n; i++){
                     for( int j = 0; j < m; j++){

                     }
                 }                
                 의 복잡도 = n²
             --------------------------------------------
                 for( int i = 0; i < n; i++){
                     for( int j = 0; j < m; j++){
                         for( int k = 0; k < 10000; k++){

                         }
                     }
                 }
                 의 복잡도 = n³이 아님!
                 k에 10000이라는 숫자가 있지만 m과 n이 무한대로 간다면
                 10000은 무시할 수 있는 숫자
                 그렇게에 위와 똑같이 n²
             --------------------------------------------
                 for( int i = 1; i < n; i*2){

                 }
                 의 복잡도 = log0ⁿ
 
      - 알고리즘에서는 최악의 상황을 염두해 두고 평가를 진행
            그 이유는 무엇일까?
            최선의 경우에서도 복잡도를 쓸 수 있지 않을까?
              ex ) 5  4  7  10  1  2 
                     - 5라는 숫자를 찾고 싶음
                     : 앞에서 시작하면 바로 첫번째부터 찾을 수 있음
             : 최선의 경우에서는 어떤 알고리즘을 보여도 모두 만족할 만한
               결과를 내놓기 때문에 비교 불가
             : 그렇기에 최악의 경우를 두고 비교구조로 삼는다.
             : 평균적인 경우도 간혹가다가 비교구조로 놓기도 한다.
                  - 하지만 잘 쓰이지 않는다(평균이 어딘지 모른다)

       - 현실적 알고리즘(Polynomial complexity : P 문제)
            : 다항시간 안에 풀리는 알고리즘
            : 상식선에서 풀 수 있는 문제
                ex ) sorting, dp, 정렬, 큰 수 뽑기

       - 비현실적 알고리즘(Nondeterministic Polynomial complexity : NP 문제)
            : 복잡도가 !(팩토리얼), 지수형태로 올라가는 알고리즘
                ex ) 해밀턴 경로문제, 한 붓 그리기(모든 경로를 한 붓으로 겹치지 않고)
                      4000!처럼 컴퓨터도 계산하기 어려운 것들(오래 걸리는 것들)

       풀 수 없는 지수시간의 알고리즘을 다항시간안에 풀 수 있을까?
         -> 밀레니엄 문제(P와 NP가 같은지 아닌지는 아무도 모름)
             이것을 증명한 사람은 컴퓨터 공학 최고의 영애 튜링상을 받게 된다.
             아무도 푼 적이 없음!!

       P-NP문제

       - 피부에 와닿는 예시
        : 소인수분해 문제
             3 * 7 = 21 -> 3와 7의 곱을 내놓으라고 하면 금방 나옴
             21 = 3 * 7 -> 21이 어떤 소수의 곱인지 내놓으라고 하면 오래 걸림

             큰 숫자면 더 오래 걸릴 것

       NP를 활용하여 일상생활에서 자주 쓰임
       ex ) 전세계의 대부분의 보안이 "공개키", "비밀키"로 이루어져 있음
          : 공인인증서(RSA 알고리즘)
             - RSA알고리즘의 기반은 소인수분해가 어렵다
               (비현실적 시간 복잡도)는 점을 이용
             - 공개키, 비밀키 발행(비밀키는 본인 혼자)
                  : 누군가가 본인에게 메세지를 보내려면 
                    본인이 공개한 공개키로 Encrypt 후,그것이 본인에게 옴. 
                    비밀키는 공개키로 잠근 것을 열 수 있음(반대로도 똑같음)
                    다른 사람이 공개키로 잠근 것을 열수 있음
                    이 공개키와 비밀키를 만드는데에 "소수"가 들어감
           
                    p라는 소수와 q라는 소수를 곱해서 만든 n값을 세간에 공개해도
                    시간이 너무 오래걸려서 p와 q를 알 수 없음
                    비밀키는 이 p와 q를 이용해서 만듦
                     => 그래서 보안에서 쓰이고 있음
                          if, P-NP가 증명되게 되면 
                          현실에 존재하는 모든 공개키, 비밀키의 비밀이 풀리고
                          전세계의 모든 사람들의 돈을 싹쓰리 가능(?)
       if, P=NP(P와 NP가 같다면) ????
          배우자 찾기도 팩토리얼의 시간복잡도인데 
          아무것도 안해도 배우자를 찾을 수 있는 상황이 되버림
          알고리즘도 쉽게 풀 수 있는 상황이 옴
          즉, 이 세상에 일어나는 모든 일들을 기계로 함축시킬 수 있게 됨
             -> 이 세계는 사이버공간이라는 말도 나올 수 있음