[06JUL, 2021] TIL

코로나가 다시 심해져서 영어 스터디가 연기되었다..ㅠㅠ 오늘이 두 번째 날이었어서 아쉬웠지만 건강이 우선..! 그래서 오늘은 집콕하면서 알고리즘 강의도 듣고 문제도 푸는 날로 보냈다.📝

 

---

 

✔️ Set

프로그래머스에서 문제를 풀다 중복 값을 제거해야 했는데 나는 includes()를 이용해 풀었다. 다른 풀이 중 set을 사용한 것을 보았다. set은 Set 은 ES6에서 등장한 새로운 data object로 unique 값만 저장하도록 하기 때문에 배열에 넣으면 중복 값이 사라진다. 

const result = [...new Set(answer)];

그래서 이렇게 사용하면 중복 값을 제거할 수 있었다. const result = new Set(answer)로 배열을 set으로 변환하여 중복 값을 제거하고, Spread Operator를 이용하여 다시 배열로 만들어주었다.

 

mdn 예제:

var myArray = ['value1', 'value2', 'value3'];

// Array를 Set으로 변환하기 위해서는 정규 Set 생성자 사용
var mySet = new Set(myArray);

mySet.has('value1'); // true 반환

// set을 Array로 변환하기 위해 전개 연산자 사용함.
console.log([...mySet]); // myArray와 정확히 같은 배열을 보여줌

 

 

✔️ 선형 탐색

처음부터 마지막까지 차례대로 탐색한다. 찾고자 하는 자료가 나올 때까지 모든 자료를 확인해야 한다.

정확하지만 효율적이지 못한 방법이다. 하지만 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하기도 하다. 왜냐면 이런 경우에는 무작위로 탐색하는 것보다는 순서대로 탐색하는 것이 효율적이기 때문이다. 하지만 평균적으로 최악의 상황(찾고자 하는 요소가 맨 마지막에 있는 경우)에서 종료되는 것에 가깝기 때문에 비효율적이다.

 

 

✔️ 정렬 알고리즘

• 단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬
• 복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

 

✔️ 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 개의 자료가 차례차례 비교되면서 위치를 찾아가는 모습이 거품이 보글보글 일어나는 것처럼 보인다 하여 버블 정렬이라고 부른다고 한다.

* 서로 인접한 두 개의 요소를 비교해 위치를 교환하는 방식으로 정렬하는 방법

* 시간 복잡도: O(N^2), 정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문

* 단점: 시간 복잡도가 최악, 최선, 평균의 경우 모두 O(N^2)이어서 비효율적이다. 다른 정렬에 비해 정렬 속도가 느리다. 교환 횟수가 많다.

 

 

✔️ 선택 정렬 (Selection Sort)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 와 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬한다. 그래서 교환 횟수는 줄지만 비교하는 횟수는 증가한다. 

* 시간 복잡도: O(N^2), 정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문

 

---

 

TIL 쓰면서 느낀 점은 정렬 방법은 더 많으니까 TIL 말고 따로 한 페이지로 정리하면 좋을 것 같다!