1. 코딩테스트 준비하기

p. 17~30 (1일차)

강의: 강의 시간복잡도, 디버깅 (Java)

---

1. 시간복잡도: 주어진 문제를 해결하기 위한 연산 횟수  * 1억번의 연산 = 1초

✔ 표기법

  - 빅-오메가(Ω(n)): 최선일 때의 연산 횟수 표기법

  - 빅-세타(Θ(n)): 보통일 때의 연산 횟수 표기법

  - 빅-오(O(n)): 최악일 때의 연산 횟수 표기법

 

예)

**int findNumber = (int)(Math.random() * 100);

for(int i = 0; i < 100; i++) {

  if( i == findNumber) {

}

Ω ❗  i가 0이기 때문에 findNumber가 0일 때, for문에서 1번만에 출력 가능

Θ ❗ 평균적으로 50회 반복 시 값을 찾을 수 있음 즉, N을 2로 나눔

 

* 코테에서는 빅-오 표기법 (최악의 경우) 을 기준으로 수행 시간을 계산하는 것이 좋다.

** 알고리즘 마다 시간복잡도가 존재한다

    💥 외우는 것이 아니라 많이 이해해야 함

---

2. 시간복잡도 활용하기 *연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

✔ 알고리즘 적합성 평가

    -  데이터의 개수 확인하기 

    -  데이터 개수에 알맞는 알고리즘을 사용

        예) 제한시간 2초인 경우 => 2억 번 이하의 연산 횟수 내로

               ❓ 버블 정렬 = (1,000,000)²  = 1,000,000,000,000

                                       1,000,000,000,000 > 200,000,000 

               ❗ 부적합 알고리즘

 

              ❓ 병합 정렬 = nlongn

                                     1,000,000log(1,000,000) = 약 20,000,000

                                      20,000,000 < 200,000,000 (0.2초 내)

               ❗ 적합 알고리즘

 

✔ 시간 복잡도 도출

     -  상수는 시간 복잡도 계산에서 제외한다.

        * 연산횟수가 N인 경우와 3(상수)N인 경우 모두 큰 차이가 없다

           두 경우 모두 O(n)으로 같다.

 

     -  가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이다.

        * 일반 for문이 10개가 더 있다고 하더라도 시간복잡도는  N²로 유지다.

 

✔ 시간 복잡도 따지기

 1. 데이터와 알맞은 알고리즘 사용

 2. 비효율적인 로직 찾아서 효율적으로 변경

---

3. 디버깅 (오류 잡는 과정)

* log보다 디버깅을 사용하는 것이 오류를 더 빨리 찾을 수 있다.

✔ 디버깅 방법: 디버깅하고자 하는 줄에 중단점을 설정 후 디버깅 기능 실행

    -  중단점 여러개 설정 가능 (클릭)

    - 1줄씩 실행하거나 다음 중단점까지 실행 가능

 

✔ 실수하기 쉬운 4가지 사례

    -  변수 초기화 오류: 실행문 전에 변수값이 잘 초기화 되었는지 확인 가능

    -  반복문에서 인덱스 범위 지정 오류

    -  변수 사용 오류

    -  자료형 범위 오류

* 자료형은 처음부터 long형으로 선언하기!