알고리즘 라이프 (Bad Choices)
일상 속 스마트한 선택을 위해
28 Apr 2018
View Comments
#bookreview
#daily
#life
#algorithm
#ali
작년 말 한국을 다녀오면서 사들고온 알고리즘 라이프(Bad Choices by Ali Almossawi)란 책이 책꽃이에 있길래 읽었습니다. 참 쉽고 명료하게 잘 정리 해 놓은 이책은 일상 생활에서 흔히 우리가 접할수 있는 알고리즘들을 컴터 공학의 기초들과 같이 잘 접목시켜 나열하고 있습니다. 얼마나 술술 읽히는지 다 읽는데 3시간도 채 걸리지 않은거 같네요. 이책엔 여러가지 예제를 제시하는데 제 생각을 조금 첨가하여 몇가지 예제만 소개해 드리려합니다. 아래 내용들은 책에서 다룬 내용과는 다소 차이가 있습니다. 제 견해가 많이 포함되어 있습니다.
산더미처럼 쌓인 양말 짝을 맞춰라
양말이 한더미 쌓여있는데 양말의 짝을 맞춰야 합니다. 어떻게 해야 효율적일까요? 아마 가장 쉽게 생각할수 있는 방법은 아마 양말 한짝을 찾아서 다른 한짝을 양말 산더미에서 찾는 방법일겁니다. 만약 많은 양말이 쌓여있다면 다른 한짝의 양말을 찾는데 오랜 시간이 걸릴 겁니다. 코드로 표현하자면 이런 식이겠네요:
for i in range(n):
for j in range(i, n):
if (socks[i] == socks[j]) 찾았다! socks[i]와 socks[j]는 빼서 정리그럼 다른방법이 뭐가 있을까요? 그냥 무자비로 나열하는 방법이 있습니다. 나열하다가 짝이 맞으면 맞춘것끼리 치워두면 되니까요. 우린 흔히 이 방법을 코딩에선 캐시(해시)로 구현해볼수 있습니다. 한짝을 캐시에 넣어두었다 다른 한쪽이 맞으면 치워두는 방식입니다. 대충 코드로 적어볼까요?
for i in range(n):
if (socks[i] in cache):
찾았다! 캐시에 있는 양말과 현재 양말을 정리
cache[socks[i]] = socks[i]위에 코드들은 대충 적은것이고 정말 제대로 코드를 적는다면 양말의 맞춤을 알기위해 왼쪽인지, 오른쪽인지, 모양은 어떤지, 무늬는 어떤지등등 각각 양말이 가져야할 특징들이 필요할테고 이 정보를 가지고 제대로 짝을 맞춰 나갈 수 있을 것입니다.
폭탄세일 셔츠를 쓸어 담아라
옷걸이에서 자신의 사이즈에 맞는 셔츠를 빨리 찾아서 담아야 합니다. 이를 쉽게 접근한다면 한쪽 끝에서 자신의 사이즈가 맞는 셔츠가 나올때까지 고를것입니다. 하지만 이러면 재수가 없을땐 다른쪽 끝까지 뒤지게 될 경우가 생기므로 효율적이진 않습니다. 우린 여기서 정렬되어 있는 셔츠를 가지고 이득을 볼 수 있습니다. 왜냐하면 셔츠는 보통 사이즈별로 정렬이 되어있기 때문이죠. 그렇다면 중간을 찾아보고 내 사이즈보다 큰지 작은지를 확인하여 다른쪽 중간을 찾아 나가는 식으로 찾아나갈수 있습니다. 우린 후자의 방법을 흔히 이진검색(binary search)이라고 부릅니다. 이 방법은 첫번째 방법인 선형검색(linear search)보다 찾음에 있어 항목의 수의 크게 영향을 받지 않는다는 장점이 있습니다. 하지만 데이터(셔츠)들이 모두 정렬되어 있어야 한다는 단점을 가지므로 무조건 좋다고는 할수 없습니다.
빠르게 미로를 탈출하라
만약에 아주 복잡한 미로속에서 길을 잃었다면 어떻게 하는게 효율적일까요? 제일 간단하게는 역시 무자비로 통로가 나오면 가보는 방법이 있다. 하지만 이 방법엔 문제가 하나 있습니다. 우리가 지났왔던 길인지를 모르다면 같은 길을 계속 걷게되고 끝이 없는 여정이 될수 있겠죠. 그럼 어떻게 지나갔던 길을 쉽게 표시 할 수 있을까요? 우린 헨젤과 그레텔의 동화에서 빵으로 길을 표기했던 장면을 기억할것입니다. 그렇습니다, 비슷하게 빵이 아닐지라도 온 길을 표시하고 막다른 곳에 도달할 때마다 온 길을 되짚어 나가 다른길을 찾는 것입니다. 우린 이 방법을 역추적(Backtracking)이라고 합니다. 실패를 할 때 다시 갈림길로 돌아가 다른 경로를 찾아보고 계속 반복한다면 출구를 찾을 수 있을것입니다.
쏟아진 우편물을 주소에 따라 정리하라
우채부의 33개의 주소지로 정리되어 있던 우편물을 담은 상자가 우르르 쏟아졌습니다. 어떻게 다시 주소지에 따라 정리할까요? 간단한 방법으로는 우편물을 하나씩 비교해가며 정리해볼수 있겠습니다. 이런 방법을 우린 흔히 삽입정렬(Insertion Sort)이라고 부르는데, 삽입정렬은 물건들이 거의 다 정렬이 되어있을때 효율적이므로 아마 우르르 쏟아진 우편물을 정렬하는데는 도움이 별로 안될것이다. 그럼 다른 정렬방법을 써보면 어떨까? 합병정렬(Merge Sort)을 써보면 어떨까? 뭉치를 계속 반으로 나눠서 두개가 남으면 두개를 주소에 따라 정리하고 4개를 정리하고 8개를 정리하고 계속 정리해 나갑니다. 하지만 33개의 주소지 뿐인 상황에서는 둘중 어느 정렬방법을 선택해도 빠를겁니다. 만약 몇천개의 몇만개의 주소지가 있었다면 합병정렬(Merge Sort)가 월등히 더 빨리 정렬 할 것입니다. 두개의 정렬방법말고 33개의 주소지가 주어진 상황에선 bucket sort/radix sort등등 다른 정렬방법이 효율적일수 있습니다.
SNS에서 관심받을 만한 상태메시지를 업로드하라
트위터와 같이 140개의 단어로 짦고 굵은 메시지를 전달하기 위해 뭘 해야할까? 쉬운 방법으로는 임팩트는 덜 하지만 긴 단어를 짦은 단어로 줄일 수 있을것입니다. 아니면 불필요한 철자들을 일부로 생략할수도 있겠고요. 이처럼 긴단어를 짧게 압축시키는 방도는 늘 시도되어 왔습니다. 그 중 하나의 방법으로 사용되는게 허프만 부호화입니다. 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘이다. 이렇게 허프만 트리를 이용하여 압축을하면 글자를 8비트의 바이너리로 표현할때보단 허프만 부호를 사용하여 압축한 바어너리를 사용하면 큰 압축률을 가진다는것을 알수 있습니다. 이 밖에 단어를 압축시킬수 있는 방법은 많이 있습니다. 하지만 상대방이 알아볼수 있는것이 가장 중요하므로 무조건 압축을 많이한다고 좋은것은 아닙니다.
연말 송년회 전에 모든 잔업을 끝마쳐라
보통 일을 효율적으로 끝내려면 어떻게 할까요? 그냥 아무생각없이 첫번째 일을하다가 다음꺼를하고 다음꺼를하고 하면서 다 끝낼때까지 하는 방법이 있겠습니다. 아니면 쉬운 것에서부터 어려운 순으로 정렬하고 하나씩 해나가는 탐욕적 방법(greedy approach)도 있습니다. 쉬운게 아니라 중요한 순으로 우선 순위에 따라 처리하는 방법도 있겠습니다. 여기서 주위해야 할 것은 그 ‘우선수위’라는 것이 사살은 ‘소요시간’의 함수 일 수 있다는 점입니다. 예를들어 1000장짜리와 1장짜리가 프린트를 위해 기다리고 있다면 1장짜리를 프린트하고 1000장짜리를 프린트 하는것이 더 합리적이라는 말입니다. 우린 이렇게 여러개의 일들을 동시에 처리한다면 효율적으로 처리가 될것입니다. 하지만 동시에 여러가지를 병렬로 진행한다면 신경써야 하는 부분도 많이 있습니다. 이번 일 처리로 인해 다른 일 처리의 지장은 없는지, 이번 일처리는 다음 일처리를 하는데 연관성을 주시하여 살펴 보셔야 합니다.
수제 이니셜 목걸이를 고쳐라
목걸이에 이름 철자들을 끼워넣다 철자가 틀려 다시 배치해야 한다면 어떨까요? 목걸이에 걸린 철자들을 하나씩 빼어내어 철자를 맞춰 다시 끼워 넣는 방법이 있을겁니다. 이를 배열로 구현한다면 어떨까요? 중간에 뭘 하나 넣으려면 그 후에 오는 것들은 하나씩 옆으로 미뤄야 하겠죠. 하지만 목걸이에 철자들을 하나씩 빼어낸 다음 철자를 맞추고 다시 끼워 넣는다고 했으니 똑같은 그림은 아니겠네요. 그러니 정확하게는 스택으로 이를 구현할수 있겠네요. 철자를 빼다가 (pop) 고쳐야하는 부분이 나오면 고치고 다시 끼워 넣는 (push) 작업을 하는거죠.
또 다른 방법은 없을까요? 철자가 틀린 곳을 바로 자르고 철자를 바로 맞춘다음 다시 붙여넣는 방법이 있겠네요. 이는 자료구조(Data Structure)중 하나인 연결리스트(LinkedList)로 구현 할 수 있겠네요. 연결리스트의 종류는 크게 3가지로 나누는데요. Singly, Doubly, Circular Linked List가 있습니다. 링크드리스트에 장점이라면 삭제 및 삽입을할때 바로 진행 (O(1)) 할수 있다는 점인데, 삭제 또는 삽입할 위치 바로 앞에 있는 위치를 필요로 하기 때문에 불편을 겪습니다.
알고리즘이란? - '한정된 시간에서 유의미한 목적을 달성하는 명확한 단계들의 연쇄'
My Overall Rating of this book:
