[TIL] 프론트엔드 Day 5

공부한 내용

1. 정렬 알고리즘

1. 버블 정렬
   처음부터 끝까지 배열을 순회하며 이웃한 두 원소를 비교한다. 만약 두 원소의 우선순위가 반대라면, 둘의 위치를 변경한다. 한번 순회할 때 마다 우선순위가 가장 낮은 원소가 배열의 가장 뒤에 위치하게 된다. 이 동작을 모든 원소가 우선순위순으로 정렬된다. 별도의 공간을 사용하지 않지만 시간 복잡도가 $O(n^2)$이다.

   ex)
   1번째 순회: 2, 4, 1, 3 => 2, 1, 4, 3 => 2, 1, 3, 4
   2번째 순회: 2, 1, 3, 4 => 1, 2, 3, 4

2. 선택 정렬
   버블 정렬과 비슷하며 복잡도 또한 버블 정렬과 동일한 $O(n^2)$이지만 자리바꿈이 적어 더 빠르다. 배열을 모두 순회하여 가장 우선순위가 높은 원소의 위치를 찾아내고, 그 위치의 원소를 가장 앞의 원소와 바꾼다. 그리고 가장 앞의 원소를 제외하고 위의 동작을 반복한다.

   ex)
   2, 4, 1, 3 => 1, 4, 2, 3 => 1, 2, 4, 3 => 1, 2, 3, 4

3. 삽입 정렬
   두 번째 원소부터 자신보다 우선순위가 큰 원소가 나올 때까지 앞으로 이동한다. 큰 원소를 발견하면 그 원소의 바로 뒤에 삽입한다.

   ex)
   2, 4, 1, 3 => 2, 4, 1, 3
   (2가 4보다 우선순위가 크므로 4를 2의 뒤에 삽입한다.)
   2, 4, 1, 3 => 1, 2, 4, 3
   (1보다 우선순위가 큰 원소가 없다, 맨 앞에 삽입한다.)
   1, 2, 4, 3 => 1, 2, 3, 4
   (3은 자신보다 우선순위가 큰 2의 뒤에 삽입한다.)

4. 합병 정렬
   분할 정복 알고리즘을 이용한 정렬이다. 모든 원소를 나눌 수 없을 때까지 반으로 나누고 나누어진 작은 원소들을 합병하며 정렬한다. 합병하는 동작은 선형시간 $O(n)$이 걸리며 이 동작을 $log{n}$반복해서 시간 복잡도는 $O(nlogn)$이다.

5. 퀵 정렬
   임의의 원소를 골라 기준(pivot)으로 정한다. 해당 원소보다 우선순위가 낮은 그룹과 높은 그룹으로 나눈다. 나누어진 두 그룹에서도 동일하게 기준을 정하고 두 그룹으로 나눈다. 이를 반복하면 정렬이 완료된다. 퀵 정렬은 일반적으로 $O(nlogn)$의 시간복잡도를 가지지만, 최악의 경우엔 시간복잡도가 $O(n^2)$이 된다.

   ex1) 가장 앞의 원소를 기준으로 할 때,
   5, 9, 1, 3, 7, 2, 4, 8, 6
   1, 3, 2, 4 | 5 | 9, 7, 8, 6 <5가 기준>
   ( | 1 | 3, 2, 4 ) | 5 | ( 7, 8, 6 | 9 | ) , <양 옆으로 1과 9가 기준>
   ( | 1 | ( 2 | 3 | 4 ) ) | 5 | ( ( 6 | 7 | 8 ) | 9 | ), <3과 7이 기준, 정렬 완료>
   
   ex2) 최악의 경우 $O(n^2)$
   9, 8, 7, 6, 5, 4, 3, 2, 1
   | 9 | 8, 7, 6, 5, 4, 3, 2, 1
   | 9 | | 8 | 7, 6, 5, 4, 3, 2, 1
   | 9 | | 8 | | 7 | 6, 5, 4, 3, 2, 1
   $...$

6. 힙 정렬
   앞서 배운 힙 자료구조를 이용한 정렬. 우선순위가 가장 높은 원소를 루트로 두는 힙을 이용해 정렬할 원소를 모두 힙에 집어넣고 루트를 계속해서 꺼내주면 정렬이 완료된다. $O(nlogn)$의 시간복잡도를 가진다.

2. 이진탐색

분할 정복 알고리즘을 따른 탐색방법. 일상 생활에서 업다운 게임을 생각하면 편하다. 1부터 100까지의 숫자로 업다운 게임을 한다고 상상해보자. 아마 대부분의 사람들은 처음 질문에서 확실하게 절반의 선택지를 제외할 수 있는 50을 고를 것이다. 이와 같은 방법을 이용해 빠르게 탐색하는 값을 찾는 것이 이진 탐색 알고리즘이다.

• 이진 탐색 트리
  위에 설명한 이진 탐색을 트리에 적용시킨 자료구조이다. 모든 노드가 최대 2개의 자식노드를 가지며, 왼쪽의 자식노드의 값은 부모노드의 값보다 항상 작으며, 오른쪽의 자식노드의 값은 부모노드의 값보다 항상 크다는 규칙으로 노드를 유지한다.

3. 제너레이터

이터러블이자 이터레이터인 값(Well-formed Iterator)을 반환하는 함수를 제너레이터라고 부른다.

 fucntion *name(param) {
 	yield value1;
	yield value2;
	yield value3;
    return returnValue;
 }

위와 같이 일반적인 함수명 앞에 $*$를 붙여 선언하며, next()로 반환할 값들을 yield 명령어를 이용해서 선언해준다. return 값이 존재하지만 이터레이터를 이용한 순회를 할 때는 return값은 거치지 않는다. yeild 명령어는 loop내에서도 이용이 가능하며, 해당 loop가 무한루프여도 값을 미리 계산하지 않기 때문에 메모리 문제는 발생하지 않는다.

---

다시 볼 내용

제너레이터

---

느낀점

강의를 조금씩 미리 듣다보니 금요일 공부량이 약간 적었다. 하지만 그 시간만큼 과제에 집중 할 수 있어서 좋았다. 데브코스 첫주는 이렇게 하루도 빠짐없이 출석하고, 학습 기록을 남기게되어 의미있었다고 되돌아본다. 이런 열정이 식지않고 끝까지 노력할 수 있는 내가 되고싶다. 화이팅!

---

Reference

프로그래머스 프론트엔드 데브코스