[딩코딩코 2025 코딩테스트 필수 알고리즘] - 3. 점근 표기법

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp

---

점근 표기법이란?

접근 표기법이란 알고리즘의 성능을 수학적으로 표기하는 방법이다. 또한 알고리즘의 효율성을 평가하고, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이라고 할 수 있다.

점근 표기법 종류

점금 표기법 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법 이 있다.

빅오 표기법 은 최악의 성능이 나올 때 어느정도의 연산량이 걸릴것인지

빅오메가 표기법 은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

에 대해 표기하는 방법이다.

알고리즘으로 점근 표기법 이해하기

더 정확하게 이해하기 위해 코드를 통해 이해해보자

문제

Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.

[3, 5, 6, 1, 2, 4]

def is_number_exist(number, array):
    # 이 부분을 채워보세요!
    return True

result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3, [3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7, [6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2, [6,9,2,7,1888]))

해결 방법

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False

result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

그러면 이 함수의 시간 복잡도는 얼마나 걸릴까? array 의 길이만큼 연산 * 비교 연산 1번 = N * 1 = N 즉, N 만큼의 시간 복잡도를 가지는 것을 알 수 있다.

그런데 모든 경우에 N 만큼의 시간이 걸릴까? input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾으면, 첫번째 원소를 비교하는 순간 결과값을 반환한다.

그러나 input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 어떻게 될까? 마지막 원소 끝까지 찾다가 겨우 마지막에 3을 찾아 결괏값을 반환하게 된다.

즉, 위의 경우에는 빅오 표기법으로 표시하면 $O(N)$, 빅 오메가 표기법으로 표시하면 $Ω(1)$ 의 시간복잡도를 가진 알고리즘이다 라고 할 수 있다.

지금까지 우리는 항상 최악의 경우, 빅오 표기법으로 분석해왔다. 그 이유는 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문이다.

지금까지 시간복잡도, 공간복잡도, 점근표기법을 배우면서 아래를 기억하면 된다.

1. 입력값에 비례해서 얼마나 늘어날지 파악하자. (1 , N , N^2)
2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자.