자료구조와 알고리즘

1. 추상자료형(Abstract Data Type, ADT)

• 데이터와 해당 데이터에 수행할 수 있는 연산을 정의하지만, 구현 방법은 명시하지 않음.
• 예시: 가방(Bag)의 추상자료형
  • 데이터: 중복 허용, 순서 없음, 비교 가능
  • 연산:

    def contains(bag, e):  # 특정 요소가 존재하는지 확인
        return e in bag
    
    def insert(bag, e):  # 요소 추가
        bag.append(e)
    
    def remove(bag, e):  # 요소 삭제
        bag.remove(e)
    

---

2. 알고리즘 성능 분석

(1) 실행 시간 측정

• 실제 실행 시간 측정
  → time 모듈을 이용하여 실행 시간을 측정할 수 있음.

  import time
  
  def example():
      start = time.time()  # 시작 시간
      # 실행할 코드
      time.sleep(2)  # 예제: 2초 대기
      end = time.time()  # 종료 시간
      print(f"실행 시간: {end - start:.6f} 초")
  
  example()
  

• 한계점
  • 동일한 하드웨어 및 소프트웨어 환경에서 실행해야 함.
  • 단순한 경우에는 효과적이지만, 일반적으로 알고리즘의 복잡도 분석이 더 중요.

---

(2) 알고리즘 복잡도 분석

• 알고리즘의 성능을 **입력 크기(n)에 따른 연산 횟수(T(n))**로 평가.

점근적 표기법(Asymptotic Notation)

• 복잡도 표기 예시:
  • T(n)=65666n+100000T(n) = 65666n + 100000 → O(n)
  • T(n)=n2+2nT(n) = n^2 + 2n → O(n²)
• 핵심 개념:
  • 가장 큰 차수의 항만 남김 (고차항이 지배적)
  • 상수 계수는 무시 (성장 속도에 미미한 영향)
  • O(n2)O(n²)은 O(n)O(n)보다 증가 속도가 훨씬 빠름 (n이 커질수록 차이 커짐)

Big-O 표기법 예시

알고리즘 시간 복잡도 예제

상수 시간	O(1)	배열 인덱스 접근
로그 시간	O(log n)	이진 탐색
선형 시간	O(n)	배열 전체 탐색
선형 로그	O(n log n)	병합 정렬, 퀵 정렬 평균
이차 시간	O(n²)	버블 정렬, 삽입 정렬
세제곱 시간	O(n³)	플로이드 워셜 알고리즘
지수 시간	O(2ⁿ)	피보나치(단순 재귀)
계승 시간	O(n!)	외판원 문제(브루트 포스)

---

(3) 복잡도 예제

1) O(n) 예제

def linear_search(arr, target):
    for i in range(len(arr)):  # 전체 탐색 (O(n))
        if arr[i] == target:
            return i
    return -1

2) O(n²) 예제

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):  # 중첩 반복문 (O(n²))
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

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

---

3. 결론

• 추상자료형: 데이터와 연산을 정의하지만 구현은 X
• 실행 시간 측정: time 모듈로 확인 가능하나 환경에 따라 변동
• 복잡도 분석:
  • 점근적 표기법(Big-O)로 알고리즘 증가 속도를 분석
  • 고차항 우선, 상수 무시 (O(n²) > O(n log n) > O(n))
  • Big-O 개념을 이해하면 최적의 알고리즘 선택 가능