Skip to content

algorithm_performance_with_cpp_examples.md

Latest commit

 

History

History
124 lines (88 loc) · 5.58 KB

algorithm_performance_with_cpp_examples.md

File metadata and controls

124 lines (88 loc) · 5.58 KB

알고리즘 성능 측정 및 공간 복잡도 고려

시간 복잡도(Time Complexity)

알고리즘의 성능을 측정하는 데 있어 중요한 척도는 시간 복잡도입니다. 시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 입력값의 크기와 관련지어 표현한 것입니다. 입력값이 커질수록 알고리즘의 실행 시간이 어떻게 변하는지를 나타내며, 이를 통해 알고리즘의 효율성을 평가할 수 있습니다.

문제 요구 성능 파악

문제에서 요구하는 성능을 파악하기 위해서는 주어진 입력값을 통해 시간 복잡도를 구하고 이를 기준으로 성능을 분석해야 합니다. 이는 주어진 문제를 해결하는 데 있어 적합한 알고리즘을 선택하는 데 중요한 역할을 합니다.

재귀 함수와 공간 복잡도

재귀 함수를 사용할 때는 시간 복잡도뿐만 아니라 공간 복잡도도 고려해야 합니다. 재귀 함수는 호출될 때마다 함수 코드 영역, 함수에서 사용하는 변수 영역, 매개변수 영역이 메모리에 할당됩니다. 예를 들어, 10!을 구할 때는 메모리에 10개의 함수 호출이 쌓이게 됩니다.

주의사항:

  1. 공간 복잡도: 재귀 함수는 메모리 사용이 많을 수 있습니다.
  2. 재귀 깊이 제한: 일부 언어는 재귀 깊이 제한이 있습니다. (예: 파이썬)

예시: C++의 재귀 깊이 제한

#include <iostream>
using namespace std;

void recursiveFunction(int depth) {
    if (depth == 0) return;
    recursiveFunction(depth - 1);
}

int main() {
    recursiveFunction(1000);  // 재귀 깊이 1000으로 호출
    return 0;
}

재귀 깊이 제한을 넘어가는 경우 스택 오버플로우가 발생할 수 있습니다.

자료구조와 시간 복잡도

각 언어에서 제공하는 자료구조의 메서드의 시간 복잡도를 이해하고 정리하는 것은 중요합니다. 단순히 GitHub에서 제공하는 코드를 복사해서 사용하는 것이 아니라, 직접 구현해보고 성능 차이를 이해해야 합니다. 이를 통해 문제 분석 후 요구하는 성능에 맞는 구현 전략을 세울 수 있습니다.

STL 컨테이너 및 알고리즘의 시간복잡도

자료구조/알고리즘 접근 탐색 삽입 삭제
배열(Array) O(1) O(n) O(n) O(n)
연결 리스트(Linked List) O(n) O(n) O(1) O(1)
스택(Stack) O(n) O(n) O(1) O(1)
큐(Queue) O(n) O(n) O(1) O(1)
해시맵(HashMap) - O(1) O(1) O(1)
트리(Tree) O(log n) O(log n) O(log n) O(log n)
힙(Heap) O(n) O(1) O(log n) O(log n)

코드 개선과 시간 복잡도

시간 제한 초과(TLE) 문제를 해결하기 위해서는 시간 복잡도를 고려하여 연산 횟수가 많은 부분을 찾아 개선해야 합니다. 전체 코드에서 시간이 많이 소요되는 부분을 찾아 효율적인 알고리즘으로 대체함으로써 성능을 개선할 수 있습니다.

예시: 코드 개선

아래는 배열에서 중복된 요소를 제거하는 코드의 예시입니다.

개선 전:

#include <vector>
using namespace std;

vector<int> removeDuplicates(const vector<int>& arr) {
    vector<int> result;
    for (int i : arr) {
        if (find(result.begin(), result.end(), i) == result.end()) {
            result.push_back(i);
        }
    }
    return result;
}

위 코드는 중복 검사를 위해 find 함수를 사용하므로 시간 복잡도는 O(n^2)입니다.

개선 후:

#include <vector>
#include <unordered_set>
using namespace std;

vector<int> removeDuplicates(const vector<int>& arr) {
    unordered_set<int> s(arr.begin(), arr.end());
    return vector<int>(s.begin(), s.end());
}

unordered_set 자료형을 사용하면 시간 복잡도가 O(n)으로 개선됩니다.

의사코드(Pseudocode)

의사코드는 구현하기 전 데이터의 흐름을 정리하고, 로직을 명확히 하는 데 사용됩니다. 이는 문제 해결 과정에서 중요한 단계로, 전체 시간의 6070%를 할애할 가치가 있습니다. 구현 단계는 3040% 정도로 시간 배분을 하면 좋습니다.

시간 복잡도 정리

자료구조를 배울 때 각 메서드의 시간 복잡도를 정리해보겠습니다. 이는 직접 구현해보고 성능 차이를 이해하는 데 도움이 됩니다.

예시: 리스트(List)

  • 탐색: O(n)
  • 삽입/삭제 (중간): O(n)
  • 삽입/삭제 (끝): O(1)

예시: 해시맵(HashMap)

  • 탐색: O(1)
  • 삽입: O(1)
  • 삭제: O(1)

이해하고 직접 구현해보면서 성능 차이를 경험해보는 것이 중요합니다. 이를 통해 문제 분석 후 요구하는 성능에 맞는 구현 전략을 세울 수 있습니다.

결론

  • 시간 복잡도는 알고리즘 성능 측정의 중요한 척도입니다.
  • 재귀 함수를 사용할 때는 공간 복잡도도 고려해야 합니다.
  • 자료구조의 각 메서드의 시간 복잡도를 이해하고 정리하는 것이 중요합니다.
  • 코드 개선 시 시간 복잡도를 고려하여 주요 연산 부분을 최적화해야 합니다.
  • 의사코드를 통해 데이터 흐름을 정리하고 구현 전 로직을 명확히 해야 합니다.

학습 과정에서 복사 붙여넣기가 아니라 직접 구현하고 성능 차이를 이해하는 것이 중요합니다. 이를 통해 문제 분석 후 적절한 구현 전략을 세울 수 있는 능력을 키워야 합니다.