알고리즘 라이프

이 책은 일상생활에서 부딪히는 문제의 다양한 해결방법을 제시하고, 

그 방법들을 비교해 어떤 것이 효율적인지 찾아보면서 

알고리즘적 사고방식에 대해 알아보는 것이다. 

 

 

 

1. 산더미처럼 쌓인 양말 짝을 맞춰라 

 

- 방법1 

양말 한짝을 꺼낸 후, 빨래더미에서 짝을 찾아 한쪽에 놓는다. 

그 다음, 다른 양말을 꺼내서 짝을 찾고 한쪽에 놓는다. 

이런 식으로 계속한다. 

 

- 방법2. 

양말 한 짝을 꺼내 한쪽에 놓은 다음, 다른 양말을 꺼낸다. 

그 양말에 한쪽에 놓아둔 것과 짝이 맞으면 맞춰 놓는다. 

안 맞으면 짝없는 양말줄에 따로 놓되, 색깔이나 크기가 같은 것들을 모아 둔다. 

 

 

- 해설

양말 100켤레가 있다고 생각하자.

방법1의 경우 빨래더미에 있는 양말들을 계속 보고 또 보아야 할 가능성이 대단히 높다. 

양말을 새로 한짝 꺼내볼 때, 그 양말은 어떤 특징을 가졌는지 모르는 양말이다. 

하지만, 방법2의 경우 짝없는 양말들을 미리 한쪽에 늘어놓았기 때문에 

빨래더미에서 어떤 양말을 꺼내 보면, 그것이 본 적이 있는 양말인지 아닌지 알 수가 있다. 

 

결론은 두번째 방법이 더 빠른데, 이것이 바로 기억에 의존한 덕분이다. 

더 정확하게는 검색표(캐시; 독특한 식별자'키'의 모음) 덕분이다. 

식별자들 각각이 데이터의 연관항목을 가리키고 우리는 그 항목에서 키의 값을 검색한다. 

이런 표현법을 키값 짝짓기(key-value pair)라고 한다. 

 

양말 찾기에서 키는 '색깔'이다. 

빨간색 양말을 한 짝 꺼낸다면 짝없는 양말을 늘어놓은 곳에서 '빨강'을 찾는다. 

빨강 영역을 발견하고 나면 다른 식별자(모양이나 특징)을 골라낸다. 

만약, 빨간색 영역이 없다면 새로 '빨강'이라는 영역을 만들 것이다. 

 

그렇지만, 모양과 색깔이 서로 다른 양말들이 더 많다면, 

한쪽에 늘어놓은 짝없는 양말도 상당히 많아질 것이고, 

빨래더미에서 새로 양말을 꺼낼 때마다 그 짝없는 양말 전체를 훑어보아야 할 것이다. 

즉, 배열을 검색하는데 시간이 많이 걸릴 수 있다. 

이러한 배열 검색의 대안으로 새로운 구조를 고안했는데, 

그것은 연관배열 혹은 사전이라고 하는데, 해시표(hash table)라고도 부른다.

해시표는 하나의 집합에 데이터들을 보관한다는 점은 배열과 정확하게 똑같지만, 

순서를 따르지 않고 즉각적인 검색을 한다는 점에서 다르다. 

상수시간 검색으로도 불린다. 

 

 

 

 

 

2. 폭탄세일 셔츠를 쓸어 담아라. 

 

우리가 많은 물건들 중에서 하나의 물건을 찾고 있는데, 

찾는 물건을 발견할 때까지 모든 물건을 다 살펴봐야 하는 상황이라면 어떨까? 

즉, 선형시간(linear time)이 걸리는 경우리면 말이다. 

일반적으로 선형함수(linear function)에서 100개중에 하나를 찾는데 1분이 걸린다면, 

200개 중에서 하나를 찾는 데에는 2분이 걸릴 것이라고 예상한다. 

하지만, 하나의 물건을 찾는데 로그시간(logarithmic time)이 걸리는 특수한 경우, 

즉 물건이 정렬되어 있는 경우도 있다. 

선형시간을 로그시간으로 바꾸고 나면 이점이 엄청나게 많기 때문에 

로그는 특히 증가율에 대해서 논의할 때 아주 중요한 개념이다. 

 

- 방법1. 

옷걸이 한쪽 끝에서 다른 쪽 끝까지 차례대로 뒤져라. 

 

- 방법2. 

