4. 알고리즘

* 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 듣고 요약한 내용입니다. 해당 글에는 퀴즈에 대한 정답 및 풀이도 있습니다. 아직 퀴즈를 풀지 못하신 분들은 퀴즈를 풀고 난 후에 해당 포스팅을 읽으시길 바랍니다.

 

목차

1) 검색 알고리즘

2) 알고리즘 표기법

3) 선형 검색

4) 버블 정렬

5) 선택 정렬

6) 정렬 알고리즘의 실행시간

7) 재귀

8) 병합 정렬

1. 검색 알고리즘

학습목표: 주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있습니다.

 

선형 검색

- 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사합니다.

- 배열이 정렬되어 있는지 아닌지 모를 때 또는 정렬이 되어 있지 않을 때는 선형 검색이 이진 검색보다 빠릅니다.

 

For i from 0 to n-1

  If i'th element is 50
  
    Return true
    
Return false

 

이진 검색

- 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하여 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 됩니다.

 

If no items

  Return false

If middle item is 50

  Return true
  
Else if 50 < middle item

  Search left half
  
Else if 50 > middle item

  Search right half

2. 알고리즘 표기법

들어가기 전에: 아주 간단한 프로그램인 경우에는 실행 시간을 걱정할 필요가 없지만, 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 실행 시간은 매우 중요해집니다.

학습 목표: 알고리즘의 실행 시간의 상한과 하한을 표기할 수 있습니다.

 

 

- 위와 같은 그림을 공식으로 표기한 것이 Big O 표기법입니다.

- 알고리즘이 얼마나 잘 설계되어 있는지 또 코드가 얼마나 잘 구현되었는지를 일반적으로 Big O 표기법을 사용해 표현합니다.

 

- Big-O 표기법은 알고리즘이 최악의 경우에 필요한 계산수가 어느 정도 크기인지를, 대략적인 추정값을 표현합니다.

- 여기서 O는 "on the order of"의 약자로, 쉽게 생각하면 "~만큼의 정도로 커지는" 것이라고 볼 수 있습니다.

 

- O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.

- 실행 시간(러닝 타임)이란 프로그램이나 알고리즘이 동작하는데 걸리는 시간을 말합니다.

 

• O(n^2)
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

- Big O가 알고리즘 실행 시간의 상한(최악의 경우)을 나타내는 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한(최선의 경우)을 나타내는 것입니다.

- 예를 들어, 선형 검색에서는 n개의 항목이 있을 때 최대 n번의 검색을 해야 하므로 상한아 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼 수도 있으므로 하한은 Ω(1)이 됩니다.

 

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

3.선형검색

학습 목표: 주어진 배열 또는 구조체에서 선형 검색을 할 수 있습니다.

 

선형 검색

- 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색합니다.

 

효율성 그리고 비효율성

- 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다. 찾고자 하는 원소가 맨 마지막에 있거나 리스트 안에 없는 경우 효율성이 매우 떨어집니다.

- 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용합니다.

- 정렬은 시간이 오래 걸리고 공간을 더 차지합니다. 그러나 검색 전에 정렬을 하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야할 경우 시간을 단축할 수 있습니다.

 

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
  string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"}; // 와 c 언어는 배열을 이렇게 선언하는 구나
  string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};
  
  for (int i = 0; i < 4; i++)
  {
    if (strcmp(names[i], "EMMA") == 0)
    {
      printf("Found $s\n", numbers[i]);
      return 0;
    }
  }
  
  printf("Not found\n");
  return 1;
}

 

- 새로운 자료형인 구조체를 정의해서도 위 코드를 구현할 수 있습니다.

- C 언어에서 == 연산자로는 문자열 비교를 할 수 없다. 문자열을 돌면서 문자 하나하나를 비교해야 되기 때문이다.

- strcmp(string compare)함수를 사용하면 문자열 비교를 할 수 있다. 이 함수는 2개의 파라마터 즉, 비교하는 대상이 같을 때 0을 리턴한다.

- 문자열 비교후 리턴해주지 않으면 "Found", "Not Fount" 모두 출력되기 때문에 return 문을 작성해주어야 한다.

 

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
  string name;
  string number;
}
person;

int main(void)
{
  person people[4]; // people 이름을 가지고 요소가 4개인 배열이 있고, 그 안의 요소들을 person 구조체를 따른다.
  
  people[0].name = "EMMA";
  people[0].number = "617–555–0100";
  people[1].name = "RODRIGO";
  people[1].number = "617–555–0101";
  people[2].name = "BRIAN";
  people[2].number = "617–555–0102";
  people[3].name = "DAVID";
  people[3].number = "617–555–0103";

  // EMMA 검색
  for (int i = 0; i < 4; i++)
  {
    if (strcmp(people[i].name, "EMMA") == 0)
    {
      printf("Found $s\n", people[i].number);
      return 0;
    }
  }
  
  printf("Not found\n");
  return 1;
}

 

