알고리즘 Part.1

1.1 최대 숫자 찾기

순차탐색(Sequential Search) 를 활용해 카드를 한 장씩 차례대로 읽어가며 찾는다.
카드는 정렬X

1.2 임의의 숫자 찾기

10장의 카드가 오름차순으로 정렬되어있는데, 임의의 숫자인 85를 찾고자 할 때 순차탐색보다 효율적인 방법은?

카드가 정렬되어 있다면 이진탐색(Binary Search)를 활용해 반으로 나누며 탐색한다.

1.3 동전 거스름돈

거스름돈을 받을 때 가장 적은 수의 동전을 받고싶다면?

그리디 (greedy) 알고리즘을 이용해 가장 큰 값의 동전부터 챙긴다.

1.4 한붓그리기

한 점에서 출발해 모든 선분을 한 번만 지나서 출발점으로 돌아오되, 연필이 떨어져서는 안된다.

선택한 선분들이 삭제된다고 생각하며, 그래프가 disconnect 되지 않게 유의하며 다음 선분을 선택한다.

1.6 가짜 동전 찾기

아주 많은 동전 더미 속 k개의 가짜 동전이 섞여 있다. 눈으로는 식별할 수 없고, 가짜 동전의 무게는 정상적인 동전보다 약간 가벼워 무게를 측정해 판별할 수 밖에 없다.
양팔 저울만 사용하여 가짜 동전을 찾아야 하는데, 가능한 저울을 사용 횟수를 최소화하자

• 1 : 1 비교
• n / 2로 짝을 지어 비교
• 계속해서 1 / 2로 나누며 비교 위 두 아이디어는 운이 좋아 한 번에 가짜 동전을 찾을 수 있지만 ,최악의 경우를 고려하면 효율이 좋지 못하다.
  반면 세 번째 아이디어는 운과 상관없이 마지막에 가서 가짜 동전을 찾을 수 있지만, 항상 평균적인 시간이 소요된다는 점에서 효율적이다.

  동전이 1,024개 있다면 512개씩 양쪽에 올리고 .. 256 .... 32 ... 4 ..
  총 10번 저울을 사용하면 된다 .
  시간복잡도는 log 1024 = 10 이 나오니 O(log n)이다.

  1.7 독이 든 술단지

  어느날 이웃 나라의 스파이가 임금님의 창고에 들어가서 술단지 하나에 독을 넣고 나오다가 붙잡혔다.
  스파이는 눈 으로 확인할 수 없는 독을 사용하였고, 하나의 단지에만 독을 넣었다고 실토하고는 숨을 거두었다.
  스파이가 사용한 독의 특징은 독이 든 단지의 술을 아주 조금만 맛 보아도 술을 맛 본사람은정확히 일주일 후에 죽는다는 것이다. 임금님은 독이 든 술단지를 반드시 일주일 만에 찾아내라고 신하들에게 명하였다.
  문제는 희생되는 신하의 수를 줄이는 것이다.
  (알고리즘에 사용되는 신하 수를 최소화)

  각 술단지를 2진수인 0과 1로 표기하여, 각 비트당 한 명의 신하를 할당한다면 신하의 희생을 최소화하며 독이 든 술단지를 찾아낼 수 있다.
  술단지 개수가 n인 경우 log n명의 신하가 필요하고, 최소 희생자 수는 0명, 최대 희생자 수는 log n명이다.