23.12.12 자료구조와 복잡도

1. 자료구조

    - 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합

    - C++ 은 STL 을 기반으로 전반적인 자료 구조를 가장 잘 설명 할수 있는 언어

      * STL : C++의 표준 템플릿 라이브러리이자 스택, 배열 등 데이터 구조의 함수 등을 제공하는 라이브러리 묶음

 

2. 복잡도

  1) 시간 복잡도

     (1) C++ 의 기본

           - 잠시 C++의 기본을 살펴보자

           - 아래와 같이 만들고 실행시킨 이후 wow 라고 입력하면 wow가 출력됨

           - C++은 main 함수를 중심으로 돌아가므로 main 함수 하나를 무조건 만들어야함

           - 컴파일이 시작되면 전역변수 초기화, 라이브러리 import 등의 작업이 일어나고, main 함수에 얽혀 있는

              함수들이 작동 됨

           - 이후 0을 리턴하며 프로세스 종료

           - 코드의 각부분을 설명하면 다음과 같다

           A) 헤더파일. STL 라이브러리를 import. 이 중 bits/stdc++.h는 모든 표준 라이브러리가 포함된 헤더

           B) std라는 네임스페이스를 사용한다는 뜻. cin 이나 cout 등을 사용할 때 원래는 ste::cin 처럼 네임스페이스를

               달아서 호출해야 하는데, 이를 기본적으로 설정한다는 뜻.

               참고로 네임스페이스는 같은 클래스 이름 구별, 모듈화에 쓰이는 이름을 말함

           C) 문자열을 선언. <타입> <변수명> 이렇게 선언. string 라는 타입을 가진 a라는 변수를 정의함

                예를 들어 string a = "큰돌" 이라고 하면 이때 a를 lvalue 라고 하며 큰돌을 ralue 라고 한다

                lavalue 는 추후 다시 사용할 수 있는 변수이며, rvalue 는 한 번 쓰고 다시 사용하지 않는 변수

           D) 입력. 대표적으로 cin. scanf 가있다

           E) 출력. 대표적으로 cout 와 printf 가 있다

           F) return 0 프로세서가 정상적으로 마무리됨을 뜻함

#idclude <bits/stdc++.h   // --- (A) 
using namespace std;      // --- (B) 
string a;                 // --- (C)
int main()                // --- (D)
{
	cin >> a;         // --- (E)
    cout << a << "\n";    // --- (F)
    return 0;             // --- (G)
}

 

      (2) 빅오 표기법

           - 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

           - 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는데 쓰임

           - 입력범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것

           - 가장 영향을 많이 끼치는 항의 상수 인자르 ㄹ빼고 나머지 항을 없앤 것 다른 항들이 신경 쓰일 수 있지만

              증가 속도를 고려하면 그렇지 않다

           - 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 때문에

             이것만 신경 쓰면 된다는 이론이다

           - 예) 입력크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 10n2 + n 이라고 하면 아래와 같은 코드를

                   상상할 수 있다 시간복잡도는 O(n2)

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';
}

 

      (3) 시간 복잡도의 존재이유

           - 효율적인 코드로 개선하는 데 쓰이는 척도가 된다

           - 버튼을 누르고 화면이 나타나는데 이 로직이 O(n2) 의 시간 복잡도를 가지고 9초가 걸린다고 가정했을 때

             이를 O(n) 의 시간복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 된다

 

      (4) 시간 복잡도의 속도 비교

           - O(1) 과 O(n) 은 입력 크기가 커질수록 차이가 많이 나는 것을 볼 수 있다.

           - O(n2) 은 말할 것도 없을 만큼 차이가 크다

           - 즉 O(n2) 보다는 O(n), O(n) 보다는 O(1) 을 지향해야 한다

 

  2) 공간 복잡도

      - 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양

      - 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함

      - 예) 아래 코드 처럼 되어 잇는 배열이 있다고 하면 a 배열은 1004 x 4 바이트의 크기를 가지게 되는데

              이런 공간을 말함

int a[1004];

 

  3) 자료구조에서의 시간 복잡도

      - 아래는 자주 쓰는 자료 구조의 시간 복잡도를 나타낸 모습이다

      - 보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려하면서 쓴다

자료 구조의 평균 시간 복잡도
자료구조	접근	탐색	삽입	삭제
배열 (array)	O(1)	O(n)	O(n)	O(n)
스택 (stack)	O(n)	O(n)	O(1)	O(1)
큐 (queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트   (doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블   (hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리 (BTS)	O(logn)	O(logn)	O(logn)	O(logn)
AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

자료 구조의 최악의 시간 복잡도
자료구조	접근	탐색	삽입	삭제
배열 (array)	O(1)	O(n)	O(n)	O(n)
스택 (stack)	O(n)	O(n)	O(1)	O(1)
큐 (queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트   (doubly linked list)	O(n)	O(n)	O(1)	O(1)
해시 테이블   (hash table)	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리 (BTS)	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)
레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)