[컴퓨터알고리즘] Ch.1 알고리즘의 첫걸음

사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.

🧐 알고리즘

• 9세기경 페르시아 수학자인 알코리즈미의 이름으로부터 유래
• 최초의 알고리즘: BC 300년경 유클리드의 GCD 알고리즘
• 문제를 해결하기 위한 단계적인 절차를 의미
  • 단계적인 절차를 따라하면 주어진 문제의 해를 찾음(요리법과 유사)
• 효율적인 알고리즘 고안이 중요
  • 주어진 문제에 대해 여러 종류의 알고리즘이 있을 수 있으나, 항상 보다 효율적인 알고리즘을 고안하는 것이 매우 중요
    
    

🧐 1.1 최대 숫자 찾기

❓ 문제

카드놀이 중에서 아주 간단한 가장 큰 숫자 찾기를 생각해보자. 카드 10장이 바닥에 펼쳐져 있다.

45, 60, 90, 75, 20, 55, 85, 35, 10, 25

가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자 중에서 가장 큰 숫자를 기억해가며 진행하는 방법일 것이다. 마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다.

👨🏻‍🔬

이러한 방식을 순차탐색(Sequential Search) 이라고 한다.

카드를 한 장씩 차례대로(주어진 순서대로) 읽어가며 찾는 방법이다.

👩🏻‍💻 의사코드로 표현해본다면?

Alg findMax(A)

    input array A of size n
    output integer max

1. max <- A[0]

2. for i <- 1 to n-1
    if(A[i] > max)
        max = A[i]

3. return max

🧐 1.2 임의의 숫자 찾기

❓ 문제

특정 숫자가 적힌 카드를 찾는 것을 생각해 보자.

45, 20, 60, 35, 10, 55, 90, 85, 75, 25

최대 숫자 찾기처럼 머릿속에 숫자를 기억하고 바닥에 펼쳐진 카드를 차례대로 한 장씩 읽으며 해당 숫자가 적힌 카드를 찾는다.

👨🏻‍🔬

1.1의 문제와 같이 순차탐색(Sequential Search) 을 이용한 풀이법이다.

❓ 문제

같은 10장의 카드가 오름차순으로 미리 정렬되어 있다고 가정하자. 순차탐색보다 더 효율적인 방법은 없을까?

중간 카드 한 장을 읽어 숫자와 비교해보는 것이 첫 카드를 읽어 나가는 순차탐색보다 훨씬 빠르게 목표에 다가감을 알 수 있다.

👨🏻‍🔬

이러한 방식을 이진탐색(Binary Search) 이라고 한다.

오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이 과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘이다.

👩🏻‍💻 의사코드로 표현해본다면?

재귀 호출 방식

Alg binarySearchRecur(A[], left, right, key)

int mid;
static int count = 0;

if(left <= right)
{
    count++;
    mid = (left+right)/2;
   
    if(key == A[mid])
        return count;
    else if(key < A[mid])
        return binarySearchRecur(A, left, mid-1, key);
    else
        return binarySearchRecur(A, mid+1, right, key);
}

return 0;

반복 방식

Alg binarySearchIter(A[], left, right, key)

int mid, count = 0;

while(left <= right)
{
    count++;
    mid = (left+right)/2;
    if(key == A[mid])
        return count;
    else if(key < A[mid])
        right = mid - 1;
    else
        left = mid + 1;
}

return 0;

🧐 1.3 동전 거스름돈

❓ 문제

물건을 사고 거스름돈을 동전으로 받아야 할 때, 대부분의 경우 가장 적은 수의 동전을 받길 원한다. 어떻게 하면 가장 적은 수의 동전을 찾을까?

남은 거스름돈 액수를 넘지 않는 한도에서 (욕심내어) 가장 큰 액면의 동전을 계속하여 선택하면 된다.

👨🏻‍🔬

이러한 방식을 그리디(Greedy) 알고리즘이라 한다. 자세한 내용은 4.1절에서 계속된다.

🧐 1.4 한붓그리기

❓ 문제

어느 한 점에서 출발하여 모든 간선을 한 번만 지나서 출발점으로 돌아오되, 궤적을 그리는 동안 연필이 종이에서 떨어져서는 안된다. 점은 여러 차례 방문하여도 무방하다. 어떻게 한붓그리기의 해결 방법을 찾아야 할까?

현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 사이클(Cycle)을 찾는다.

🧐 1.5 미로찾기

