[자료구조]
자료 구조(Data Structure)는 효율적으로 데이터를 관리하고 수정, 삭제 , 탐색 , 저장할 수 있는 데이터 집합을 말합니다.
c++ 는 STL을 기반으로 전반적인 자료 구조를 가장 잘 설명할 수 있는 언어미ㅕ, 이를 기반으로 자료 구조에 대한 참고 코드를 제공합니다.
- STL : C++의 표준 템플릿 라이브러리이자 스택, 배열 등 데이터 구조의 함수 등을 제공하는 라이브러리의 묶음
C++ 의 기본
시간 복잡도를 알아보기 전, 잠시 C++의 기본을 살펴보고 갑시다. 먼저 입력받은 문자열을 출력하는 프로그램을 하나 만들어 보겠습니다.
[빅오표기법, 시간복잡도와 공간복잡도]
빅오 표기법
시간 복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 가리킵니다.어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타냅니다.
빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것인데, 앞서 말한 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(N^2)
이 됩니다.
'가장 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앤 것이죠
다른 항들이 신경 쓰일 수도 있찌만 증가 속도를 고려한다면 그렇지 않습니다.
입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 때문에 이것만 신경 쓰면 된다는 이론입니다.
시간 복잡도의 존재 이유
이 시간 복잡도는 왜 필요할까요?
바로 효율적인 코드로 개선하는 데 쓰이는 척도가 됩니다.
버튼을 누르고 화면이 나타나는데 이 로직이 O(N^2)의 시간 복잡도를 가지고 9초가 걸린다고 해봅시다. 이를 O(N)의 시간복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 되겠죠?
공간 복잡도
공간 복잡도는 프로그램을 실행 시켰을 때 필요로 하는 자원 공간의 양을 말합니다. 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함합니다.