- person 이라는 이름의 구조체를 자료형으로 정의하고 person 자료형의 배열을 선언하면 그 안에 포함된 속성값은 '.'으로 연결해서 접근할 수 있습니다.

- C에서 struct 키워드는 여러가지 자료형을 담기위한 그릇입니다.

- 앞으로 이렇게 캡슐화를 하여 많은 관련 정보를 한 번에 관리할 일이 많아집니다.

4. 버블 정렬

학습 목표: 버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.

 

버블 정렬

- 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다. 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.

- 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.

 

Repeat n-1 times

  For i from 0 to n-2
  
    If i'th and i+1'th elemets out of order
    
      Swap them

 

 

- 요소가 6개(n개) 라고 했을 때, 2개씩 짝지어서 비교를 하기 때문에 비교하는 것을 5번(n-1번) 반복합니다.

- 인덱스가 0부터 시작한다고 했을 때 인덱스는 n-2 까지 순회합니다. 왜? 인덱스가 0부터 시작하고 n-2번째 인덱스에 있는 값과 그 다음값(n-1 번째에 있는 값, 마지막 값)을 비교할 수 있기 때문입니다.

- 즉, 중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 n-1번, n-2번 반복되므로 (n-1) * (n-1) = n² - 2n + 1 번의 비교 및 교환이 필요합니다.

- 여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.

- 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 됩니다.

 

• O(n^2) - 버블 정렬
• O(n log n)
• O(n) - 선형 검색
• O(log n) - 이진 검색
• O(1)

- 버블 정렬을 사용하면, 선형 탐색이나 이진 탐색보다 더 시간이 많이 듭니다.

- 정렬이 이미 되어 있더라도 버블 정렬을 하게 되면 맹복적으로 다시 비교하게 됩니다. 따라서 하한선 또한 Ω(n^2) 입니다.

- 버블 정렬이 효율적으로 사용할 수 있는 경우라면 데이터의 양이 적을 때이며, 이미 비교할 요소들이 정렬되어 있다고 하더라도 처음부터 비교를 하기 때문에 정렬된 데이터에 버블 정렬은 비효율적입니다.

5. 선택 정렬

학습 목표: 선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.

 

선택 정렬

- 보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.

- 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다. 

- 선택 정렬은 교환 횟수를 최소화 하는 반면 각 자료를 비교하는 횟수는 증가합니다.

 

예시)

다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.

 

6 3 8 5 2 7 4 1

 

먼저 아래 숫자들 중에서 가장 작은 값을 찾습니다.

 

6 3 8 5 2 7 4 1

 

가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환합니다.

 

1 3 8 5 2 7 4 6

 

그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾습니다.

 

1 3 8 5 2 7 4 6

 

가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환합니다.

 

1 2 8 5 3 7 4 6

 

이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료됩니다.

 

1 2 3 4 5 6 7 8

 

For i from 0 to n-1

  Find smallest item between i'th item and last item
  
  Swap smallest item with i'th item

 

- 여기서도 두 번의 루프를 돌아야 합니다.

- 바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 합니다.

- 따라서 소요 시간의 상한은 O(n^2)이 됩니다. 하한도 마찬가지로 Ω(n^2) 입니다. 버블 정렬과 동일합니다. 

 

6. 정렬 알고리즘의 실행시간

학습 목표: 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있습니다.

 

실행시간의 상한

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

 

실행시간의 하한

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

 

- 정렬이 모두 되어 있는 숫자 리스트로 버블 정렬을 한다고 가정했을 때, 원래 버블 정렬 (의사) 코드를

 

Repeat n-1 times

  For i from 0 to n-2
  
    If i'th and i+1'th elements out of order
    
      Swap them

 

- 다음과 같이 교환이 일어나지 않을 때까지 수행하도록 루프 조건을 재정의한다면

 

Repeat until no swaps

  For i from 0 to n-2
  
    If i'th and i+1'th elements out of order
    
      Swap them

 

- 최종적으로 버블 정렬의 하한은 Ω(n)이 됩니다. 상황에 따라서는 선택 정렬보다 더 빠른 방법이 될 수 있습니다.

 

실행시간의 하한

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

7. 재귀

학습 목표: 함수를 재귀적으로 사용하는 코드를 작성할 수 있습니다.

 

재귀

- 함수가 본인 스스로를 호출해서 사용하는 것을 재귀(Recursion)라고 합니다.

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
  // 사용자로부터 피라미드의 높이를 입력받아 저장
  int height = get_int("Height: ");
  
  // 피라미드 그리기
  draw(height);
}

