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

1. 시간 복잡도

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

실행 후 wow라고 입력하면 wow가 출력 됩니다.
C++은 main 함수를 중심으로 돌아가므로 main 함수 하나를 무조건 만들어야 합니다. 이후 컴파일이 시작되면 전역변수 초기화, 라이브러리 import 등의 작업이 일어나고, main 함수에 얽혀 있는 함수들이 작동됩니다. 그러고 나서 main 함수가 0을 리턴하며 프로세스가 종료됩니다.

각 부분을 설명하면

1. 해더 파일. STL 라이브러리를 import한다. 이 중 bits/stdc++.h는 모든 표준 라이브러리가 표함된 헤더이다.
2. std라는 네임스페이스를 사용한다는 뜻. cin이나 cout 등을 사용할 때 원래는 std::cin 처럼 네임스페이스를 달아서 호출해야 하는데, 이를 기본으로 설정한다는 뜻.
   참고로 네임스페이스는 같은 클래스 이름 구별, 모듈화에 쓰이는 이름을 말한다.
3. 문자열을 선언함. <타입><변수명>. string이라는 타입을 가진 a라는 변수를 정의함.
   string a = "큰 돌"
   -a는 lvalue로 다시 사용 될 수 있는 변수
   -큰돌은 rvalue로 한 번 쓰는 변수
4. 입력. 대표적으로 cin, scanf
5. 출력. 대표적으로 cout, printf
6. 프로세스가 정상적으로 마무리됨을 뜻함.

1.1 시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
알고르즘 로직이 얼마나 오랜 시간이 걸리는지 나타냄.

빅오 표기법

10n²+n => O(n²)

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

입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것.
'가장 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앤 것.

시간 복잡도의 존재 이유

효율적인 코드로 개선하는데 쓰이는 척도가 된다.
버튼을 누르고 화면이 나타는데 이 로직이 O(n²)의 시간 복잡도를 가지고 9초가 걸린다고 가정하자. 이를 O(n)의 시간 복잡도를 가지는 알고르즘으로 개선한다면 3초가 걸리게 된다.
O(1)을 지향해야 한다.

1.2 공간 복잡도