70일차 CS50 [알고리즘1]

2021. 01. 13 목요일

여기에서 무료로 CS 강의를 들을 수 있고, 여기서 들은 것을 바탕으로 정리해보고자 한다.

CS50 강의 3일차이다. 코드스테이츠를 통해서 한 번 배워봤던 부분이라서 그런지 다시 보니까 처음 배웠을 때보다 더 이해가 잘되었다.

오늘은 알고리즘, 선형 탐색, 버블 정렬, 선택 정렬 강의를 들었다. 아래는 강의 자료를 기반으로 다시 정리해본 것이다.

생각해보기 부분은 나의 생각이므로 정답이라고 할 수는 없다.

---

1. 알고리즘

알고리즘이란?

입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야하는지에 대한 규칙들의 순서적 나열. 이러한 일련의 순서적 규칙들의 나열 방법에 따라 알고리즘의 종류가 달라지고, 같은 출력값이라도 그 값에 도달하는 시간이 서로 다를 수 있다.

정확한 알고리즘 vs 효율적인 알고리즘

전화번호부에서 Mike Smith를 찾는 알고리즘
1. 전화번호부를 집는다.
2. 첫번째 장을 펼친다.
3. 이름을 찾는다.
4. "Smith" 이름이 있으면 Mike에게 전화한다.
5. 없으면 다음 페이지로 넘긴다. 3행으로 간다.
6. 다 찾아도 없으면 포기한다.

이렇게 첫 번째 장부터 하나하나 찾아나가면 Mike Smith를 찾는데 성공할 것이다. 그런데 전화번호부가 1000장 이면 Mike Smith의 전화번호를 찾으려면 1000장을 다 넘겨야 할 수도 있다. 그래서 알고리즘은 정확성도 중요하지만, 효율성도 중요하다.

전화번호부에서 효율적으로 Mike Smith를 찾는 알고리즘
1. 전화번호부를 집는다.
2. 책의 중간을 펼친다.
3. 이름을 찾는다.
4. "Smith" 이름이 있으면 Mike에게 전화한다.
5. 지금 페이지보다 앞부분에서 "Smith"를 찾는다.
6. 지금 페이지보다 뒷부분에서 "Smith"를 찾는다.
7. 다 찾아도 없으면 포기한다.

위의 알고리즘처럼 전화번호부가 이름순으로 정렬되어 있다면 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지를 알고 있다. 그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행한다. 한 페이지가 남을 때까지 계속 수행하면 마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 것이다.

첫번째 코드에서는 최대 1000번의 탐색을 수행해야하지만, 두번째 코드에서는 최대 10번의 탐색으로 Mike Smith의 이름을 찾을 수 있게 된다.

효율성 Win!🎉

---

2. 선형 탐색

선형탐색이란?

원하는 원소가 발결될 때까지 처음부터 마지막 자료까지 차례대로 탐색하는 것이다.

선형탐색의 효율성

선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 n번만큼 실행해야 한다. 하지만 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.

정렬이 필요한 이유

선형탐색은 효율적이지 못한 방법이기 때문에 효율적인 알고리즘을 사용할 수 있도록 정렬을 해주어야 한다. 정렬은 시간이 오래 걸리고 공간을 더 차지하게 된다. 하지만 이 추가적인 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있을 것이다.

생각해보기

Q. 효율성을 높여줘야하는 이유는 무엇일까?

A. 정렬을 하면 공간을 더 차지하지만 탐색을 빠르게 할 수 있게된다. HDD와 RAM중 RAM이 더 비싸다는 것은 알고 있을 것이다. HDD 저장공간을 늘리는 데는 큰 비용이 들지 않지만 RAM 공간을 늘리려면 많은 비용이 들기 때문에 RAM 공간을 늘려도 되지않도록 효율을 높여주는 것이다.

---

3. 버블 정렬

버블 정렬이란?

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

실행

버블 정렬

[5, 1, 6, 2, 4, 3]의 배열이 있다. 이것을 버블 정렬하는 과정을 수도코드로 작성해보면 다음과 같다.

1. 5와1을 비교해서 1이 5보다 작기 때문에 두 수는 교환될 것이다.
2. 다음은 5와 6을 비교하는데 올바른 순서이기 때문에 넘어간다.
3. 6과 2를 비교해서 계속 같은 방식으로 비교해서 교환한다.

