[알고리즘 강의노트] 1. 알고리즘의 첫 걸음

 

알고리즘이란?

• 문제를 해결하기 위한 단계적 절차
• 수학은 병렬적으로 수식을 계산할 수 있으므로 단계적이지 않다. 알고리즘이라고 부르지 않음
• 요리법은 같은 과정을 여러 번 반복하지 않기 때문에 알고리즘이 아니다.
• 최초의 알고리즘: BC 300 유클리드 최대공약수 알고리즘(GCD)

 

 

 

순차탐색

이진탐색

그리디

한붓그리기: 오일러 서킷 문제

- 현재 점으로 돌아오는 그려지지 않은 사이클이 존재한다면 해당 점으로 간다. 

미로찾기: 오른손법칙

 

 

 

1.6 가짜동전 찾기

많은 동전 중 하나의 가짜동전이 있다. 가짜동전은 진짜동전보다 무게가 조금 가볍다. 최소의 저울질로 가짜동전을 찾아내자!

 

동전의 전체 개수를 n개라고 하자.

1. 2개씩 짝을 지어 2개씩 저울에 올려서 확인한다.
   • 운이 좋으면 한 번만에 동전을 찾아낼 수 있다
   • 최대 n/2번의 저울질이 필요
2. 전체 동전을 반으로 나누어 저울에 올린다. 가벼운 쪽에 가짜동전이 있는 것이므로 무거운 쪽을 버리고 가벼운 쪽을 다시 반으로 나누어 저울에 올린다.
   
   • logn번의 저울질이 필요. 
   • 항상 마지막 저울질할 때 가짜동전을 찾아낸다. 고정된 횟수의 저울질이 필요(logn번)

 

2번 방법은 분할정복 방법이며, 반씩 나누므로 이진탐색으로 볼 수 있다. 

 

 

 

1.7 독이 든 술단지

많은 술단지 중 하나의 단지에만 독이 들어있다. 독을 먹으면 일주일 뒤에 죽는다. 가장 적은 수의 사람을 동원하여 일주일만에 독이 든 술단지를 찾아내자!

 

이진수를 사용하여 문제를 해결한다.

• 사람마다 한 자리씩 할당하여 해당 비트가 1이면 술을 마시고 비트가 0이면 술을 마시지 않는다.

• 술단지 수가 n개라면 동원되는 사람의 수는 logn명이다.
  (술단지 수가 8 이면 동원되는 사람의 수는 log8 = 3명)
• 각 자리마다 사람을 하나씩 할당한다.
• 해당 비트가 1이면 그 사람이 마시고, 0이면 안마신다.
• 첫 술단지는 아무도 안먹어도 되고, 마지막 술단지는 모든 사람이 먹어야한다.

 

• 이 방법은 최악의 경우 동원된 모든 사람들(logn명)이 죽는다.
• 최선의 경우 한 명이 죽는다.