알고리즘 이론 (시간복잡도 ~ 삽입정렬)

✅시간 복잡도

알고리즘 선택의 기준이 됨
 

시간 복잡도를 줄이는 방법

• 알맞은 알고리즘 사용
• 비효율적인 로직 찾아서 효율적으로 리팩토링 (ex)다중 for문)

 

✅배열과 LinkedList

• 배열은 인덱스가 있기 때문에 값에 접근하는 속도가 리스트에 비해 빠르다.
• 리스트는 포인터로 연결되어있기 때문에 데이터를 삽입하거나 삭제하는 연산 속도가 배열보다 빠르다.
• 크기 변화가 없는 데이터를 다룰때는 배열, 크기가 변하기 쉬운 데이터를 다룰때는 리스트
• 리스트는 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

 

✅구간 합

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]
 

구간 합을 구하는 공식

i~j까지의 합 → S[j] - S[i-1]
 

✅스택과 큐

스택

• LIFO(Last-in First-out), 삽입과 삭제가 한쪽에서만 일어나는 특징이 있음
  • top : 삽입과 삭제가 일어나는 위치
  • push : top 위치에 새로운 데이터를 삽입하는 연산
  • pop : top 위치의 데이터를 삭제 and 확인하는 연산
  • peek : top 위치의 데이터를 단순 확인하는 연산
• 깊이 우선 탐색, 백트래킹 종류의 코딩테스트에 효과적
• 후입선출은 개념 자체가 재귀함수 알고리즘 원리와 일맥 상통함

 

큐

• FIFO(First-in First-out), 삽입과 삭제가 양방향에서 이루어짐
  • rear : 큐에서 가장 끝(데이터가 들어오는 곳) 데이터를 가리키는 영역
  • front : 큐에서 가장 앞(데이터가 나가는 곳)의 데이터를 가리키는 영역
  • add : rear 부분에 새로운 데이터를 삽입하는 연산
  • poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • peek : 큐의 맨 앞(front)에 있는 데이터를 단순 확인하는 연산
• 너비 우선 탐색에서 자주 사용

 

✅버블정렬

• 구현방법이 가장 쉽지만 시간복잡도는 가장 높음
• n*(n-1)*/2 = (n^2-n)/2 → 상수 제외 → 시간 복잡도 O(n^2)

 

✅선택정렬

• 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것
• n*(n-1)*/2 = (n^2-n)/2 → 상수 제외 → 시간 복잡도 O(n^2)

 

✅삽입정렬

• 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것
• 인덱스 시작 번호가 0이라면 1번 인덱스부터 선택하여 앞의 인덱스 데이터(정렬된 데이터)와 비교 시작
• 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있음
• 마찬가지로 이중 for문으로 구현되므로 시간 복잡도 O(n^2)