알고리즘에 대해서

코드포시스 난이도 800점을 풀기 전 알아야 될 기본적인 개념들을 정리합니다.

1. 알고리즘이란?

알고리즘(Algorithm)은 특정 문제를 해결하기 위한 일련의 절차나 규칙들의 모음입니다.

알고리즘의 특성

• 입력: 0개 이상의 입력이 필요
• 출력: 1개 이상의 결과를 출력
• 명확성: 각 단계가 명확하게 정의되어야 함
• 유한성: 유한한 시간 안에 종료
• 효율성: 효율적인 방법이어야 함

2. 알고리즘의 중요성

프로그래밍에서 알고리즘은 매우 중요합니다:

1. 문제 해결: 복잡한 문제를 단계적으로 해결
2. 효율성: 실행 시간과 메모리 최적화
3. 코드 품질: 깔끔하고 유지보수하기 쉬운 코드 작성

3. 시간 복잡도와 공간 복잡도

알고리즘의 성능을 측정하는 기준:

• 시간 복잡도(Time Complexity): 알고리즘 실행 시간
• 공간 복잡도(Space Complexity): 알고리즘 사용 메모리

Big O 표기법

표기	이름	예시
O(1)	상수	배열 인덱싱
O(log n)	로그	이진 탐색
O(n)	선형	선형 탐색
O(n log n)	선형로그	병합 정렬
O(n²)	제곱	버블 정렬
O(2ⁿ)	지수	조합 문제

4. 기본 정렬 알고리즘

버블 정렬 (Bubble Sort)

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]
    return arr

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)

선택 정렬 (Selection Sort)

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)

5. 탐색 알고리즘

선형 탐색 (Linear Search)

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

• 시간 복잡도: O(n)

이진 탐색 (Binary Search)

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

• 시간 복잡도: O(log n)
• 조건: 배열이 정렬되어 있어야 함

정리

알고리즘 공부는 프로그래머의 기초입니다. 다음 글에서는 더 복잡한 알고리즘들을 배워보겠습니다.

---