코딩 테스트 스터디 1주차

코딩테스트 합격자 되기 1주차

[공부할 내용]

시간복잡도

• 왜 시간복잡도가 필요한가?

• 점근적 표기법의 개념

• 알고리즘에 시간 복잡도를 적용하는 법

• 프로그래머스의 채점 방식

• 관련문제 3개정도 풀이

시간복잡도란?

• 입력값과 연산수행시간의 척도를 수치화하여 나타낸 것

그래서 시간복잡도는 왜 필요할까?

• 어느 환경에서나 동일한 성능측정을 하여 수치화된 값으로 나타내는게 시간복잡도인데, 시간복잡도를 확인함으로써 코드의 성능을 알 수 있고 효율적으로 관리할 수 있기 때문이다.

점근적 표기법

• 점근적표기법은 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation) 이 있습니다.
• 주로 코딩테스트에서는 빅오 표기법을 주로 사용합니다.
• 연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현하는데 점근표기법은 함수를 단순화하여 함수의 증가율을 다른 함수와의 비교로 표현하는 방법입니다. 이것으로 시간과 공간 복잡도를 표현할 수 있습니다.

알고리즘에 시간 복잡도를 적용하는 법

예를들어

  for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            count++
        }
    }

이런 자바스크립트 코드가 있다면 중첩for문에 대해

• 첫 번째 반복문의 최대 반복 횟수는 N이며
• 두 번째 반복문의 최대 반복 횟수도 N이므로
  O(N * N) = O(N²)이 된다.

또한

   for(i=0; i<N; i++) {
        count++
    }

    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            count++
        }
    }

일 경우에는 O(N² + N) 이 되는데 N의 값이 커질수록 차수가 높은 N² 에 비해 N 의 값은 한없이 작아져 유의미해지지 않게된다. 따라서 위의 식은 차수가 높은 최고차항의 값만 적용이 되기 때문에
O(N²) 로 나타낼 수 있다.

코딩테스트에서 가장 많이 나타나는 점근적표기법을 정리하자면 아래의 표로 나타낼 수 있다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
오른쪽으로 갈수록 비효율적이다.

프로그래머스의 채점 방식

자주 사용되는 예시를 들자면

• O(1) : 배열 인덱스를 통한 원소 직접 접근
• O(log n) : 이진탐색
• O(n) : 순차탐색 -> (N ≤ 10,000,000)
• O(n log n) : 정렬 -> (N ≤ 1,000,000)
• O(n²) : 행렬곱셉, 다항식 계산 -> (N ≤ 5,000)
• O(2ⁿ) : 부분집합 구하기, 하노이 -> (N ≤ 20)
• O(N!) : 순열생성, 외판원문제(TSP) -> (N ≤ 11)

화살표 뒤의 값은 대략적인 N의 크기에 따른 허용 시간복잡도 이다. (단, 맹신하지는 말 것!)

---

예제)

아래 다항식에 대해 점근적 상한을 구해주세요.

• Y = 2ˣ - 3X² + 5x -> O(2ˣ)

• Y = X² + X! - 2ˣ -> O(N!)

• Y = 3X + logX - 4 -> O(N)

아래 문제를 읽고 점근적 상한을 구해주세요.

• 데이터가 N개인 배열을 순차탐색하는 경우
  -> O(N)

• 행과 열이 각각 N개인 행렬의 원소를 모두 더하는 경우
  -> O(n²)

• N개의 동전을 던질때 앞/뒷면에 대한 모든 경우의 수
  ->O(2ⁿ)

프로그래머스 문제
1. 아이스 아메리카노

function solution(money) {
    var answer = [Math.floor(money/5500),money%5500];
    return answer;
}

--> O(1)
money값의 크기가 커져도 바로 출력값을 얻어낼 수 있다.

2. 중복된 숫자 개수

function solution(array, n) {
    var answer = array.filter(i => n === i).length
    return answer;
}

--> O(n)
내장함수 filter를 사용하여 순차탐색을 했다.

3. 팩토리얼

function solution(n) {
    var factorial = 1;
    var i = 1;
        
    while(factorial <= n) {
            i++;
            factorial *= i;  
        }
            
    return i-1;
    
}

--> O(N)
while문을 사용하여 n개인 배열을 factorial과 비교하며 순차탐색 했다.