코딩테스트를 위한 알고리즘과 시간복잡도

알고리즘

알고리즘은 문제를 해결하는 방법입니다.

한 문제를 해결하는 방법은 무수히 많습니다.  그 중 자주 쓰이는 해결 방법에는 다익스트라, DP, DFS 등과 같이 이름을 붙여서 문제를 해결하는 방법을 패턴화 하였고 이것을 알고리즘 이라고 합니다.

알고리즘을 학습하여 응용, 적응 할 수 있게 된다면 코딩테스트의 문제를 보다 쉽게 해결할 수 있습니다.

 

 

알고리즘의 평가 기준

알고리즘의 평가 기준에는 3가지가 있습니다.

1. 시간 복잡도 : 문제를 해결하는데 걸리는 시간 과 관련이 있습니다. 시간이 적게 소요될 수록 좋은 알고리즘이라고 할 수 있습니다. 

2. 공간 복잡도 : 한정된 메모리를 최대한 적게 사용할 수록 효율적입니다. 공간 복잡도를 통해 알고리즘이 메모리를 얼마나 차지하게 될 지 나타냅니다.

3. 구현 복잡도 : 개발자는 보통 협업을 하기 때문에, 구현이 너무 복잡해지고 알아보기 힘든 코드를 작성해서는 안됩니다. 나중에 보아도 이해하기 쉬운 코드를 작성하도록 해야합니다.

 

국내 기업의 코딩 테스트에서는 시간 복잡도를 가장 중요하게 생각하는 것 같습니다. 

 

 

시간 복잡도

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력값 n의 관계를 의미합니다.

시간 복잡도를 통해 실행시간이 얼마나 걸릴지를 예상 할 수 있습니다.

시간 복잡도는 Big-O 표기법으로 표현합니다.

 

입력 n에 대한 실행 시간을 O(n)  같이 표시 합니다.

 

간단한 코드로 빅오 표기법을 알아보겠습니다.

 

1. simple statements : O(1)

num=0
num+=1

 

2. single loop : O(n)

3. nested loop : O(n^2)

def example_function(arr):
    n = len(arr)

    # 첫 번째 반복문
    for i in range(n):
        print(i)

    # 두 번째 반복문
    for i in range(n):
        for j in range(n):
            print(i, j)

    # 세 번째 반복문
    for i in range(n):
        print(arr[i])

# 예시 입력 데이터
example_array = [1, 2, 3, 4, 5]

# 함수 호출
example_function(example_array)

 

이 코드의 시간 복잡도는 세 부분으로 나뉩니다. 첫 번째 반복문의 시간 복잡도는 O(n), 두 번째 반복문은 O(n^2), 세 번째 반복문은 O(n)입니다. 전체 함수의 시간 복잡도는 이 세 부분의 시간 복잡도 중 가장 큰 값으로 결정됩니다. 따라서 이 코드의 전체 시간 복잡도는 O(n^2)입니다.

 

4. 두 번 재호출 하는 재귀 함수 : O(2^n)

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        # 재귀 호출로 인해 2^n의 호출이 발생
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 피보나치 수열의 n번째 항을 계산
result = fibonacci_recursive(5)
print(result)

 

5. 이진탐색과 같이 탐색하는 데이터가 반씩 줄어드는 함수 : O(logn)

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # 중간 인덱스 계산

        if arr[mid] == target:
            return mid  # 찾은 경우 해당 인덱스 반환
        elif arr[mid] < target:
            low = mid + 1  # 중간 값이 타겟보다 작으면 오른쪽 반탐색
        else:
            high = mid - 1  # 중간 값이 타겟보다 크면 왼쪽 반탐색

    return -1  # 타겟이 배열에 없는 경우

# 정렬된 배열
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# 이진 탐색 호출
target_index = binary_search(sorted_array, 5)
print(target_index)

 

 

시간 복잡도의 크기 순서

n! > 2^n > n^3 > n^2 > nlogn > n > logn > 1

 

 

코딩테스트를 위한 시간 복잡도

• sort 함수 :  O(nlogn)
• 이진탐색 : O(logn)
• heap
  • push() : O(logn)
  • pop() : O(logn)
  • 길이가 n인 array를 heap으로 : O(nlogn)
• Hash table
  • 구축 : O(n)
  • 검색 : O(1)