4. 자료구조

4.1 복잡도 

알고리즘을 수행하면 시간과 메모리 공간 드으이 자원이 사용되며

시간 복잡도는 알고리즘의 실행 시간을 정량화하는 것

공간 복잡도: 실행하는 데 필요한 메모리 사용량을 정량화 

복잡도 표기법: 빅오 표기법 

입력 값(n)에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도를 표현

최고차항을 기준으로 표현하는 이유는 연산의 수가 극한에 수렴할 때 나머지 항이 복잡도에 미치는 영향은 미미하기 때문이다. 

 

4.2 선형 자료구조

연속적으로 데이터가 나열되는 자료구조를 나타낸다. 

배열, 리스트, 스택, 큐

 

4.2.1 배열

정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조 

각 데이터를 배열의 요소라고 하며 데이터를 가리키는 번호를 인덱스라고 한다. 

 

접근: 걸리는 시간 복잡도 O(1)

검색: 걸리는 시간 복잡도 O(n)

삽입: 걸리는 시간 복잡도 O(n)

삭제: 걸리는 시간 복잡도 O(n)

*n"은 데이터의 총 개수 또는 크기

 

4.2.2 연결 리스트

크기가 정해져있지 않은 동적 자료구조 

여러개의 노드로 구성되어 있음 - (노드: 데이터와 다음 노드가 저장된 주소 값을 가지고 있음)

헤드 포인터와 테일 포인터로 시작과 끝을 알 수 있음

 

걸리는 시간 복잡도

검색:  O(n) - 첫 번째 노드부터 하나씩 값을 확인하는 선형 탐색 

추가: 데이터를 추가하는 연산 자체 O(1)(이전 노드가 가리키는 주소 값을 변경하는 작업), / 데이터를 추가하려는 위치로 이동하기까지: O(n)

삭제: 데이터를 삭제하는 연산 자체 O(1) , 데이터를 추가하려는 위치로 이동하기까지: O(n)

 

4.2.3 스택

데이터를 쌓는 형태로 LIFO(Last In First Out) 후입선출

어떤 작업의 실행을 취소할 때, 웹 브라우저에서 뒤로가기 할 때 . 들최근에 처리한 작업들을 하나씩 꺼낼 때 사용

 

연산	설명	시간 복잡도
push	스택에 새로운 데이터 삽입	O(1)
pop	스택에서 가장 위에 있는 데이터 삭제	O(1)
peek	스택에서 가장 위에 있는 데이터 확인	O(1)
isEmpty	스택이 비어 있는지 확인	O(1)
isFull	스택이 가득 찼는지 확인	O(1)

 

 

4.2.4 큐

데이터가 순차적으로 들어오는 형태로, FIFO(First in, First Out) 선입선출

큐의 맨 앞: front, 맨 뒤: rear

운영채제에서 프로세스가 CPU를 할당받기 전가지 대기하는 준비 큐 

어떠한 작업을 처리할 때 작업 요청이 들어온 순서대로 처리하기 위해 사용 

 

연산	설명	시간 복잡도
enqueue	큐의 rear에 새로운 데이터 삽입	O(1)
dequeue	큐의 front에서 데이터 삭제	O(1)
peek	큐의 front에 있는 데이터 확인	O(1)
isEmpty	큐가 비어있는지 확인	O(1)
isFull	큐가 가득 찼는지 확인	O(1)

 

큐를 배열로 구현하면 rear 의 인덱스를 이용해 큐가 가득 찼는지 쉽게 확인할 수 있고, 인큐/디큐를 수행할 때 front나 rear 만 수정하면 된다. 하지만 데이터가 1개인 경우 rear의 인덱스를 보고 큐에 데이터가 가득 찼다고 생각할 수 있다. 

새로운 해결 방식으로 순환 큐(원형 큐)

삽입 연산을 할 때 배열의 앞부분에 데이터를 삽입하고, 배열의 시작과 끝이 구분되지 않아 삽입과 삭제를 유연하게 수행할 수 있다. 

 

**덱

양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 자료구조로 큐와 스택을 합친 형태