CS_알고리즘 공부 : 알고리즘 관련 기초 개념 정리.

◇ 알고리즘 관련 기초 개념 정리.

목  차

1. 알고리즘이란
2. 알고리즘의 계산 복잡도

Ⅰ. 알고리즘이란?

🩻. 알고리즘의 개념.

"알고리즘"이란, 주어진 문제를 해결하기 위한 명확하고 순차적인 단계별 절차입니다.

프로그래밍상에서 '알고리즘'은
특정 작업을 수행하거나 문제를 해결하기 위한 명확한 지침의 집합을 의미합니다.

🩻. 알고리즘의 주요 특징.

• 명확성 : 각 단계는 모호하지 않고 명확해야 합니다.
• 유한성 : 알고리즘은 반드시 유한한 수의 단계 후에 종료되어야 합니다.
• 입력과 출력 : 정해진 입력을 받아서 원하는 결과를 출력합니다.
• 효율성 : 실행 가능한 시간 내에 문제를 해결할 수 있어야 합니다.

🩻. 알고리즘의 중요성.

"알고리즘"은 프로그래밍의 기초가 되며,
동일한 문제에 대해 여러가지 해결방법이 존재할 수 있습니다.

따라서 문제 해결을 위해 가장 효율적인 알고리즘을 선택하는 것이 중요합니다.

🩻. 알고리즘 분석.

: 알고리즘 분석은 다음과 같은 요소들을 고려합니다.

• "시간 복잡도" : 알고리즘 실행에 필요한 시간.
• "공간 복잡도" : 알고리즘이 사용하는 메모리의 양.
• "정확성" : 모든 입력에 대해 올바른 출력을 생성하는지 여부.

Ⅱ. 알고리즘의 계산 복잡도

🩻. 입력 크기와 계산 횟수.

'알고리즘'의 성능을 평가할 때 입력 크기와 계산 횟수는 핵심적인 요소입니다.

• 입력 크기와 계산 횟수는 알고리즘의 수행 성능에 영향을 미칩니다.
• 대체로, 입력 크기가 작고 계산 횟수가 적을수록 수행 성능은 향상됩니다.

예시: 1부터 n까지의 합을 for 반복문으로 구할 때

• n은 입력 크기에 해당한다.
• 그런데, 프로그램은 덧셈을 1부터 n까지 n-1번 수행해야 하므로, 계산 횟수가 n에 정비례한다.

# 반복문을 사용한 방법 - O(n)
def sum_to_n(n):
    sum = 0
    for i in range(1, n+1):
        sum += i
    return sum

# 수학적 공식을 사용한 방법 - O(1)
def sum_to_n_formula(n):
    return n * (n + 1) // 2

첫 번째 방법은 n번의 반복이 필요하므로 O(n)의 시간 복잡도를 가집니다.
반면 두 번째 방법은 입력 크기와 관계없이 일정한 연산만 수행하므로 O(1)의 시간 복잡도를 가집니다.

🩻. 계산 복잡도의 표현 : 대문자 O 표기법.

계산 복잡도(complexity)

: 어떤 알고리즘이 문제를 해결하기 위해 해야하는 계산과정이 얼마나 복잡한지를 나타내는 정도.

• 대표적인표기법 : 'Big O' 표기법

표기법.

O(1) - 상수 시간
: 상수 시간 복잡도는 입력 크기와 관계없이 항상 동일한 실행 시간을 가집니다.
가장 효율적인 시간 복잡도입니다.

대표적인 예시:

배열의 특정 인덱스 접근

스택의 push/pop 연산

해시 테이블의 삽입/조회

O(log n) - 로그 시간
: 입력 크기가 증가할 때 실행 시간이 로그적으로 증가합니다.
매우 효율적인 시간 복잡도로 간주됩니다.

대표적인 예시:

이진 탐색

균형 이진 트리 연산

분할 정복 알고리즘

O(n) - 선형 시간
: 실행 시간이 입력 크기에 비례하여 선형적으로 증가합니다.

대표적인 예시:

배열 순회

선형 탐색

단일 반복문

O(n²) - 이차 시간
: 실행 시간이 입력 크기의 제곱에 비례하여 증가합니다4.

대표적인 예시:

중첩된 반복문

버블 정렬

선택 정렬

O(2ⁿ) - 지수 시간
: 입력 크기가 1 증가할 때마다 실행 시간이 2배씩 증가합니다.
가장 비효율적인 시간 복잡도 중 하나입니다.

대표적인 예시:

재귀적 피보나치 수열 계산

부분집합 생성

완전 탐색 알고리즘

대체로 입력 크기가 큰 문제를 풀 때는
복잡도 O(1)인 알고리즘이 O(n)인 알고리즘보다 훨씬 더 빠른 경향이 있습니다.

🩻. 계산 복잡도의 세부 항목.

:알고리즘의 계산 복잡도는 시간 복잡도와 공간 복잡도로 나누어 분석합니다.

시간 복잡도

시간 복잡도는 알고리즘의 수행 시간을 평가하는 지표입니다.
.

• 주요 특징:

  • 측정 방식:

    • 기본 연산(데이터 입출력, 산술 연산, 제어 연산)의 실행 횟수로 평가9

    • Big O 표기법을 사용하여 최악의 경우를 표현

• 주요 시간 복잡도 분류:

  • O(1): 상수 시간 - 입력 크기와 무관한 일정 시간

  • O(log n): 로그 시간 - 이진 탐색 등

  • O(n): 선형 시간 - 단일 반복문

  • O(n log n): 선형 로그 시간 - 퀵소트, 머지소트

  • O(n²): 이차 시간 - 이중 반복문

  • O(2ⁿ): 지수 시간 - 재귀적 피보나치 수열

공간 복잡도

공간 복잡도는 알고리즘 실행에 필요한 메모리 공간을 측정하는 지표입니다.

• 구성 요소:

  • 입력 공간: 입력 데이터가 차지하는 공간

  • 보조 공간: 알고리즘 실행 중 임시로 사용하는 추가 공간

• 특징:

  • 고정 공간: 입력 크기와 무관한 상수 공간

  • 가변 공간: 입력 크기에 따라 변하는 공간

현대에는 하드웨어 메모리 용량이 크게 향상되어,
일반적으로 시간 복잡도가 공간 복잡도보다 더 중요하게 고려됩니다