시간 복잡도에 대하여

1. 시간 복잡도란?
   1. 빅-오 표기법
      1. 최악의 경우 걸리는 시간
   2. 시간 복잡도 그래프
      1. 이진탐색 O(logN)
      2. 선형탐색 O(N)
      3. 정렬 O(N logN)
      4. 조합 O(N^2)
      5. 순열 O(N!)
   3. 입력 데이터 개수별 사용 가능한 시간 복잡도 알고리즘
      1. N 값에 따라 알고리즘 적용 시 최대 1억번이 안넘어야 한다.
      2. 1억이 넘는다 ? → 빨리 다른 알고리즘을 찾아봐야한다.
   4. 1. 잘못된 문제풀이
         1. 문제 확인 → 풀이 고안 & 작성→ 제출 → 완료
      2. 올바른 물제풀이
         1. 문제 확인 → 풀이 고안 → 효율성 체크 → 풀이 작성 → 제출 → 완료문제풀이 방법론

1. 시간 복잡도 계산하기
   1. 어림짐작하기 >> 반복문의 횟수를 계산해보자.
   2. 시간 복잡도를 줄이는 방법
      1. 정렬된 배열 arr에서 특정 원소의 위치를 찾을 때
         1. 전체 순회O(N) → 이진탐색 O(logN)
      2. 배열에서 중복 요소를 제거하고 싶을 때
         1. 전체 순회 O(N^2) → 자료구조 Set O(N)
2. 결론
   1. 시간 복잡도 : 코드작성 전 자신의 풀이가 충분히 효율적인지 판단할 수 있는 중요한 요소.
   2. 면접에서도 언급되는 만큼 풀이 고안 후 반드시 시간복잡도를 따지자.

느낀점

• 시간복잡도를 먼저 고안하는 것이 중요하다고 느꼈다.
• 내가 풀었던 방법이 정확하게 잘못된 방법이라고 나와있어서 조금 놀랐다.
• 조금 시간이 걸리더라도 시간복잡도는 O(XXX) 이군,,! 하면서 먼저 고려하는 습관을 들여야겠다고 생각했다.