Today I Learned(TIL) 21.07.22

오늘 공부한 것

• 모두를 위한 컴퓨터 과학(CS50 2019) 챕터4 알고리즘
  

오늘 배운 것

• 선형 검색
  • 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사.
  • 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용.
• 이진 검색 : 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복. (정렬이 되어있어야 함)

• 알고리즘 표기법(Big O)
• O = on the order of "~만큼의 정도로 커지는"
  이미지출처: boostcourse cs50
• 알고리즘 실행 시간의 상한
  - O(n^2): 선택 정렬, 버블 정렬
  - O(n log n)
  - O(n) - 선형 검색
  - O(log n) - 이진 검색
  - O(1)
• 알고리즘 실행 시간의 하한
  - Ω(n^2): 선택 정렬, 버블 정렬
  - Ω(n log n)
  - Ω(n) - 배열 안에 존재하는 값의 개수 세기
  - Ω(log n)
  - Ω(1) - 선형 검색, 이진 검색
• 실행시간의 상한이 낮은 알고리즘이 더 좋을까, 하한이 낮은 알고리즘이 더 좋을까?
  • 최악의 상황을 고려해야하기 때문에 상한이 낮은 알고리즘이 더 좋다.

• 버블 정렬
  • 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬.
  • 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있음.
  • 버블 정렬이 효율적인 경우는 데이터양이 적거나 정렬되어 있지 않은 경우.
  • 버블 정렬이 비효율적인 경우는 데이터양이 크거나 이미 정렬된 자료일 경우.

    만약 정렬이 모두 되어있는 숫자 리스트가 주어진다면,
    최종적으로 버블 정렬의 실행시간 하한은 Ω(n)이 된다.

• 선택 정렬
  • 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬.
  • 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가.
• 선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까?
  • 이중 선택 정렬(Double Selection Sort) : 한 번 탐색할 때 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고 최댓값은 끝과 바꾼 다음, 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식으로 반복 횟수가 반으로 줄어든다.
• 재귀(Recursion)
  • 함수가 본인 스스로를 호출해서 사용.

    void draw(int h)
    {
       // 높이가 0이라면 (그릴 필요가 없다면)
       if (h == 0)
       {
           return;
       }
    
       // 높이가 h-1인 피라미드 그리기
       draw(h - 1);
    
       // 피라미드에서 폭이 h인 한 층 그리기
       for (int i = 0; i < h; i++)
       {
           printf("#");
       }
       printf("\n");
    }

• 병합 정렬
  • 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식으로 이 과정은 재귀적으로 구현된다.
  • 배열을 분할하는 과정에서 메모리 사용량이 증가하고 어느 정도 정렬된 상황에서는 효율성이 떨어짐.

---

월요일에 할 일

• 모두를 위한 컴퓨터 과학(CS50 2019) 챕터5 메모리