최근 파이썬 공부를 하면서 개발자 유투브 영상 등을 틈날때마다 보고있는데 다들 입을모아 알고리즘을 꼭 공부해야한다, 코딩테스트를 위해서 뿐만 아니라 개발자로써 커리어를 쌓기 위해 꼭 필요하다라는 얘기를 들어 매일 조금씩이라도 공부하기 위해 책을 읽으며 기록하려고 한다.

내가 아직 프로그래밍 언어에 대한 이해도가 깊지 않기 때문에, 특정 언어에 얽매이지 않고, 또한 아침 출근 직후 시간에 짬내서 읽기 괜찮은 분량의 책을 찾았는데 이 책이 딱 그 조건에 부합해서 선택해보았다.

앞으로 평일에는 하루에 4페이지 정도 읽고 내용을 간단하게 요약해서 블로그에 올리려고 한다.

제 1장. 알고리즘이란

1. 음식 요리법은 알고리즘

알고리즘(Algorithm); 컴퓨터를 이용해 주어진 과제를 해결하기 위한 처리 절차
- 과제의 예
  - 최대 공약수를 구한다
  - 정보의 순서를 정해 나열
  - 원하는 정보 검색

현실세게의 다양한 과제의 해결에도 알고리즘의 개념이 사용된다
예: 음식 요리법
- 치킨카레 만들기 ⇒ 과제
- 알고리즘
  - 요리 재료 종류와 양을 정의
  - 시간별로 요리 절차가 적혀있다

2. 알고리즘은 선인들의 지혜

음식 요리법 중 나쁜 요리법은 사용하는 사람이 적어질 것이고, 음식을 맛있게, 쉽게, 빠르게 만들 수 있는 좋은 요리법은 사용하는 사람이 많아질 것 ⇒ 알고리즘도 마찬가지

알고리즘의 경우에도 보다 효율적으로, 보다 범용적으로, 보다 빠르게 처리를 할 수 있도록 알고리즘을 개선하게 된다.

3. 알고리즘을 이해하는 것은 게임을 잘 하게 되는 것

알고리즘의 학습은 게임의 공략법과 같이 더 나은 프로그램을 만들기 위한 방법
- 알고리즘은 효율적인 프로그래밍을 위해 반드시 학습해야한다.

4. 알고리즘에는 ‘정당성’과 ‘정지성’이 있어야한다

알고리즘은 다음의 두 가지 조건을 충족해야 한다.

1. 정당성

주어진 과제에 대해 올바른 결과를 반환해야 한다(입력값이 지정된 조건과 일치한다면 ).
정당성을 증명하는 방법: 단정문(Assertion)
- 알고리즘의 실행순서 중 임의의 위치에서 충족해야하는 조건이 성립하는지(올바르게 동작하는지) 체크
- 단계별 동작을 확인해 알고리즘 전체의 정당성을 체크할 수 있다.

2. 정지성

어떠한 조건의 입력값이 주어지더라도 정해진 시간 내 반드시 정상적인 종료를 보장
영원히 처리를 반복해 답을 내지 않는 처리(무한 루프)는 알고리즘이 아님
정지성을 증명하는 방법: 반복 처리의 종료조건 체크에 사용되는 변수를 관찰해 정해진 횟수만큼 반복하면 반드시 정지하는 것을 증명

5. 알고리즘에는 다양한 종류가 있다

중요한 알고리즘의 종류
- 기술 계산
- 정렬
- 검색
- 문자열 패턴 매칭

1. 기술계산

기술계산을 위한 알고리즘
기술계산의 예
- 유클리드 호제법(최대공약수)
- 가우스 소거법(방정식)
- 사다리꼴의 법칙(정적분)
- 데이크스트라 알고리즘(최적 경로)
- 에라토스테네스의 체(소수)

2. 정렬(Sort)

1줄로 늘어선 데이터를 작은순서(오름차순) 또는 큰 순서(내림차순)로 정렬하는 알고리즘
정렬의 예
- 단순 선택 정렬
- 단순 교환 정렬 (버블 정렬)
- 단순 삽입 정렬
- 셸 정렬
- 병합 정렬
- 퀵 정렬

3. 검색(Search)

많은 양의 데이터 중 원하는 데이터를 찾는 알고리즘
검색의 예
- 선형검색 (리니어 서치: Linear Search)
- 이진 검색 (바이너리 서치: Binary Search)

4. 문자열 패턴 매칭

문자열 중 지정 문자열의 패턴(부분 문자열)과 일치하는 부분을 찾는 알고리즘
문자열 패턴 매칭의 예
- 단순 문자열 일치
- KMP 알고리즘
- BM 알고리즘

5. 구조적 프로그래밍

프로그램을 효율적으로 작성, 설계상 오류 최소화하기위한 방법론
구조적 프로그래밍에서 사용하는 프로세스 흐름
- 순차구조: 작성 순서대로 순차 실행
- 선택구조: 조건에 따라. 수행할 작업의 흐름 변경
- 반복구조: 조건이 일치하는동안 일정과정 반복 실행