자료구조란?
어떠한 구조로 데이터를 다룰 것인지!
시간 복잡도
- 입력의 크기에 따른 프로그램 실행 시간의 관계
- 표기법: 빅 오 표기법, 빅 세타 표기법, 빅 오메가 표기법
더보기
빅 오 표기법: 함수의 점근적 상한 표기
빅 세타 표기법: 입력에 대한 평균적인 실행 시간
빅 오메가 표기법: 입력에 대한 실행 시간의 점근적 하한
- 빅 오 표기법: 최고차항의 차수만 고려한다.
공간 복잡도
- 프로그램 실행시 필요한 메모리 자원의 양 (즉, 메모리 사용량의 척도)
배열과 연결 리스트
배열 (Array)
- 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
- 0부터 시작하는 고유 번호, 인덱스가 매겨짐.
- 인덱스를 통해 요소에 접근 or 수정하는 시간은 요소 개수와 무관하게 일정. 즉, O(1)
- 앞부터 차례대로 특정 요소가 있는지 찾는 연산: O(n)
- 특정 요소를 추가하거나 삭제하는 경우: O(n) (중간 변동으로 인해 이후의 요소들 이동)
정적 배열(static array)
프로그램 실행 전에 크기가 고정되어 있는 배열
동적 배열(dynamic array)
실행 과정에서 크기가 변할 수 있는 배열
연결 리스트 (Linked List)
- 노드의 모음으로 구성된 자료구조
- 연결 리스트(linked list)에서 말하는 노드란?
- "저장하고자 하는 데이터(들)" + "다음 노드의 위치(메모리상의 주소) 정보"를 포함하는 구성 단위
- 특정 노드에 접근할 수 있다면, 다음 노드의 위치도 알 수 있으므로 자연스럽게 다음 노드 데이터에도 접근 가능하다.
- 첫 번째 노드는 헤드, 마지막 노드는 꼬리.
노드는 메모리 내에 반드시 순차적으로 저장될 필요 없으므로,
연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용하다.
- 연결 리스트에서 특정 요소에 접근시: O(n) -> 앞에서부터 순차적으로 접근할 수밖에 없으므로
- 중간에 요소를 추가 or 삭제시, 재정렬이 불필요하므로: O(1)
싱글 연결 리스트
- 한 쪽 방향으로 꼬리에 꼬리를 무는 형태
- 다음 노드의 위치만 알 수 있고, 이전 노드의 위치 알기 어려움. 즉, 단방향 탐색만 가능.
이중 연결 리스트
- 다음뿐만 아니라 이전 노드 위치까지 포함. 양방향 탐색도 가능.
- BUT, 2개 위치 정보 저장하는 만큼 저장 공간이 더 필요함.
환형 연결 리스트 (원형 연결 리스트)
- 꼬리 노드(마지막)가 헤드 노드(첫번째)를 가리켜, 원형으로 구성됨.
- 물론 이중 연결 리스트로도 환형 연결 리스트를 구현할 수 있다.
스택과 큐
스택 (Stack)
- 한 쪽에서만 데이터의 삽입 및 삭제가 가능한 자료구조. 후입선출(LIFO)
- 저장은 push, 빼내기는 pop
1번 상황: 최근에 임시 저장한 데이터를 먼저 활용해야 할 때
2번 상황: 뒤로가기 기능 만들고 싶을 때
1번 상황
대표적인 상황: 함수의 매개변수를 저장하기 위해 스택을 사용하는 경우
-> 최근에 호출된 함수의 매개변수가 가장 먼저 활용되고, 가장 먼저 메모리에서 삭제됨.
큐 (Queue)
- 한 쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제. 선입선출(FIFO)
- 데이터 삽입은 enqueue, 데이터 빼내는 것은 dequeue
- 임시 저장된 데이터를 차례차례 내보내거나 꺼내 와야 하는 각종 buffer로도 활용
원형 큐 (circular queue)
- 데이터 삽입하는 쪽과 삭제하는 쪽, 양쪽을 하나로 연결해 원형으로 사용
덱 (deque)
- 양방향 큐(double-ended queue)의 약자. 양쪽으로 데이터를 삽입/삭제 가능
우선순위 큐 (priority queue)
- 지정된 요소들이 선입선출로 처리되지 아니하고, 정해진 우선순위가 높은 순으로 처리되는 큐
- 힙(heap)이라는 자료구조 기반으로 구현