옷걸이 중앙 지점 근처에서 셔츠를 찾아라. 

중앙 지점에서 찾은 셔츠가 크면 왼쪽을 뒤져라. 

작으면 오른쪽을 뒤져라. 

그런식으로 계속하라. 

 

- 해설. 

방법2는 셔츠들이 크기순으로 옷걸이 정렬되어 있을 가능성이 높다는 것과, 

평균 크기를 찾고 있으니 찾는 셔츠가 옷걸이 중앙 부분에 걸려있을 가능성이 높다는 것이다. 

 

사전이나 전화번호부, 책의 색인처럼 중앙에서 시작해서 왼쪽이나 오른쪽으로 이동하여 검색하고, 

매번 검색할 집합을 반으로 나누는 것이 바로 로그시간 알고리즘이 사용하는 전형적인 방법이다. 

 

정렬된 물건들 중에서 무엇인가를 로그적으로 찾는 방법을 이진검색(binary search)라고 부르기도 한다. 

그 방법이 선형검색이라고 부르는 방법1보다 월등히 낫다. 

 

 

 

3. 장보기 횟수를 최소한으로 줄여라. 

 

컴퓨터에 항목들의 집합을 저장하는 방식은 여러 가지가 있다. 

1의 양말 찾기에서 본 배열 방식과,

2의 배열의 내용물을 정렬함으로써 특수한 성질(검색용이성)을 최대화 할 수 있는 추상데이터 타입의 작동방식이다. 

 

- 방법1. 

부족한 품목이 있다는 것을 알게 되면, 시장에 사러 간다. 

 

- 방법2. 

부족한 품목의 목록을 작성해둔다. 

목록이 일정한 양이 될 때만 한번 시장에 간다. 

아니면, 꼭 필요한 식품, 킷캣바 같은 것이 떨어졌을 때만 한번 방문한다. 

 

- 해설. 

스택은, 무언가를 쌓아 올린것을 뜻한다.

즉, 아랫쪽에 얼마나 많은 것이 쌓여 있든 가장 위에 놓인 항목에만 관심을 두는 경향을 최대한 활용한다. 

 

부족한 물품 항목들이 인지적 스택에 저장되어 있으며, 

중요한 것은 그 스택에서 항목들을 꺼내는 것(popping)이다. 

즉, 그 스택에 어떠한 물품(예; 킷캣)을 추가(push)하면, 스택이 빌때까지

최상위에 있는 것을 반복적으로 제거하기 시작하는 것이다,

킷캣은 그 스택을 비우는 방아쇠인 것이다. 

 

 

 

 

 

4. 빠르게 미로를 탈출하라

 

 

- 방법1.

통로를 따라 걸어가다가 나가는 길을 찾을 때까지 갈림길에서 아무 쪽으로나 돌아라

 

- 방법2. 

오른손을 벽에 얹고 벽을 따라가면서 매번 오른쪽으로만 돌아라. 

 

- 방법3. 

움직이는 동안 실타래를 계속 풀어라. 

만약 막다른 길에 다다르거나 실에 발이 걸리면 

직전에 왔던 갈림길로 돌아가서 다른 방향으로 가라. 

 

- 해설. 

방법3의 경우는, 역추적(backtracking)인데, 실타래가 있어야 가능하다. 

즉, 막다른 곳에 도달할 때마다 온 길을 되짚어 나가 다른 길을 찾는 것이다. 

실패를 할 때마다 갈림길로 돌아가 다른 경로를 찾을 수 있다면, 

반드시 출구를 찾을 수 있다. 

 

미로처럼 제한된 환경에서 한 지점에서 다른 지점으로 이동한다는 개념은 중요하다. 

그것은 네트워크나 그래프같은 것이다. 

그것들의 선(edge)이 미로의 통로에 해당하고, 

정점(vertex)이 교차로에 해당한다. 

 

우리가 흔히 사용하는 맵 어플(길찾기)이나, 로봇 청소기 등에서 사용된다. 

 

 

 

 

 

 

5. 쏟아진 우편물을 주소에 따라 정리하라. 

 

*어떻게 문제들을 더 작은 문제로 쪼갤 수 있을지 생각해보라. 

순서가 정해져 있으면 일을 더 빠르게 할 수 있다. 

신문이 날짜순으로 정리되어 있거나, 드라마가 회차순으로 정렬되어 있는 것을 생각해보자. 

 

 

- 방법1. 

