부스트코딩 뉴비챌린지 스터디 4주차 : 알고리즘

검색 알고리즘

👉 선형 검색 (linear search)

- 배열 인덱스를 처음부터 끝까지 순서대로 확인하는 방법

 

👉 이진 검색 (binary search)

- 배열을 조건에 따라 절반으로 나누면서 확인하는 방법

 

정렬 알고리즘

👉 버블 정렬 (bubble sort)

- 인접한 두개의 값을 비교하며 정렬하는 방식

- 이미 정렬된 배열이 들어와도 하나씩 순서를 확인하는 작업을 해야하는 건 변함없기 때문에 

버블 정렬의 하한선은 Ω (n)

 

👉 선택 정렬 (selection sort)

- 배열 안의 가장 작은 값을 찾아서 첫 번째 위치와 교환하는 방식의 정렬 방법

 

👉  병합 정렬  (merge sort) 

 

🚩 병합 정렬의 3 step

1. 왼쪽 배열 정렬

2. 오른쪽 배열 정렬

3. 왼쪽 오른쪽 배열을 하나로 합친다

 

이게 무슨 소리냐면.. 일단 그룹을 다 나눠줘야 한다.

 

 

이런 숫자의 배열이 있다고 했을때 먼저 그룹을 반으로 쪼갠다

 

 

그러면 왼쪽엔 7452 오른쪽엔 6381이 남게 된다. 왼쪽을 반으로 또 쪼개준다.

 

 

이번에는 왼쪽은 74 오른쪽에는 52가 있는 게 된다. 왼쪽을 한 번 더 반으로 나눈다.

 

이제 왼쪽을 다 쪼갰다. 여기서부터 정렬이 시작된다.

위에서 병렬의 3 step에서 왼쪽 오른쪽을 정렬하고 마지막에 하나로 합친다고 했다.

7과 4 하나씩만 남은 상황에서는 따로 정렬할 필요가 없으므로 배열을 하나로 합친다.

 

4와 7을 하나로 합치면서 오름차순으로 정렬했다.

이 때는 왼쪽은 4 7 , 오른쪽은 5 2가 된다. 왼쪽은 정렬됐지만 오른쪽은 정렬이 안됐으니 정렬해준다.

 

이제 왼쪽, 오른쪽 모두 정렬이 되었다. 다음 스텝은 뭐다? 하나로 합친다!

 

 

하나로 합칠때 작은 숫자들끼리 먼저 비교를 한다.

먼저 4와 2를 비교 → 더 작은 2를 제일 처음에 다음 자리에 4가 오게 함 → 7과 5를 비교해서 5를 가져오고 남은 7을 가져옴

 

남은 오른쪽 숫자 4개도 동일한 과정을 거친 후, 왼쪽 4개와 오른쪽 4개를 병합하면 아래와 같이 된다.

 

 

장점

- 최악의 경우 가장 빠르게 정렬함

단점

- 최선의 경우에도 동일한 과정을 반복해야하므로 시간을 낭비함

 

상한선을 개선하고 싶다면 하한선을 희생해야 할지도.. 

 

 

알고리즘 표기법 : 알고리즘의 효율을 파악하는 척도

👉 Big-O 표기법

- 알고리즘의 실행 시간의 상한(최댓값)을 나타내는 방법

- 컴퓨터과학에서 몇 번의 계산 과정이 필요한지 표기하는 방법

 

- O(n)과 O(n/2)는 x값이 엄청나게 커지면 결국에는 같아지기 때문에 같은 값으로 취급함

- O(log n)도 밑의 수가 무엇인지는 중요하지 않기 때문에 그냥 log n으로 씀

 

👉 Big Ω 표기법

- 알고리즘의 실행시간의 최솟값 같은 개념 (실행시간의 하한을 나타냄)

- 운이 좋아서 한 번에 값을 발견할 수 있는 것들(선형 탐색, 이진 탐색)은 Ω (1)임 

 

👉 알고리즘의 실행 시간

 

개발자들은 최악의 경우를 생각해야하기 때문에 실행시간의 상한이 낮은 게 좋은 프로그램 

 

👉 실행 시간의 상한

 

O(n^2)	선택 정렬, 버블 정렬
O(n logn)	병합 정렬
O(n)	선형 검색
O(log n)	이진 검색
O(1)

 

👉 실행 시간의 하한

 

Ω(n^2)	선택 정렬, 버블 정렬
Ω(n logn)	병합 정렬
Ω(n)
Ω(log n)
Ω(1)	선형 검색, 이진 검색

 

👉 Theta (Θ) 표기법

- 어떤 알고리즘의 상한선과 하한선이 같을 때 사용 

 

Θ (n^2)	선택 정렬
Θ (n log n)	병렬 정렬

 

 

💡 재귀 (Recrusion)

 

👉 재귀 함수는 자기 자신을 호출한다. 쉽게 말하면 함수 안에서 또 함수 본인을 호출하는 것!

 어떤 조건에 걸릴 때까지 호출이 반복되며 루프를 형성할 것이고 for문 같은 반복문을 이용하는 대신 재귀 함수를 이용할 수 있다.

 

⚠ 프로그래머 유우머 ⚠ 구글에 recursion(재귀)을 검색하면 나오는 화면 🤣