기술면접 대비 - 자료구조

1. 시간 복잡도와 공간복잡도 -> 알고리즘이 효율적인지를 판단하는 척도

시간복잡도

알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 표기한 것 -> 입력을 기준으로 할 때 필요한 연산의 수

공간복잡도

프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지 -> 고정공간(알고리즘과 무관한 공간), 가변공간(알고리즘과 밀접한 공간)

- 빅오 표기법 : 복잡도를 표기하는 방법 '빅오엔'

2. 스택,큐

스택

차곡차곡 쌓아 올린 형태의 자료구조, 후입선출(LIFO) 구조 -> 한 곳(TOP)을 통해서 삽입, 삭제가 이루어지는 자료구조

시간복잡도 : 삽입/삭제 O(1) - 맨 위에서 이루어지기에 , 검색 O(n) - 특정데이터를 찾을 때까지 수행함으로

큐

줄을 서서 기다리는 것, 선입선출(FIFO) 구조 -> 한쪽 끝에서는 삽입 작업, 한쪽 끝에서는 삭제 작업만 이루어지는 자료구조

시간 복잡도 : 삽입/삭제 O(1) - 삽입은 front에서만 삭제는 rear에서만 이루어져서 , 검색 O(n) - 특정데이터를 찾을 때까지 수행함으로

3. 배열, 링크드리스트

배열

입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조 -> Index를 통한 접근이 용이하다.

시간복잡도 : 검색: O(1)-원하는 인덱스를 알 때, 순차검색: O(n) 삽입/삭제 : 배열 처음, 중간 O(n), 배열의 끝 O(n)

링크드리스트

여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조 

시간복잡도 : 검색 O(n), 삽입, 삭제 처음: O(1) , 중간과 끝에는 탐색시간으로 O(n)이 추가로 발생한다.

둘의 비교

배열 : index를 통한 빠른 접근, 삽입/삭제가 오래 걸림

링크드리스트 : 처음부터 탐색을 진행해야 함, 삽입. 삭제가 용이하다.