코딩테스트 - 알고리즘

시간복잡도

• "내 코드가 채점 서버의 시간 제한(보통 1초) 안에 통과할 수 있을까?"를 예측하는 척도
  • "입력 데이터($N$)가 많아질 때, 계산 시간이 얼마나 늘어나는가?"를 나타내는 그래프 기울기
    • 절대적인 시간(몇 초)이 아니라, 연산 횟수의 증가 추세를 봄
• Big-O 표기법($O$)으로 불림

---

예시로 이해하기

• ex. 해리포터 책 찾기

• $O(1)$ - 상수 시간 (최고)

  • 사서에게 물어보니 "A구역 3번째 칸에 있어요"라고 바로 알려줍니다.
  • 책이 100권이든 100만 권이든, 단 한 번에 찾습니다.
  • 예: set 이나 dict 에서 key 로 찾기,li[3] 처럼 인덱스로 접근하기

• $O(\log N)$ - 로그 시간 (아주 빠름)

  • 책이 제목순으로 정렬되어 있습니다.
  • 책장의 딱 중간을 펴보고, '해리포터'보다 뒤쪽이면 앞쪽 절반은 버립니다.
  • 이렇게 범위를 절반씩 줄여나갑니다.
  • 예: 이분 탐색, 이진 트리.

• $O(N)$ - 선형 시간 (보통)

  • 책이 뒤죽박죽 섞여 있습니다.
  • 첫 번째 책부터 끝까지 하나하나 제목을 확인해야 합니다.
  • 운 없으면 마지막에 찾습니다
  • 예: for문 1개, if a in list (리스트 탐색).

• $O(N^2)$ - 제곱 시간 (느림)

  • 책 한 권을 집을 때마다, 도서관의 다른 모든 책과 비교해서 색깔이 같은지 확인합니다.
  • 책이 10배 늘어나면 시간은 100배 걸립니다.
  • 예: 이중 for문 (방금 겪으신 시간 초과의 원인)

---

코드로 이해하기

• $O(1)$ - 즉시 완료

def method1(arr):
    print(arr[0])  # 데이터 크기와 상관없이 딱 1번 실행

• $O(N)$ - 데이터만큼 비례

def method2(arr):
    for x in arr:  # 데이터가 10개면 10번, 100개면 100번
        print(x)

• $O(N^2)$ - 데이터의 제곱만큼 (위험!)

def method3(arr):
    for i in arr:       
        for j in arr:   
            print(i, j) 

---

이분 탐색 (Binary Search)

• "범위를 절반씩 뚝뚝 잘라내며 찾는 방법" ($O(\log N)$)
  • '업-다운(Up-Down) 게임' 과 동일함

필수조건

• 이분 탐색을 쓰려면 데이터가 반드시 정렬(Sorted)되어 있어야 함
  • 숫자가 뒤죽박죽 섞여 있다면(예: [50, 10, 90])
    • 중간값이 50이라고 해서 찾으려는 값이 왼쪽에 있는지 오른쪽에 있는지 알 수 없기 때문
  • 그래서 문제 풀 때 순서는 보통 입력 받기 -> 정렬하기 -> 이분 탐색 순서

코드 사용

• start - 탐색 범위의 시작 인덱스

  • end - 탐색 범위의 끝 인덱스

    • mid - 중간 인덱스

def binary_search(array, target):
    # 1. 탐색 범위 설정 (처음에는 전체 리스트)
    start = 0
    end = len(array) - 1

    # 2. 범위가 유효할 때까지 반복 (start가 end를 넘어가면 종료)
    while start <= end:
        mid = (start + end) // 2  # 중간 인덱스 구하기
        
        # 3. 찾았을 때
        if array[mid] == target:
            return mid  # 찾은 위치(인덱스) 반환
            
        # 4. 타겟이 중간값보다 클 때 (오른쪽 절반 탐색)
        elif array[mid] < target:
            start = mid + 1
            
        # 5. 타겟이 중간값보다 작을 때 (왼쪽 절반 탐색)
        else:
            end = mid - 1
            
    return -1  # 끝까지 못 찾으면 -1 반환 (또는 None, False 등)

# 사용 예시
nums = [1, 3, 5, 7, 9, 11] # 정렬된 리스트
print(binary_search(nums, 7)) # 결과: 3 (인덱스 3에 위치함)

---

스택(Stack)과 큐(Queue)

• 가장 기본이 되는 자료구조
  • 데이터가 들어오고 나가는 순서가 다름

스택 (Stack)

• 후입선출 (LIFO - Last In First Out)

  • 비유: 설거지통에 쌓인 접시. 나중에 넣은 접시를 가장 먼저 꺼냅니다.
  • 사용처: '되돌리기(Undo)' 기능, 괄호 짝 맞추기 (()), 깊이 우선 탐색(DFS)

큐 (Queue)

• 선입선출 (FIFO - First In First Out)

  • 비유: 맛집 줄 서기. 먼저 온 사람이 먼저 들어갑니다.
  • 사용처: 순서대로 업무 처리하기, 너비 우선 탐색(BFS)

파이썬 팁

• 스택: 그냥 list를 쓰면 됩니다. (append(), pop())
• 큐: collections 모듈의 deque를 써야 시간 초과가 안 납니다

---

DFS (Depth-First Search)

• 깊이 우선 탐색

이론

• 원리
  • 갈림길이 나오면 한 우물만 끝까지 팝니다.
  • 막히면 다시 돌아와서 다른 길을 갑니다.
• 구현
  • 재귀함수(Recursion) 또는 스택 사용

---

BFS (Breadth-First Search)

• 너비 우선 탐색

이론

• 원리
  • 갈림길에서 연결된 곳을 동시에 넓게 퍼져나가며 찾습니다.
  • 호수에 돌 던졌을 때 물결이 퍼지는 모양
• 구현
  • 큐(Queue) 사용
• 특징
  • "최단 거리"를 구할 때 무조건 사용합니다.

---

해시 (Hash) - 딕셔너리

• set / dict

이론

• 핵심

  • 데이터를 저장하고 찾는 속도가 $O(1)$로 매우 빠릅니다.

• 사용처

  • "A라는 사람이 명단에 있나?", "과일 별로 재고가 몇 개 남았나?" 같은 문제를 풀 때
    • 리스트보다 훨씬 강력합니다.

---

스택(Stack)

• LIFO (Last In, First Out)
  • 가장 나중에(Last) 넣은 것이 가장 먼저(First) 나옵니다.
• 접시를 쌓을 때 맨 위에 올리고(Push), 꺼낼 때도 맨 위에서부터 꺼내죠(Pop)? 그게 바로 스택입니다.

---

큐(Queue)

• FIFO(First-In-First-Out, 선입선출) 구조
  • 즉, 가장 먼저 들어간 데이터가 가장 먼저 나와야 합니다.

• collections.deque

  • deque는 양방향 큐로, 앞쪽에서 데이터를 빼는 popleft() 작업이 $O(1)$의 시간 복잡도