-----ETC-----/C++로 배우는 알고리즘과 자료구조 시리즈

[C++로 배우는 알고리즘과 자료구조] Day 1: 알고리즘과 자료구조 소개

cogito21_cpp 2024. 7. 1. 13:00
반응형

알고리즘과 자료구조란?

알고리즘 (Algorithm)

알고리즘은 주어진 문제를 해결하기 위해 설계된 일련의 절차나 방법입니다. 알고리즘은 컴퓨터 과학에서 매우 중요한 개념으로, 효율적인 문제 해결과 성능 최적화를 위해 필수적입니다.

알고리즘의 특징:

  1. 명확성 (Clarity): 각 단계는 명확하고 이해하기 쉬워야 합니다.
  2. 유한성 (Finiteness): 알고리즘은 반드시 종료되어야 합니다.
  3. 입력 (Input): 0개 이상의 입력이 있어야 합니다.
  4. 출력 (Output): 1개 이상의 출력이 있어야 합니다.
  5. 효율성 (Efficiency): 시간과 공간 측면에서 효율적이어야 합니다.

자료구조 (Data Structure)

자료구조는 데이터를 저장하고 조직화하는 방법입니다. 자료구조는 데이터에 대한 접근 및 수정 작업을 효율적으로 수행할 수 있도록 설계됩니다. 적절한 자료구조를 선택하는 것은 알고리즘의 성능을 최적화하는 데 중요합니다.

자료구조의 종류:

  1. 기본 자료구조: 배열, 연결 리스트, 스택, 큐 등.
  2. 트리: 이진 트리, AVL 트리, 힙 등.
  3. 그래프: 인접 리스트, 인접 행렬 등.
  4. 해시 테이블: 키-값 쌍을 저장하는 자료구조.

알고리즘의 성능 분석

알고리즘의 성능을 평가하기 위해 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 사용합니다.

시간 복잡도 (Time Complexity)

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 나타내며, 일반적으로 입력 크기 ( n )에 대한 함수로 표현됩니다. Big-O 표기법을 사용하여 알고리즘의 시간 복잡도를 나타냅니다.

  • O(1): 상수 시간
  • O(log n): 로그 시간
  • O(n): 선형 시간
  • O(n log n): 로그 선형 시간
  • O(n^2): 이차 시간
  • O(2^n): 지수 시간

공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타내며, 입력 크기 ( n )에 대한 함수로 표현됩니다.

 

예제: 배열의 합 구하기

배열의 합을 구하는 간단한 알고리즘을 통해 알고리즘과 자료구조의 기본 개념을 이해해 보겠습니다.

#include <iostream>
#include <vector>

// 배열의 합을 구하는 함수
int arraySum(const std::vector<int>& arr) {
    int sum = 0; // 합을 저장할 변수 초기화
    for (int num : arr) {
        sum += num; // 배열의 각 요소를 합에 더함
    }
    return sum; // 최종 합 반환
}

int main() {
    // 예제 배열
    std::vector<int> arr = {1, 2, 3, 4, 5};

    // 배열의 합 계산 및 출력
    int sum = arraySum(arr);
    std::cout << "배열의 합: " << sum << std::endl; // 결과 출력

    return 0;
}

 

설명

  • 입력: 배열 ( arr )
  • 출력: 배열의 모든 요소의 합
  • 시간 복잡도: O(n) (배열의 모든 요소를 한 번씩 순회하기 때문)
  • 공간 복잡도: O(1) (추가적인 메모리 사용이 거의 없음)

위의 예제에서는 배열의 각 요소를 순회하며 합을 계산합니다. 이 알고리즘은 입력 배열의 크기에 따라 선형적으로 실행 시간이 증가하므로, 시간 복잡도는 O(n)입니다.

이제 알고리즘과 자료구조의 기본 개념을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 2: 배열과 문자열"에 대해 학습하겠습니다.

반응형