바닥에 봉투 뭉치 하나를 놓는다. 

다른 뭉치를 집어 그 주소가 첫번째의 것과 가까우면,

첫번째 뭉치의 왼쪽에 놓는다. 

그런식으로 계속해서 가장 가까운 주소지 뭉치가 제일 왼쪽, 

가장 먼 주소지가 제일 오른쪽에 있을때까지 계속한다. 

 

 

- 방법2. 

바닥에 봉투 뭉치들을 한 줄로 늘어놓는다. 

그 줄을 절반으로 나눈다. 그 절반을 절반으로 나눈다. 

그런식으로 계속한다. 

각 쌍 중에서 더 가까운 주소지 뭉치를 왼쪽에,

더 먼 주소지 뭉치를 오른쪽에 놓고

모든 쌍을 그런식으로 계속 정렬한다. 

 

 

- 해설. 

방법1은 위에서 살펴본 양말 더미에서 짝찾기와 같은 

이차시간 알고리즘의 전형이다. 

어떤 집합에서 무엇을 찾아내기 위해 전체 집합을 살펴본다면, 

항상 이차시간(n²) 알고리즘을 이용하고 있는 것이다. 

 

이차미만 정렬의 일반적인 방법은 분할정복법이라고 알려진 것이다.

즉, 항목들의 집합을 더 작은 집합들로 쪼갠후에 그 집합들을 정렬하는 방식이다. 

집합을 반으로 나누는 것은 앞에서 보았듯이 로그시간이고,

그것들을 다시 합쳐놓는 것은  모든 항목에 한번씩만 방문하므로 선형시간 작업이다. 

그러므로 방법2의 정렬방법은 선형로그 시간이다. 

이차시간보다 훨씬 빠르고 선형시간보다 약간 느리다고 보면 된다. (n log n)

 

 

 

 

 

 

6. 위대한 음악가들을 정복하라. 

* 영향력 있는 음악을 익혀라. 

 

- 방법1. 

영향력 있는 있는 음악가를 찾아서 그 사람의 노래를 듣는다. 

그 다음 다른 영향력 있는 음악가를 찾아서 그 사람의 노래를 듣는 식으로 계속 한다. 

 

- 방법2. 

음반 가게에 가서 무작정 음반을 잔뜩 산다. 듣는다. 

 

 

- 해설. 

방법1은 링크 분석이라고 알려진 방법이다. 

어떤 자질을 공동으로 가지고 있는 것의 집합이 있다면, 

그것들 사이의 관계(링크)를 분석하여 어떤것이 가장 중요한가?라는 

질문에 답할 수 있다.

가장 많이 참조된 항목에 더 높은 값을 부여하는 구글의 검색 엔진 알고리즘과 같은 방법이다. 

 

방법2는 최악의 경우 선형시간이 걸릴것이고, 방법1은 상수시간이 걸릴것이다. 

 

 

 

 

 

 

 

 

 

 

 

7. SNS에서 관심받을 만한 상태메시지를 업로드하라.

(상태 메시지를 재치있게 다시 쓰되, 140자 이하가 되게 한다.)

 

* 수행시간 복잡도(run-time complexity) : 여러 방법들의 상대적인 속도

* 공간 복잡도(space complexity): 그 방법들에 얼마나 많은 메모리나 디스크 공간이 요구되는가

 

- 방법1. 

긴 단어를 재미는 좀 덜하지만, 짧은 단어로 바꿔라. 

 

- 방법2. 
모음처럼 자주 나오는 철자를 생략하라. 

(best part is some of... => bst part is some of... )

 

- 해설. 

방법2가 컴퓨터 작업과 유사하다. 

데이터 저장에 필요한 공간의 양을 감소시키는 방법이다. 

무언가를 없애지 않고 '최적화'하는데 중점을 두는 방법은, 

알파벳의 철자에 숫자값을 부여하여 단어 같은 데이터를 저장한다. 

숫자나 다른 문자들도 마찬가지다. 

그다음 그 숫자값은 컴퓨터가 이해할 수 있는 이진법(binary)을 이용해 저장된다.

 
또한 이진법으로 만든 데이터를 더더욱 효율적으로 최적화한 방법들이 나왔다. 

예를 들어, 새뮤얼 모스의 암호화 방법은 기존 28비트를 11비트만 있으면 사용 가능하도록 최적화하였다. 

허프만 부호화와 같은 데이터 압축 기술은 중요하고,

