-
일상 생활에서의 알고리즘Algorithm/개념 2020. 12. 28. 18:26
(1) 최대 숫자 찾기
(2) 임의의 숫자 찾기
(3) 동전 거스름돈
(4) 한붓 그리기
(5) 미로 찾기
(6) 가짜 동전 찾기
(7) 독이 든 술단지
알고리즘이란 문제를 해결하기 위한 단계적인 절차이다.
본 포스트에서는 여러 가지 문제 상황에서 알고리즘이 어떻게 활용되는 지에 대해 작성한다.
(1) 최대 숫자 찾기
임의의 숫자가 적혀진 카드 10장이 바닥에 놓여있는 상황을 가정한다.
가장 큰 숫자가 적힌 카드를 찾는 방법들은 무엇인가?한 가지 방법은 카드의 숫자를 하나씩 비교, 가장 큰 숫자를 기억해가며 진행하는 방법이다.
이러한 방식을 ‘순차탐색(Sequential Search)’이라고 한다.
(2) 임의의 숫자 찾기
위와 같은 상황에서 특정한 숫자가 적힌 카드를 찾는 방법들은 무엇인가?
한 가지 방법은 찾으려고 하는 특정 숫자를 머리 속에 기억하고 펼쳐진 카드를 한 장씩 읽으며 해당 숫자를 찾는다.
이러한 방식 역시 ‘순차탐색’을 이용한 것이다.그런데, 10장의 카드가 오름차순으로 미리 정렬되어 있다고 가정한다.
이러한 경우에는 순차탐색보다 더 효율적인 방법이 있다.오름차순으로 정렬된 데이터를 반으로 나누고 나누어진 반을 다시 반으로 나누는 것을 반복하면서 원하는 데이터를 찾는다.
이러한 탐색 알고리즘을 ‘이진탐색(Binary Search)’이라고 한다.
(3) 동전 거스름돈
물건을 사고 거스름돈을 동전으로 받는 상황을 가정한다.
대부분의 사람들은 거스름 돈으로 적은 수의 동전을 받기를 원한다.
예를 들어, 거스름돈이 700원이라면 500원짜리 1개, 100원짜리 2개를 받기를 원한다.
특별한 경우를 제외하고는 100원짜리 7개, 또는 10원짜리 70개를 받기를 원하지 않는다.
그렇다면, 적은 수의 동전을 거스름돈으로 받기 위한 일반적인 방법은 무엇인가?일반적으로 거스름돈에 대하여 가장 큰 액면의 동전부터 차례로 고려한다.
남은 거스름돈 액수를 넘지 않는 한도에서 가장 큰 액면의 동전을 계속하여 선택하는 방법이다.
즉, 710원이 거스름돈일 경우, 500원짜리부터, 100원, 10원 순서대로 선택한다.
(710 - 500X1 = 210, 210 - 100X2 = 10, 10 - 10X1 = 0)
이러한 알고리즘을 ‘그리디(Greedy) 알고리즘’이라고 한다.
(4) 한붓그리기
종이에서 연필을 떼지 않고 그리는 것을 한붓그리기라고 한다.
어느 한 점에서 출발하여 모든 선분을 한 번만 지나서 출발점으로 돌아오되, 그리는 동안 종이에서 연필이 떨어져서는 안 된다. 단, 한 점을 여러 차례 방문하여도 괜찮다.
한붓그리기의 경우, 어떻게 해결 방안을 찾을 것인가?현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 ‘사이클(cycle)’을 찾는다.
(5) 미로 찾기
복잡한 미로 속에 갇혀있을 때, 미로에서 탈출하는 방법은 무엇인가?
일반적인 방법은 현 위치에서 한 방향을 선택하여 이동 후, 길이 막혀 있으면 다시 돌아 나와서 다른 방향으로 시도하는 것을 반복하는 것이다.
그러나 이러한 방법은 매우 비효율적이다.미로에서 나가는 방법 중 하나는 ‘오른속 법칙’을 이용하는 것이다. 벽에 오른손을 댄 뒤, 출구가 나올 때까지 오른속을 벽에서 떼지 않고 걸어간다.
이러한 방법은 크레타 섬 미로의 실타래가 없어도, 미로에 특별한 표시를 하지 않아도 항상 출구를 찾게 해준다.
(6) 가짜 동전 찾기
아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여 있는 상황을 가정한다.
가짜 동전은 눈으로 식별하 수 없으며, 오직 양팔 저울만을 이용해서 찾을 수 있다.(가짜 동전은 진짜 동전에 비해 가볍다고 가정한다.)
가능한 저울에 동전을 다는 횟수를 줄일 수 있는 방법들은 무엇인가?첫 째, 임의의 동전 1개를 저울 왼편에 올리고, 나머지 동전을 하나씩 오른편에 올려서 가짜 동전을 찾는다.
이 경우, 운이 좋다면 1번만에 가짜 동전을 찾을 수 있다.
그러나 최악의 경우, 가짜 동전을 마지막으로 선택한다면, (n-1)번 저울을 재야 한다.둘 째, 동전을 2개씩 짝을 지어, n/2 짝을 각각 저울에 달아서 가짜 동전을 찾는다.
이 경우에도 마찬가지로, 운이 좋으면 첫 번째 짝을 저울에 올렸을 때 바로 가짜 동전을 발견할 수 있다.
최악의 경우는 가짜 동전이 포함된 동전 짝을 가장 마지막으로 저울에 올렸을 때인데, 이 때 n/2번의 저울을 재야 한다.셋 째, 동전들을 2개의 그룹으로 나눈 뒤 저울 양편에 각각 놓는다.
그렇다면 2개의 그룹 중 가짜 동전이 어디 속해 있는지 알 수 있다.
가짜 동전이 속해 있는 그룹을 다시 2개의 그룹으로 나누고, 위와 같은 작업을 반복한다.
이러한 방법은 운이 좋고 나쁘고가 없다. 왜냐하면 가짜 동전은 어차피 마지막에 가서야 발견할 수 있기 때문이다.
항상 log2n 횟수를 시행하여야 한다.
그러나 동전의 갯수가 매우 많다면, 가장 효율적인 방법이다.
(7) 독이 든 술단지
임금의 창고에는 매우 많은 술단지가 있는 상황을 가정한다.
그런데, 술단지 중 하나에 독이 들어가게 되었다.
눈으로는 독이 들어간 술을 식별할 수 없다.또한, 독이 든 술의 특징은 조금만 마셔도 정확히 일주일 뒤에 죽는다는 것이다.
임금은 독이 든 술단지를 일주일 만에 찾아내라고 신하들에게 명령을 내렸다.
어떻게하면 희생되는 신하의 수를 줄일 수 있을 것인가?이러한 문제 해결의 핵심은 적은 수의 술단지에 대하여 우선 생각해 보는 것이다.
술단지의 수를 늘려가면서 일반적인 규칙을 찾는 것이 중요하다.술단지가 2개 있다고 가정한다.
한 명의 신하가 하나의 술단지의 술을 맛보고 일주일 후 살아 있으면 먹지 않은 술단지에 독이 있는 것이고, 죽는다면 맛본 술단지에 독이 들어 있는 것이다.술단지가 4개 있다고 가정한다.
술단지를 두그룹으로 나눈다.
신하 2명이 각 그룹의 술단지 2개 중 하나만을 맛본다.
그렇다면, 맛보지 않은 술단지가 2개가 되어 일주일 후, 신하 2명이 모두 살아 있을 경우, 독이 든 술단지가 무엇인지 알 수 없게 된다.
따라서, 신하 2명이 맛보지 않은 2개의 술단지 중 하나를 또한 동시에 맛보게 한다.
이 경우, 4개의 결과가 생기게 된다.- 아무도 시음하지 않은 단지에 독이 있으면, 일주일 후 두 신하 모두 살아있다.
- 신하 A가 혼자 시음한 단지에 독이 있으면, 일주일 후 A만 죽는다.
- 신하 B가 혼자 시음한 단지에 독이 있으면, 일주일 후 B만 죽는다.
- A,B 둘 다 시음한 단지에 독이 있으면, 일주일 후 둘 다 죽는다.
그렇다면 술 단지 숫자가 많은 경우에는 어떻게 하여야 하는가?
술단지에 ‘2진수’를 부여한다.다음은 술단지가 8개일 때, 2진수 부여 및 술단지를 맛보는 신하들을 설정한 그림이다
각 술단지의 번호에서 신하 A는 첫 번째 자리, 신하 B는 두 번째 자리, 신하 C는 세 번째 자리를 담당한다.
그리고 술을 맛볼 경우 1로 표시, 그렇지 않을 경우 0으로 표시한다.이렇게 하여 단, 3명의 신하만을 이용하여 일주일 만에 독이 든 술단지가 무엇인지를 알 수 있다.
즉, 술단지를 2진수로 표현한 뒤, 각 비트당 한 명의 신하를 할당하는 방법이다.
일반적으로 n개의 단지가 있으면, lob2n명의 신하만이 필요하다.
일주일 후에 반드시 독이 든 술단지를 찾을 수 있고, 최소 희생자는 0명, 최대는 log2n명이다.
Reference
- 양성봉, 『알기 쉬운 알고리즘』. 파주: (주)생능출판사, 2013