내일배움캠프 D+109: 0803

📚 알고보면 알기쉬운 알고리즘

✳ 3주차 ❇

✔ 정렬

▶ 데이터를 순서대로 나열하는 방법

• 버블 정렬 $O(N^2)$
  자리를 바꿔가며 정렬한다.
  
• 선택 정렬 $O(N^2)$
  자리를 정해두고 그 자리에 올 원소를 찾는다.
  
• 삽입 정렬 $O(N^2)$ (최선의 경우 $O(N)$)
  특정 원소와 비교 후 삽입한다.
  
• 병합 정렬 $O(NlogN)$
  쪼개서 정렬하고 합치면서 순차 정렬한다.

✔ Stack

▶ 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조
데이터 넣고 뽑는 걸 자주하며, LinkedList와 유사하게 구현할 수 있다.

push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

✔ Queue

▶ 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조
데이터 넣고 뽑는 걸 자주하며, LinkedList와 유사하게 구현할 수 있다.

enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기

✔ Hash Table

▶ 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산
탐색을 최대한 줄여주기 위해, input에 대한 key 값을 얻어내서 관리하는 방식
데이터의 검색과 저장이 아주 빠르게 진행된다.
python에서는 dictionary로 쓰인다고 생각하면 된다.