알고리즘 문제 해결 전략 #2

알고리즘 문제 해결 전략 #2

  알고리즘 책 리뷰를 두번째 진행하려고 합니다. 일전에 간단하게 이 책에 대한 간단한 감상을 적어 올리적이 있는데요 아무래도 이 책은 그렇게 간단한 감상 만으로는 전체 내용을 이해했다고 하기 힘들다고 생각해서 제가 완전히 알고리즘에 대한 이해가 설때까지 계속해서 읽고 반복 하려고 합니다. 저의 개인적인 공부의 흐름을 블로그에 남기려고 합니다. 

 이 책이  1장은 문제 해결을 하기 위한 개론의 성격을 띄고 있다면 2장 부터는 본격적으로 이해해야할 기술들에 대한 설명이 이어집니다. 알고리즘책들을 몇권 읽어 보신 분들이라면 익숙한 용어들이지만 인간은 망각의 동물이라 그런 것인지 아니면 제가 머리가 나빠서 그런 것인지 외웠던 용어들도 계속 해서 까먹게 됩니다. 이런 기술 용어들이 어려운 이유는 그 단어에 어떤 개념을 담아서 기호화 했기 때문입니다. 그 단어가 머리에 들어 오지 않는 다는 것은 곧 그 개념을 이해하지 못했다고 해야 겠지요. 이번에 집중적으로 볼 2장에는 그런 개념어들이 많이 등장합니다. 

 저는 그래서 저의 공부의 일환으로 2장에 등장하는 용어들을 제 나름대로 정리하고 넘어가려고 합니다. 정리 해두었다가 까먹으면 이 블로그 포스트를 다시 들여다 보면 되겠지요.  책에서 친절하게 설명해 주고 계시긴 하지만 아둔한 제 머리로는 아직 손에 잡힐듯이 이해 되는 것은 아니라서 저는 몇가지 자료를 더 참고 하려고 합니다. 

첫번째는 일전에 리뷰 한적이 있는 ‘그림으로 개념을 이해하는 알고리즘’ 입니다. 개인적으로 한국에 출간된 알고리즘 관련 서적 중에서 가장 쉽게 정리 된 책이라고 생각합니다. 

두번째는 위키피디아 입니다. 한글로 작성된 위키피디아도 잘 구성되어있지만 현재 시점에서 알고리즘 관련 설명은 아직 부족한 것이 있는 것 같습니다. 그래서 저는 영어로 된 위키 피디아를 더 적극 적으로 참고 하려고 합니다. 

세번재는 책에서 소개된 내용을 초대한 활용하는 것입니다. 물론 책에서 설명된 것을 최우선으로 해야 합니다. 하지만 세번째로 설명한 이유는 이 책은 기본적인 컴퓨터에 대한 이해가 있다는 설정 하에서 씌여진 책으로 보입니다. ( 그 예로 C++ 의 기초에 대한 설명은 빠져 있습니다. ) 결국 기본적인 이해는 독자 스스로 찾아서 해야 하는 조금은 어려운 책이지요. 그래서 책의 전제도 살펴 보고 다른 자료들도 함께 살펴 보는 방식으로 용어들을 정리 해 나가려고 합니다. 

 그리고 이 책을 공부 해 나가면서 블로그도 계속해서 업데이트 해야 할 것 같습니다. 저 같이 공부를 해 나가는 입장에서 완벽하게 정리된 글을 한편 써내는 것은 어려움이 따르고 시간도 많이 걸리는 작업입니다. 저의 생업과 함께 진행해야 하는 시간 제약이 있기 때문에 블로그의 중간 중간에 업데이트 된 시점을 적어 놓고 그 이후에 추가로 공부하거나 알게된 내용을 붙여서 정리할 생각입니다. 

 1. 시간 복잡도 ( Time Complexity)

 위키백과 : 계산 복잡도 이론에서 시간복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가르킨다. 

 [시간 복잡도 - 위키백과, 우리 모두의 백과사전](https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84)

 

 1-1 계산 복잡도이론 (Computation complexity theory)은 컴퓨터 과학에서 계산이론의 분야로 계산문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 

그림 알고리즘: 시간 복잡도에 대한 개념 설명이 없음.

