C++ Week 4

시간 초과를 만나서 '시간복잡도' 생각을 하게 됐다. 간단한 개념만 알고 그냥 넘겼는데 필요하니까 찾게 됐다.

Study

알고리즘 1문제

---

Today I Learned

---

1. std::set

Overview

#include <set>

std::set<int> mySet;

std::set은 std::vector과 다르게 insert를 씀.
std::set은 자동정렬 + 중복 제거를 한다. 그래서 그냥 뒤에다 넣는 push_back이 아니라 자리를 찾아서 넣는 insert를 쓴다

set의 구조

일단 set의 시간복잡도는 logN이다.
set의 내부 구조를 알아야 하는데 set은 내부적으로 이진 탐색 트리(Binary Search Tree) 로 만들어져 있다.
여기서 트리란?

	    5
       / \
      3   7
     / \ / \
    2  4 6  8

여기서 6을 찾는다고 하면 —
5에서 시작 → 6은 5보다 크니까 오른쪽(7)으로
7에서 시작 → 6은 7보다 작으니까 왼쪽(6)으로
찾음.

8개짜리 트리에서 3번만에 찾았으니 log₂8 = 3

insert도 찾는 과정이 log N번

알고리즘 문제에서 계속 시간초과가 나서 뭐가 문제인지 다 하나하나 바꿔봤는데,
3가지가 문제였음 std::endl;, std::find, vector

---

2. endl, find, vector 시간 초과에 가장 큰 기여를 한게 뭘까?

Problem

1. vector 사이즈 미할당
2. 배열.find(); 대신 auto it = std::find() 사용
3. "\n"; 대신 std::endl; 사용
   이 세개를 고치니까 시간 초과가 해결 됐는데

어떤게 가장 큰 기여를 했으며, 앞으로 가장 신경 쓰면서 사용해야 될게 뭔지 궁금해졌다.

Solution

정답은

1. 배열.find(); 대신 auto it = std::find() 사용
   
   
2. "\n"; 대신 std::endl; 사용
   
   
3. vector 사이즈 미할당

1위 auto it = std::find(mySet.begin(), mySet.end(), num);

std::find()는 처음부터 끝까지 하나씩 뒤지는 O(N)이다.

mySet.find()는 set 내부 구조를 활용해 찾아, O(logN)임.

N과 M이 각각 최대 100,000이면
std::find()는 100,000 x 100,000 = 10,000,000,000번 연산
-> 시간초과 발생

2위 std::endl

std::endl; -> 택배가 올때마다 배달

"\n"; -> 택배를 모아서 한번에 배달

매번 출력할 떄마다 버퍼를 강제로 비우는 std::endl;는 M이 100,00이면,
100,000번 버퍼를 비우는 것.

3위 vector 사이즈 미할당

계속 TIL에 적었다시피 vector의 사이즈는 그냥 늘어나는게 아니라,
capacity가 원래값의 2배만큼의 메모리를 새로 만들어서 이사를 함.
이사 횟수는 log N 수준이지만 데이터가 클수록 티가 난다.

---

개념 정리

	- std::set<int> mySet; = 정렬, 중복없음.
    	1) mySet.insert(); 로 값을 지정해서 넣음
    - std::find, mySet.find(); = std::set의 내부 구조를 따라 가기 때문에 .find() 값이 쌈
    - \n 사용해라