자료구조

복잡도

시간 복잡도

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

어떠한 알고리즘의 로직이 얼만큼 걸리는지 시간을 나타내는데 쓰이며, 보통 빅오 표기법으로 나타낸다

빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다

가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항은 없앤다

n^2 + 3 -> n^2

시간 복잡도의 속도는 다음과 같다

O(n^2) > O(n) > O(logn) > O(1)

공간 복잡도

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

정적 변수, 재귀 함수 등 동적으로 공간을 필요로 하는 경우도 포함한다

선형 자료구조

자료 구조의 요소가 순차적으로 나열되어 있는 구조이다

연결 리스트

시간 복잡도

• 삽입, 삭제 : O(1)
• 탐색 : O(n)

데이터와 노드에 대한 주소를 담고 있는 노드 단위로 요소를 가지고 있다

주소를 어떻게 가지고 있는지에 따라 연결 리스트의 종류가 결정된다

싱글 연결 리스트 : 다음 노드의 주소만 가지고 있는 연결 리스트

이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있는 연결 리스트

원형 이중 연결 리스트 : 이중 연결리스트이면서 마지막 노드가 첫 번째 노드의 주소를 가지고 있는 연결 리스트

배열

같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다

정적 배열 기준 시간 복잡도

• 삽입, 삭제 : O(n)
• 탐색 : O(1)

보통 데이터 추가와 삭제를 많이 하는 것은 연결 리스트를 사용하고, 탐색을 많이 하는 것은 배열을 쓴다

벡터

동적으로 요소를 할당할 수 있는 동적 배열이다

컴파일 시점에 배열의 크기를 지정할 수 없다면 벡터를 사용해야 한다

시간 복잡도

• 탐색, 맨 뒤 요소 삭제, 삽입 : O(1)
• 맨 뒤나 앞이 아닌 요소 삽입, 삭제 : O(n)

스택

LIFO 성질을 가진다

시간복잡도

• 삽입, 삭제 : O(1)
• 탐색 : O(n)

큐

FIFO 성질을 가진다

시간복잡도

• 삽입, 삭제 : O(1)
• 탐색 : O(n)