다양한 난이도의 문제 예제

3.1 상수 시간 복잡도 문제 O(1).

인덱스를 통한 배열 요소 접근:

인덱스를 통한 배열 요소 접근은 상수 시간에 수행되는데, 이는 요소의 주소가 직접 계산되기 때문이야.

def get_element(arr, index):
    return arr[index]

리스트 앞에 요소 삽입 (Deque 사용):

deque를 사용하면 리스트의 앞에 요소를 상수 시간에 삽입할 수 있어.

from collections import deque

def insert_element(dq, element):
    dq.appendleft(element)

3.2 선형 시간 복잡도 문제 O(n).

배열에서의 선형 검색:

정렬되지 않은 배열에서의 요소 검색은 선형 시간이 걸려, 왜냐하면 각 요소를 확인해야 할 수도 있기 때문이야.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

배열의 요소 개수 세기:

모든 배열 요소를 한 번 세는데 선형 시간이 걸려.

def count_elements(arr):
    count = 0
    for element in arr:
        count += 1
    return count

3.3 로그 시간 복잡도 문제 O(log n).

이진 검색:

정렬된 배열에서 이진 검색을 통해 요소를 찾는 것은 로그 시간이 걸려.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

이진 탐색 트리에 요소 삽입:

균형 이진 탐색 트리(BST)에 요소를 삽입하는 것은 로그 시간이 걸려.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
        
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

3.4 제곱 시간 복잡도 문제 O(n^2).

버블 정렬:

버블 정렬로 배열을 정렬하는 것은 제곱 시간이 걸려.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

이중 루프를 통한 중복 체크:

이중 루프를 사용해 배열에 중복이 있는지 확인하는 것은 제곱 시간이 걸려.

def has_duplicates(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

3.5 지수 시간 복잡도 문제 O(2^n).

하노이 탑 문제:

하노이 탑 문제를 해결하는 것은 지수 시간이 걸려, 왜냐하면 각각의 디스크를 이동시켜야 하기 때문이야.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

집합의 모든 부분 집합 생성:

집합의 모든 부분 집합을 생성하는 것은 지수 시간이 걸려, 각각의 부분 집합을 고려해야 하기 때문이야.

def generate_subsets(s):
    result = []
    subset = []

    def backtrack(index):
        if index == len(s):
            result.append(subset[:])
            return
        subset.append(s[index])
        backtrack(index + 1)
        subset.pop()
        backtrack(index + 1)
        
    backtrack(0)
    return result
        
print(generate_subsets([1, 2, 3]))