[코딩 테스트 합격자 되기] 1주차 - 시간복잡도

 

해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다. 

 

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

 

💬주요 키워드

 

알고리즘 : 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의

 

시간복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

 

점근적 표기법 : 점근(漸近)이란 점점 가까워 지는 모양을 뜻합니다. 점근적 표기법 이라 함은 주워진 함수가 있을때, 보다 간단한 함수로 만들어 표시함을 뜻합니다.

 

빅오 표기법 : 알고리즘의 효율성을 점근적으로 표기해주는 표기법

---

 

🪄주제

 

 

---

📝생각 노트

 

      목차

1. 알고리즘이란?

2. 알고리즘 성능측정법 및 시간복잡도 개념

3. 시간복잡도를 빅오 표기법으로 표기하기

4. 코딩테스트에서 꼭 알아둬야 할 시간복잡도

5. 실전 예시

---

     알고리즘이란?

유한한 수의 규칙에 따라 구별가능한 기호들을 조작하여 입력에서 출력을 생성하기 위한 일반화된 작업

=> 알고리즘은 함수와 비슷하며 주어진 입력에 함수를 조합하여 출력을 생성하기 위한 작업

 

알고리즘의 요소는 정밀성,유일성 등 여러가지가 있지만, 코테에서는 타당성인 알고리즘의 성능이 중요하다.

 

출처 : https://ko.wikipedia.org/wiki/알고리즘

---

     알고리즘의 성능측정법 및 시간복잡도 개념

 

 

 

절대시간측정 vs 연산횟수 측정

 

- 절대시간측정 : 각 PC별 사양이 다르기 때문에 동일한 코드를 수행할 때, 다른 결과가 나올 수 있음.

컴퓨터 기준

알고리즘 성능 측정을 위해서는 환경에 제약을 받지 않는 기준이 있어야함

---

- 연산횟수측정 : 코드가 동일하면 연산횟수는 모두 동일하므로, 객관적 지표로 사용 가능

 코드 기준

연산횟수는 환경 영향을 받지 않으나, 입력값에 따라 달라질 수 있으므로 기준 필요

입력값에 따른 연산횟수가 일정하지 않은 경우(짝수는 N^2, 홀수는 N)최악의 경우를 기준으로 정함

 

---

 

 

     정리

- 코딩테스트에서 알고리즘의 성능은 연산횟수로 측정, 이를 시간복잡도 라고 함.

---

 

      시간복잡도를 빅오 표기법으로 표기하기(점근적 표기법)

 

N^2 + 3N + 5의 그래프

 

N이 커질수록 격차가 커지는 구조.

N이 1만, 1억, 무한대로 넘어간다면 N^2 >>>>>>>>범접불가>>>>>>>> 3N 

 

코딩테스트는 연산횟수를 측정하는 시험이 아님.

어느정도 복잡한지 대략적으로 알면 충분하므로

(N^2 + 3N + 5) == O(N^2)

라는 결과가 나옴

---

     정리

- 다항식에서 가장 많이 영향을 미치는 항을 남기고 제거

- 마지막 남은 항의 계수를 제거

 

 

 

---

     코딩테스트에서 꼭 알아둬야 할 시간복잡도

 

1. 이차원 배열 O(N*M)

 O(가로 * 세로)

 

---

2.  이진탐색트리 O(logN)

 시간복잡도 상으로 효율적인 알고리즘

 

---

3. 순열 O(2^N) 

 

 시간복잡도 상으로 비효율적인 알고리즘

 

---

 

     정리

- 입력값의 크기를 통해 어느정도 시간복잡도 까지 허용되는지 추측 가능

 - 구현시 주어진 시간복잡도에 따라 자료구조/알고리즘 선택하자!!

 위의 표를 보고 알맞는 알고리즘을 선택하자.

ex) 인덱스 조회엔 vector, 원소첨삭에는 list

 

     주의

동일한 동작을 하는것처럼 보이나, 시간복잡도가 다른 경우도 존재

=> 기본 set,map vs unordered 컨테이너

=> vector와 dictionary/set에서 특정 key 존재유무 확인

=> vector와 list에서 특정위치 원소 가져오기

 

시간복잡도 확인 : https://github.com/dremdeveloper/codingtest_cpp/blob/main/performance/ReadMe.md

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################

#include <iostream>
#include <unordered_map>
#include <map>
#include <chrono>

using namespace std;
using namespace std::chrono;

// map과 unordered_map의 삽입 시간비교

//unordered_map은 해시 테이블을 기반으로 하며, 평균적으로 O(1)의 시간 복잡도를 제공한다. 그러나 최악의 경우, 모든 요소가 하나의 버킷에 모일 때 O(n)이 될 수 있다.
//map은 레드-블랙 트리(Red-Black Tree)를 기반으로 하는 균형 이진 검색 트리로, 모든 주요 연산(삽입, 삭제, 검색)에 O(log n)의 시간 복잡도가 걸린다.

// 성능 차이의 주된 이유는 다음과 같다:
// - unordered_map은 해시 함수로 구현되어있으므로 삽입/삭제시 정렬이 따로 필요없다
// - map은 항상 정렬된 상태를 유지해야 하므로 삽입과 검색이 더 오래 걸릴 수 있다.(매번 정렬해야 함)

int main() {
    const int NUM_ELEMENTS = 100000; // 원소 수

    unordered_map<int, int> unorderedMap;
    map<int, int> orderedMap;

    // unordered_map에 대한 삽입 성능 측정
    auto start = high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; i++) {
        unorderedMap[i] = i;
    }
    auto end = high_resolution_clock::now();
    auto durationUnorderedInsert = duration_cast<milliseconds>(end - start);
    cout << "Insertion into unordered_map: " << durationUnorderedInsert.count() << " ms" << endl;

    // map에 대한 삽입 성능 측정
    start = high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; i++) {
        orderedMap[i] = i;
    }
    end = high_resolution_clock::now();
    auto durationOrderedInsert = duration_cast<milliseconds>(end - start);
    cout << "Insertion into map: " << durationOrderedInsert.count() << " ms" << endl;

    // unordered_map에 대한 검색 성능 측정
    start = high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; i++) {
        auto it = unorderedMap.find(i);
    }
    end = high_resolution_clock::now();
    auto durationUnorderedSearch = duration_cast<milliseconds>(end - start);
    cout << "Search in unordered_map: " << durationUnorderedSearch.count() << " ms" << endl;

    // map에 대한 검색 성능 측정
    start = high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; i++) {
        auto it = orderedMap.find(i);
    }
    end = high_resolution_clock::now();
    auto durationOrderedSearch = duration_cast<milliseconds>(end - start);
    cout << "Search in map: " << durationOrderedSearch.count() << " ms" << endl;

    return 0;
}

 

 

문제 11 : 1,000,000이하의 자연수 이므로 이중 for문을 사용하는 시간복잡도O(N^2)는 안됨

문제 62 : 행의 크기가 10이 넘지 않으므로, 모든 시간복잡도의 연산 수행 가능 

 

 

 

 

📖 내용 요약

 

요약

1. 시간 복잡도는 주로 빅오 표기법으로 표현되며, 입력 크기에 따라 알고리즘의 성능을 예측할 수 있습니다.

 

2. 코테에서 자주 사용되는 시간 복잡도 예시로 이차원 배열, 이진 탐색 트리, 순열이 있다.

 

3. 주어진 시간 복잡도에 따라 효율좋은 적절한 컨테이너/알고리즘을 선택해야 한다. ex)set/map, 퀵정렬 등...