자료구조

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합이다.

어떤 비즈니스 로직을 처리할 때 가장 효과적인 자료구조를 찾아서 쓰는 것이 중요하기 때문에 자료구조를 명확하게 알아야한다.

자료구조를 설명하기 위해 C++은 이해하기 쉬운 언어이기 때문에 자료구조 공부는 C++로 할 것이다.

1
2
3
4
5
6
7
8
#include <bits/stdc++.h> // 1
using namespace std; // 2
string a; // 3
int main(){ // 4
    cin >> a; // 5
    cout << a << '\n'; // 6
    return 0; // 7
}

  1. 헤더 파일. import할 때 사용한다. bits/stdc++.h 는 모든 표준 라이브러리를 의미한다.

  2. std라는 네임스페이스 사용하겠다. cin, cout 사용할 때 원래는 std::cin처럼 네임스페이스 달아서 사용해야하는데 이를 기본으로 설정한다는 뜻이다.

  3. 문자열 선언. <타입> <변수명> 이런식으로 선언한다. 예를들어 string a = 'Wix' 이렇게 선언했다면, a는 lvalue, Wix는 rvalue라고 한다. lvalue는 추후 다시 사용될 수 있는 변수이고 rvalue는 한 번 쓰고 다시 사용되지 않는 변수이다.

  4. 입력. 대표적으로 cin, scanf가 있다.

  5. 출력. 대표적으로 cout, printf가 있다.

  6. return 0은 프로세스가 정상적으로 마무리 됨을 뜻한다.

int는 4바이트 정수를 사용할 때 사용되는 타입이다. 표현범위는 -2,147,483,648 ~ 2,147,483,647 입니다.

시간복잡도

시간복잡도란, 입력 크기에 대해 어떤 알고리즘이 실행되는데 걸리는 시간이다. 직접적인 시간을 측정하는 것이 아닌 주요 로직의 반복횟수를 중점으로 측정된다.

왜냐하면 직접적인 시간은 여러가지 요인에 따라 변경될 수 있기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < 10; i++){
    for(int j =0; j < n; j++){
        for(int k = 0; k < n; k++){
            if(true) cout << k << '\n';
        }
    }
}

for(int i = 0; i < n; i++){
    if(true) cout << i << '\n';
    }

위 코드에서 시간 복잡도는 10n^2+n이다.

빅오표기법(Big - O)

빅오표기법은 복잡도에 영향을 가장 많이 끼치는 항의 상수인자를 제거하고 나머지 항을 없애서 복잡도를 표기하는 표기법이다.

앞선 예시를 빅오표기법으로 나타내면 O(n^2)이다.

여기서 영향을 가장 많이 끼친다는 의미는 입력 크기가 커질수록 증가속도가 가장 큰 것을 의미한다.

예를 들어 n^2은 1,4,9,16,25 이런식으로 증가하는데, n은 1,2,3,4,5 이런식을로 증가하기 때문에 영향이 가장 큰 n^2 항의 상수 인자를 제거하여 빅오표기법으로 나타낸 것이다.

빅오표기법 차트는 외워두자!

n! > 2^n > n^2 > nlogn > n > logn > 1 순입니다.

Big-O chart

상수시간 시간복잡도 O(1)

상수시간 시간 복잡도는 입력 크기와 상관없이 일정한 시간복잡도를 가지는 것을 말한다.

  1. 입력과 출력
1
cin, cout, scanf, printf
  1. 곱하기
1
a[2] *= 2;
  1. 간단한 비교 if 문
1
2
3
if (a[0] == 2) {
    // 로직
}
  1. 배열 인덱스 참조
1
2
int a[3] = {1,2,3};
int b = a[2]