한번 정렬을 하면 1, 5, 2, 4, 3, 6의 순서로 정렬이 될 것이고, 6이 제 자리에 와 있는 것을 볼 수 있다. 즉, n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게 된다. 그렇기 때문에 다음 정렬에서는 n-1개의 원소를 정렬해 주면 된다. 위의 예시의 경우 1, 5, 2, 4, 3 으로만 수행될 것이다.

버블 정렬 코드를 직접 작성해 보았다.

const bubbleSort = (arr) => {
  for(let i = 0; i < arr.length; i++){
    let isChanged = false;
    for(let j = 0; j < arr.length - i; j++){
      if(arr[j] > arr[j + 1]){
        isChanged = true;
        let first = arr[j];
        let second = arr[j + 1];
        arr[j] = second;
        arr[j + 1] = first;
      }
    }
    if(!isChanged) break;
  }
  return arr;
}

버블 정렬은 한 번 만에 모든 원소가 정렬되는 것을 보장하지 않는다. 위의 예시 처럼 5, 1, 6, 2, 4, 3은 3번의 시도가 필요하고, 6, 5, 4, 3, 2, 1은 5번의 시도가 필요하다. 즉, n개의 요소를 정렬해 주기 위해서는 n-1번 실행해 주어야 한다. 최악의 상황인 경우 최대한의 횟수를 실행해줘야 하므로 경제적이지 못하다.

생각해보기

Q. 버블 정렬이 효율적인 경우는 어떤 경우일까?

A. 데이터의 양이 적거나, 어느 정도 정렬되어있을 때 사용하면 효율적일 것 같다. 버블 정렬의 장점이 구현하기 쉽고 단순하다는 것이다. 이러한 점을 고려했을 때 데이터의 양이 적거나, 어느 정도 정렬이 되어있다면 굳이 복잡한 방법으로 구현하기 보다는 단순한 방법으로 구현해서 효율적으로 정렬할 수 있을 거라고 생각한다.

---

4. 선택 정렬

선택 정렬이란?

가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

실행

선택 정렬

[5, 1, 6, 2, 4, 3]이란 배열이 있을 때 선택 정렬을 이용해서 정렬해줘야 한다면 수도코드를 다음과 같이 작성해볼 수 있을 것이다.

1. 가장 작은 원소를 찾기 위해 첫 번째 원소인 5를 (1, 6, 2, 4, 3)와 비교한다.
2. 1이 가장 작은 값이기 때문에 5의 위치와 교환한다.
3. 1이 정렬 되었고, [5, 6, 2, 4, 3]을 정렬 해주어야 한다.
4. 이러한 방식으로 계속해서 비교와 교환을 반복한다.

위의 그림을 보면 step5에서 우리는 정렬이 되었다는 것을 알 수 있지만 컴퓨터는 우리처럼 큰 그림을 볼 수 없다. 따라서 step6으로 넘어가서 5와 6의 크기를 비교한 후에야 알고리즘이 종료된다.

선택 정렬 코드를 직접 작성해 보았다.

const selectionSort = (arr) => {
  for(let i = 0; i < arr.length; i++){
    let indexOfmin = i;
    for(let j = i; j < arr.length; j++){
      if(arr[indexOfmin] > arr[j]) {
        indexOfmin = j;
      }
    }
    [arr[i], arr[indexOfmin]] = [arr[indexOfmin], arr[i]]
  }
  return arr;
}

선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요하다. n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적다. 하지만 한 번의 교환이 일어나기 위해서는 정렬되지 않은 모든 수와 비교하는 과정이 수행되어야 하므로, $n^2$번의 비교가 이루어진다. 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 한다.

생각해보기

Q. 선택 정렬이 버블 정렬보다 선호되는 경우는 어떤 경우인가?

A. 데이터의 양이 많을 경우 선택 정렬이 더 선호될 것이라고 생각한다. 그 이유는 데이터의 양이 적을 때 버블 정렬이 더 효율적일 수 있지만, 데이터의 양이 많아지면 정렬 횟수는 크게 차이가 안날 것이고 교환횟수가 확실히 적은 선택정렬이 더 효율적일 것이라 생각하기 때문이다.