공간을 최적화하면 웹 사이트를 더 빨리 로드할 수 있다. 

현재 기술은 이미 기기가 네트워크를 통해 일부 데이터를 보내면 

그 나머지 부분을 추론하거나 재구성할 수 있는 단계까지 발달해있다. 

 

 

 

 

 

 

8. 연말 송년회 전에 모든 잔업을 끝마쳐라!

(금요일까지 모든 일을 끝내기)

 

 

- 방법1.

한 가지 일을 잠시 하다가 다른 일을 한다. 

그 일을 잠시 하다가 또 다른 일을 한다.

그런 식으로 계속한다. 

 

- 방법2. 

일들을 쉬운 것에서부터 어려운 것 순으로 정렬한다. 

가장 쉬운 일부터 시작한다. 

다하고 나면, 두 번째로 쉬운 일로 넘어간다. 

그런 식으로 계속한다. 

 

- 방법3. 

일들을 우선순위에 따라 정렬한다. 

가장 우선순위가 높은 것부터 시작한다. 

다하고 나서 두 번째 우선순위로 넘어간다. 

그런 식으로 계속한다.

 

 

- 해설. 

방법1의 시간 쪼개기 방법은 최신 운영체계가 여러 가지 작업을 처리할 때 사용하는 것으로, 

문맥전환(context switching)이라고 부른다. 

스케줄러는 현재 어떤 프로세스들이 운영되고 있는지를 보고, 그것들에 시간을 쪼개서 할당하고 

각각의 프로세스가 각각 배분된 시간 동안 제대로 수행되는지 확인한다. 

하지만 인간에게 적용한다면 인지적 대가가 상당히 크다.

다급한 요청을 받아 현재 하고 있는 일을 멈추고 다른 일을 한 다음에

처음에 하던 일로 다시 돌아가는 것은 생산성에 방해가 된다.

즉, 문맥전환은 모든 작업을 조금씩이라도 한다는 이점이 있지만,

하나를 제대로 하기에는 어렵게 된다. 

 

방법2는 가장 어려운 일을 마지막까지 미루고, 더 쉬운일을 먼저해서

성취한 작업의 수를 최대한으로 늘리는 기회주의적 방법이다. 

탐욕적 방법(greedy approach)이라고도 하는데,

최소한의 노력을 들이려고 한다는 점을 강조한 용어다. 

 

방법3은 연관성이 적은, 그래서 영향력이 더 작은 일이 아니라, 

실제로 중요한 일에 집중하여 방법2의 결점을 극복한다. 

모두 우선순위에 따라 목록화하여 배열하는 방법이다. 

주의해야 할 것은 우선순위가 사실은 소요시간의 함수일 수 있다는 점이다. 

예를들어 1050쪽 문서와 1쪽짜리 문서가 대기열에 걸려있다면

1쪽짜리에 우선순위를 주는 것이 더 합리적으로 보이는 것이다. 

그렇기때문에 시간 이외에 우선순위의 기준이 되는 속성이 무엇인지 알아야 한다. 

 

 

 

 

 

9. 수제 이니셜 목걸이를 고쳐라. 

(목걸이에 중간에 빠진 철자를 추가하라)

 

 

- 방법1. 

목걸이 걸쇠를 떼어내고 'Q'나 'U'에 도달할 때까지 하나씩 구슬을 제거하고, 

'X'를 넣은 다음 다시 하나씩 구슬을 꿴다. 

 

- 방법2. 

목걸이를 'Q'와 'U' 구슬 사이에서 자르고 어느 쪽에서든

'X'를 넣은 다음 줄을 직물용 풀로 붙인다. 

 

- 해설. 

화살표 모양으로 표현된 링크는 목걸이 줄로 비유된다. 

즉, 집합의 앞부분 어딘가에 하나의 항목을 추가하려고 한다고 해도, 

새로운 항목을 위한 공간 마련에 대해 걱정할 필요가 없이 

그냥 링크를 수정하면 된다. 

즉, 방법2에서 사용한 링크된 리스트(연결 리스트)는

삽입과 삭제를 효율적으로 처리하기 때문에

컴퓨터 작업에서 필수적인 것으로 되었다. 

 

 

 

 

 

 

 

10. 분리수거장에서 택배용 빈 상자를 찾아라 

(가능한 적은 층을 방문하여 빈 상자 하나를 찾는다)

 

 

- 방법1. 

