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

알고리즘과 자료구조란?

알고리즘 (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: 배열과 문자열"에 대해 학습하겠습니다.