void draw(int h)
{
  // 높이가 h인 피라미드 그리기
  for (int i = 1; i <= h; i++)
  {
    for (int j = 1; j <= i; j++)
    {
      printf("#");
    }
    printf("\n");
  }
}

 

- 위 코드는 아래와 같이 수정할 수 있습니다.

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
  int height = get_int("Height: ");
  
  draw(height);
}

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");
}

 

8. 병합 정렬

학습 목표: 재귀를 활용한 병합 정렬을 구할 수 있습니다.

 

- 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있습니다.

- 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.

 

마찬가지로 다음 숫자들을 오름차순으로 정렬해 보겠습니다.

 

7 4 5 2 6 3 8 1

 

먼저 숫자들을 반으로 나눕니다.

 

7 4 5 2 | 6 3 8 1

 

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠봅니다.

 

7 4 | 5 2 | 6 3 8 1

 

마지막으로 한 번 더 나눠봅니다.

 

7 | 4 | 5 2 | 6 3 8 1

 

이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합합니다.

단, 이 때 작은 숫자가 먼저 오도록 합니다. 4와 7의 순서를 바꿔서 병합하는 것이죠.

 

4 7 | 5 2 | 6 3 8 1

 

마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있습니다.

 

4 7 | 2 5 | 6 3 8 1

 

그럼 이제 4 7과 2 5 두 개의 부분들을 병합하겠습니다.

각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져옵니다.

즉, 4와 2를 먼저 비교해서 2를 가져옵니다. 그 후에 4와 5를 비교해서 4를 가져옵니다.

그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져옵니다.

 

2 4 5 7 | 6 3 8 1

 

이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거칩니다. 

 

2 4 5 7 | 1 3 6 8

 

마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합합니다.

2와 1을 비교하고, 1을 가져옵니다. 2와 3을 비교하고, 2를 가져옵니다. 4와 3을 비교하고, 3을 가져옵니다.

4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료됩니다.

 

1 2 3 4 5 6 7 8

 

- 볍합 정렬 실행 시간의 상한은 O(n log n)입니다.

- 숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.

- 실행 시간의 하한도 Ω(n log n) 입니다. 숫자들이 이미 정렬되었는지 여부에 관계없이 나누고 병합하는 과정이 필요하기 때문입니다.

 

병합 정렬의 장점

속도가 훨신 빨라진다. 

선택 정렬과 버블 정렬의 실행시간 상한은 O(n^2) 이고 실행시간 하한은 Ω(n^2) 이다. 

이에반해 병합 정렬의 실행시간 상한과 하한은 동일하게  O(log n), Ω(n log n)으로 상한, 하한 모두 더 빠르다.  

(단, 정렬이 되어있을 때는  버블 정렬의 하한이 제일 빠르다)

 

단점 

정렬하면서 추가 배열이 필요하기 때문에 메모리 사용량이 증가할 수 있다. 

선택 정렬보다 직관성이 떨어진다.  

 

퀴즈

1. 알고리즘의 성능 및 시간 복잡도를 표현하는 표기법 중 하나로, 최악의 경우일때(상한)를 나타내는 것은 다음 중 무엇인가요?

O()

 

2. 새로운 자료형을 구조체로 정의하고자 할때 알맞은 코드는?

typedef struct

 

3. 전화번호부 책에서 '이펭수'를 찾는 작업을 선형 검색으로 수행하게 될 경우 Big-O 는 어떻게 될까요?

O(n)

 

4. 5 6 7 3 2 과 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 버블 정렬을 왼쪽 처음부터 오른쪽 끝까지 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

5 6 3 2 7

 

5. 5 6 7 3 2 와 같은 숫자 리스트가 주어졌습니다. 오름차순 정렬을 위해 선택 정렬을 통해 교환을 ‘한 번’ 수행했을 때의 리스트는 어떻게 될까요?

2 6 7 3 5

 

6. 선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요? (단, 하한이 같은 경우 상한이 빠른 순으로 나열합니다)

이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬

 

7. 아래 코드는 '#'으로 피라미드를 쌓는 코드입니다. draw()와 같이 함수 안에서 함수 자기 자신을 호출하는 방식을 무엇이라고 할까요?

재귀

 

9. 병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?

버블 정렬 - 병합 정렬 - 선택 정렬

 

10. 알고리즘의 실행 시간의 상한을 비교하기 위해 Big-O 표기법을 사용합니다. 다음 Big-O 표기법 중 빠른 순서대로 올바르게 정렬한 것은 무엇인가요?

O(1) – O(log n) – O(n) – O(n^2)