❓ 문제

실타래나 도와주는 사람이 없다고 가정할 때, 어두운 미로 속에서 빠져나올 수 있는 방법은 무엇일까?

현 위치에서 한 방향을 선택하고, 벽에 오른손을 댄다. 그리고 출구가 나올 때까지 계속 오른손을 벽에서 떼지 않고 걸어간다.

🧐 1.6 가짜 동전 찾기

❓ 문제

아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여 있다. 가짜 동전은 눈으로 식별할 수 없고, 정상적인 동전보다 약간 가볍다. 양팔 저울 사용 횟수를 최소로 하여 가짜 동전을 찾으려면 어떻게 해야 할까?

철수

동전 1개를 저울 왼편에, 나머지 동전을 하나씩 오른편에 올려서 가짜를 찾는다.

👨🏻‍🔬 철수는 최대 $n-1$

👩🏻‍💻 의사코드로 표현해본다면?

Alg cheolsu(A)

    input array A of size n
    output integer count

for i <- 1 to n-1
    count++
    if(A[0] != A[i])
        return count

영희

동전을 2개씩 짝지어, $n/2$ 짝을 각각 저울에 달아서 가짜 동전을 찾는다.

👨🏻‍🔬 영희는 최대 $n/2$번 저울을 재야 한다.

👩🏻‍💻 의사코드로 표현해본다면?

Alg younghui(A)

    input array A of size n
    output integer count

for(i = 0; i < n; i += 2)
    count++
    if(A[i] != A[i+1])
        return count;

광수

동전 더미를 반으로 나누어 저울 양편에 놓아보고, 더 가벼운 쪽만 반씩 나누어 계속 절반으로 나누어 저울에 놓아 본다.

👨🏻‍🔬 광수의 알고리즘은 운이 좋을 때가 없다. 왜냐하면 항상 마지막에 가짜 동전을 찾기 때문이다. $n$개의 동전이 있을 때 항상 $log_2n$

👩🏻‍💻 의사코드로 표현해본다면?

Alg kwangsu(A, left, right)

    input array A of size n, integer left, integer right
    output integer count

1. while(left != right)
      count++
      mid = (left + right) / 2
      if(sum(A, left, mid) < sum(A, mid + 1, right))
          right = mid
      else
          left = mid + 1

2. return count

🧐 1.7 독이 든 술단지

❓ 문제

$n$개의 술단지 중 하나에만 눈으로 확인할 수 없는 독이 들어있다. 독이 든 단지의 술을 아주 조금만 맛보아도 정확히 일주일 후에 죽는다고 할 때, 희생되는 사람의 수를 최소로 하여 독이 든 술단지를 찾으려면 어떻게 해야 할까?

Hint! 입력의 크기가 아주 작을 때 문제의 답을 찾아보자.

각 단지에 2진수를 0부터 부여하고, 각 사람이 술 맛을 보면 1, 안 보면 0으로 하여 단지와 사람을 짝지어 본다.

ex) 단지1: 00 / 2: 01 / 3: 10 / 4: 11

👨🏻‍🔬

$n$개의 단지가 있으면 $log_2n$

💡 요약

👋 순차탐색(Sequential Search)

주어진 순서에 따라 차례로 탐색한다.

👋 이진탐색(Binary Search)

정렬된 항목들에 대해서 중간에 있는 항목을 비교하여 그 결과에 따라 같으면 탐색을 마치고, 다르면 작은 항목들이 있는 부분 또는 큰 항목들이 있는 부분을 같은 방식으로 탐색한다.

👋 동전 거스름돈 문제

가장 액면이 높은 동전을 항상 선택(욕심내어 선택)한다. 그리디(Greedy) 알고리즘은 4장에서 다룬다.

👋 한붓그리기 문제

오일러 서킷(Euler Circuit) 문제와 같다. 알고리즘의 핵심은 현재 점에서 다음으로 이동 가능 한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 사이클이 존재하여야 한다는 것이다.

👋 가짜 동전 찾기

동전 더미를 반으로 분할하여 저울에 달고, 가짜 동전이 있는 더미를 계속해서 반으로 나누어 저울에 단다. 이는 분할 정복(Divide-and-Con quer) 알고리즘의 일종이며, 분할 정복 알고리즘에 대해서는 3장에서 상세히 설명한다.

👋 독이 든 술단지 문제

2진수를 활용하여 그 해를 찾는다.