2023-03-30 TIL

스택

한쪽 끝이 막혀 있는 통 같은 자료구조

특징

• 위에서부터 쌓이는 느낌
• 후입선출 (LIFO) : 나중에 삽입된 데이터가 먼저 나오는 자료구조

데이터 저장, 반출

스택에 데이터를 저장하는 것을 push
스택의 데이터를 빼내는 건 pop

그림 출처 : https://devuna.tistory.com/22

활용

최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때

• 매개 변수, 지역 변수
• 쌍을 맞춰서 확인할 때
• 뒤로 가기 (페이지 뒤로 가기)
• Python에서 사용할 땐 주로 리스트 사용

큐

양쪽 끝이 뚫려 있는 통 같은 자료구조

특징

• 먼저 삽입(enqueue) 된 데이터가 먼저 나옴(dequeue)
• 선입선출 자료구조 (FIFO)

그림 출처 : https://devuna.tistory.com/22

활용

데이터를 임시 저장할 때

• 버퍼(줄을 세울 때)로 활용
• 임시 저장된 데이터를 차례차례 내보내거나 꺼낼 때 (영화관 예약 인원)

변형

1. 원형 큐 : 원형으로 이루어진 큐
   넣는 부분 front 끝이 rear라고 할 때 front와 rear가 유동적으로 움직임
2. 덱
3. 우선순위 큐 : 이진트리. 우선 순위가 높은 데이터가 먼저 나가는 큐

정렬

데이터를 정해진 기준에 따라 재배치하는 것
Ex : 2 3 1 4 -> 1 2 3 4

• 다양한 정렬 알고리즘이 존재 (버블, 선택, 삽입, 퀵….)
• 정렬 알고리즘에 따라서 시간 복잡도가 다름

종류

삽입 정렬

앞에서부터 하나하나 비교해서 내 위치를 삽입하는 방식

시간 복잡도 : O(n^2)

버블 정렬

인접한 요소랑 비교해서 정렬이 제대로 되었는지 확인하며
정렬이 제대로 될 때 까지 바꿔치기 하는 방법

시간 복잡도 : O(n^2)
바꿔치기 한 횟수가 정렬 횟수

선택 정렬

요소 중 최소값을 찾아 그 값을 맨 처음 값으로 대체
맨 처음 값을 뺀 나머지 요소들이 정렬될 떄 까지 반복

시간 복잡도 : O(n^2) -> 반복문 2개

퀵 정렬

분할 정복(divide-and-conquer) 알고리즘의 일종

시간 복잡도 : O(nlogn)

방법
1. 임의의 하나의 요소를 고른다. 이를 피벗(pivot = 기준점)이라고 한다.
2. 피벗보다 작은 부분집합, 피벗보다 큰 부분집합을 선정
3. 피벗의 좌,우를 기준으로 정렬. 정렬 뒤 피벗은 더 이상 움직이지 않는다.
4. 분할된 두개의 작은 배열에 대해 재귀적으로 반복한다.

재귀에 대한 이해가 필요

어렵다...