문제해결 알고리즘:  가장 널리 사용되는 알고리즘의 수행 시간 기준으로 , 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 

P.106

2. 선형시간 

위키백과 :  계산복잡도 이론에서 입력길이 n에 대하여 어떤 알고리즘의 실행시간이 선형이 되는 것을 뜻한다. 

[선형 시간 - 위키백과, 우리 모두의 백과사전](https://ko.wikipedia.org/wiki/%EC%84%A0%ED%98%95_%EC%8B%9C%EA%B0%84)

그림 알고리즘:  추측해야할 최대 횟수는 리스트의 길이와 같습니다. p.11

문제해결 알고리즘: N이 두배 커지면 실해도 두배 오래 걸리고, 반으로 줄어 들면 수행시간도 반으로 줄어 듭니다. 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 되지요. 

3. 선형이하 시간 알고리즘 

위키백과: 정의 없음

그림 알고리즘: 정의 없음

문제해결 알고리즘:  입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘 

P.98

4. 이진탐색 (binary search algorithm)

위키백과 :  오름차순으로 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다. 

그림 알고리즘:   이진탐색에서는 매번 남은 숫자 중의 가운데 숫자를 말하고 대답에 따라 그보다 큰 숫자 혹은 작은 숫자를 한꺼번에 없앨 수 있습니다. 

P.6

문제해결 알고리즘: 오름차순으로 정렬된 배열 A[] 와 찾고 싶은 값 x 가 주어질때 

A[I-1]<x <=A[i] 인 I 를 반환한다. A[-1] = -♾, A[N] = ♾ 로 가정한다. 

P.99

5. 다항시간 알고리즘

위키 백과 : 다항시간은 어떤 문제를 계산하는 데에 걸리는 시간이 문제의 크기 n의 다항식 함수 보다 크지 않을 것을 가르킨다. 

[다항 시간 - 위키백과, 우리 모두의 백과사전](https://ko.wikipedia.org/wiki/%EB%8B%A4%ED%95%AD_%EC%8B%9C%EA%B0%84)

그림 알고리즘 : 정의 없음

문제해결 알고리즘: 반복문의 수행 횟수를 입력 크기의 다항식으로 표현 할 수 있는알고리즘들을 다항시간 알고리즘이라고 부릅니다. 

P 100

6. 지수시간 알고리즘 

위키 백과 :  한글 위키 정의 없음 

영어 위키 : An algorithm is said to be exponential time, if/T/(/n/) is upper bounded by 2poly(/n/), where poly(/n/) is some polynomial in/n/. More formally, an algorithm is exponential time if/T/(/n/) is bounded by O(2/n//k/) for some constant/k/. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as [EXP]

[Time complexity - Wikipedia](https://en.wikipedia.org/wiki/Time_complexity#Exponential_time)

 그림 알고리즘 : 정의 없음

문제해결 알고리즘:  N이 하나증가할 때 마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수시간 (exponential time)에 동작한다고 말합니다. 

2019년 3월 2일 정리

용어를 정리하고 나니 책을 읽기가 훨씬 편해 진것 같습니다. 오랜시간 수학과 멀리 떨어진 삶을 살다 보니 수학의 개념이 적용되어 있는 자료들을 볼떄마다 불편함을 느낄때가 많습니다. 익숙하지 않은 개념들을 이해하기 위해서는 하나의 방법 밖에 없다고 생각합니다. 

바로 반복이지요.  외워질때 까지 반복하는 것 외에는 딱히 뾰족한 수가 없는 것 같습니다.다른 사람들에게 설명하는 기회를 얻게 된다면 좀더 빨리 익힐 수 있겠지만 잘 모르는 사람에게 배울 사람을 모으는 것은 쉬운일은 아니니까요. 일단 블로그에라도 제가 공부한 것들을 정리 해 나가야 할 것 같습니다 

2019/02/18 - [하루 책읽기/하루 기술서] - 열혈C 프로그래밍 - 컴퓨터와 대화하기

2019/01/29 - [하루 책읽기/하루 기술서] - 알고리즘 문제해결 전략 - 어떻게 문제를 해결 할 것인가?

2018/09/11 - [하루 책읽기/하루 기술서] - 그림으로 개념을 이해하는 알고리즘 #2