각 층마다 돌아다니며 빈 상자를 찾아본다. 

 

- 방법2. 

안내데스크에 가서 CCTV 화면을 봐 달라고 부탁한다. 

 

 

- 해설.

방법1은 직관적인 방법이고, 선형시간이 걸린다. 

방법2는 화면을 슬쩍 봐주기만 하면 몇 층에 빈 상자가 있는지

알 수 있으므로 방법1보다 낫다. 그러면 한 층만 방문하면 되기 때문에

선형시간이 아니라 상수시간에 빈 상자 하나를 찾을 수 있다. 

 

빅세타 표기법 이라는 것이 있는데 이것은 상한계와 하한계를 가진 

함수를 말한다. 즉 항목의 수가 많을 경우 우리의 함수가 선형함수(n)나 

로그함수(log n)와 같은 더 단순한 함수보다 더 빠르지 않게,

어떤 함수보다 더 느리지 않게 증가한다는 것을 나타낸다. 

 

빅세타를 보완하는 표기법이 두가지 있는데, 빅오메가와 빅오 이다. 

빅오메가는 하한계가 있는 충분히 큰 값 n의 함수이다. 

빅오는 상한계가 있는 충분히 큰 값 n의 함수이다. 

 

 

 

 

 

11. 저자의 이름 순으로 책장을 정리하라. 

 

- 방법1. 

책 한 권을 집어서 책꽂이에 꽂는다.

그 다음에 다른 책을 집어서 책꽂이에 꽂되 

순서를 봐서 첫 번째 책의 왼쪽이나 오른쪽에 꽂는다. 

그런 식으로 계속 한다. 

 

- 방법2.

북엔드를 써서 알파벳 철자별로 자리를 미리 마련해 두고 

책을 철자에 맞추어 꽂는다. 

필요할 때 북엔드의 위치를 조정한다. 

 

 

- 해설. 

방법1은 위의 5에서 우편물을 정리할 때 인접 항목들을 비교하여 

판단하여 정렬하는 방법에 이차시간이 소요된다는 것을 보았다. 

 

방법2는 책꽂이 여러 지점에 균등하게 간격을 나눠 두어서 

항목들을 옮길 자리를 미리 마련해 둔다. 

즉, 공간과 시간을 바꾼 것이다. 

그래서 간격이 더 크거나 간격의 수가 많을 수록 

매번 옮겨야 할 책의 수는 더 적어진다. 

이것은 도서관정렬 혹은 간격삽입정렬 이라고 불린다. 

 

 

 

 

12. 마트에서 최대한 빠르게 필요한 물건만 쓸어 담아라. 

(지나가는 통로의 수를 최소화하라.)

 

- 방법1. 

구입품 목록의 차례에 따라 통로를 지나가라. 

 

- 방법2.

종류별로 정렬된 목록을 미리 준비하라. 종류별로 구입하라. 

 

- 해설. 

다차원배열에 따르면 구입품 목록을 2차원으로 작성하고 

마트의 구획을 기준으로 한 하위배열에 따라 이동하게 된다. 

구입품 목록은 물품종류로 구성된 목록이고,

물품종류는 물품으로 구성된 목록이다. 

 

방법1은 위의 5장과 11장에서 살펴본 이차시간정렬 알고리즘과 

같아 보이지 않지만, 결과는 같다.

그래서 최악의 경우 마트의 모든 통로를 지나야 한다. 

 

순서와 상관없이 빠르게 검색하고 싶을 때 해시표가 유용한데, 

다차원배열에 알면 해시표를 더 잘 이해할 수 있다. 

하지만 해시함수가 해시값을 균등하게 배분하지 않을 경우,

해시함수가 충돌을 일으킬수 있다. 

충돌을 해결하기 위한 방법은 연쇄화(chaining)이다. 

연쇄화를 하면 항목의 집합으로 구성된 해시표가 생긴다. 

 

또 한가지 짚고 넘어가야 할 것은 이미 다차원배열 항목들에 대해

우선순위를 부과한 것인데, 즉 마트 입구에서부터 어떤 항목이 있는 

거리에 따라 순위가 매겨진 것이다. 

최고 우선순위의 작업을 뽑아가고 나면 재구조화하고 그 다음으로 

우선순위가 높은 작업을 위에 올려놓는 식으로 계속 한다. 

우선순위대기열은 더미(heap)라는 특수한 방식으로 표현된다.