[그림으로 배우는 알고리즘], 스기우라 켄, 서재원, 영진닷컴, 2016, (170219).

들어가며

역자의 말

등장 캐릭터 소개

제 1 장 알고리즘이란

001 음식 요리법은 알고리즘이다

알고리즘은 문제 해결을 위한 처리 절차라고 할 수 있습니다.

002 알고리즘은 선인들의 지혜

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

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

① 정당성. 알고리즘은 주어진 과제에 대해 올바른 결과를 반환해야 합니다. 이를 알고리즘의 정당성이라고 합니다. 알고리즘의 정당성이란 '입력값이 지정된 조건과 일치한다면 알고리즘은 반드시 정상적인 동작(올바른 출력값의 반환)을 보장해야 한다'고 정의할 수 있습니다. 알고리즘의 정당성을 증명하는 방법 중 하나로 단정문(Assertion)이 있습니다. 단정문이란, 알고리즘의 실행 순서 중 임의의 위치에 서서 충족해야 하는 조건이 성립하는지의 여부(올바르게 동작하는지의 여부)를 체크하는 것입니다.

② 정지성. 알고리즘은 언젠가 반드시 정지해야만 합니다. 즉, 영원히 처리를 반복하여 답을 돌려주지 않는 처리(이것을 무한 루프라고 부름)는 알고리즘이 아니라는 것입니다. '알고리즘의 정지성'이란 '어떠한 조건의 입력값이 주어지더라도 정해진 시간 내에 반드시 정상적인 종료를 보장하는 것'으로 정의할 수 있습니다. 

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

COLUMN 알고리즘의 기초가 되는 구조적 프로그래밍의 개념

① 순차구조 : 작성된 순서대로 순차 실행한다. ② 선택구조 : 조건에 따라 수행할 작업의 흐름을 바꾼다. ③ 반복 구조 : 조건이 일치하는 동안 일정 과정을 반복해서 실행한다. 

제 2 장 변수와 배열

알고리즘은 '문제'를 해결하고 '겨롸'를 얻기 위한 처리입니다. 알고리즘이 문제를 처리할 때, 그 문제는 데이터의 형태로 입력되고, 결과물 역시 데이터의 형태로 출력됩니다. 따라서 알고리즘의 처리 과정에는 다양한 임시 데이터가 필요합니다. 

006 데이터는 다양한 정보이다

데이터란 다양한 정보를 표현한 것입니다. 알고리즘에서도 문제 해결을 위한 프로세스를 설명하기 위해 다양한 데이터를 이용합니다. 알고리즘을 고안할 때는 다양한 정보가 필요합니다. 이러한 정보는 모두 데이터이며, 문제 해결을 위한 프로세스를 보조하는 역할을 담당합니다. 즉, 모든 알고리즘은 '처리'와 '데이터'를 조합하여 표현한다고 말할 수 있습니다. 

007 모든 데이터에는 타입이 있다

데이터란 다양한 정보를 표현한 것입니다. 데이터로 취급하는 정보는 다양합니다. 알고리즘에서 다루는 데이터 또한, 다양한 그룹으로 나누어서 다룹니다. 이러한 데이터 분류를 데이터 타입이라고 합니다.  

008 값은 숫자와 문자의 구체적인 표현

데이터란 다양한 정보를 표현한 것입니다. 그 데이터를 구체적으로 표현한 것이 '값'입니다. 알고리즘에서 '값'을 표현할 때에는 숫자나 기호로 표기합니다. 

009 변수는 값을 담는 상자이다

알고리즘에서 데이터를 조작할 때에는 조작한 데이터를 저장할 공간이 필요합니다. 그것이 바로 변수입니다. '변수'는 다양한 데이터를 저장하는 상자 역할을 하는 것입니다. 알고리즘에서는 다양한 데이터를 입력값으로 지정합니다. 이런 경우에는 입력값을 '변수'에 담아 전달합니다. 또한 계산 결과인 출력값으로 반환해야 합니다. 이때 결과값 역시 '변수'에 담아서 반환합니다. 또한 알고리즘은 처리 과정에서 다양한 데이터(값)을 다루게 되며, 계산 후에는 그 결과를 저장하고 있어야 합니다. 그 데이터(값)을 보관하기 위해 '변수'라는 상자를 사용합니다. 주의해야 할 점이 있습니다. 변수에는 반드시 하나의 데이터만 담을 수 있다는 점입니다. 즉, 데이터가 들어있던 변수에 다른 데이터를 넣으면, 그 변수에 원래 들어있던 데이터가 지워집니다. 

010 변수는 ‘변수명’이라는 이름으로 구별한다

변수는 '데이터(값)를 저장하는 상자'입니다. 알고리즘에서 변수는 많이 사용됩니다. 따라서 변수의 용도가 무엇인지를 표시하고, 다른 변수들과 구별하기 위한 수단이 필요합니다. 그것이 변수명입니다. 변수명은 데이터(값)를 저장하는 상자에 붙이는 이름입니다. 

011 대입문에는 변수에 값을 대입하는 기능이 있다

알고리즘에서는 변수를 이용하여 다양한 데이터를 유지하고 관리합니다.

012 변수를 변수에 대입하면, 변수에 저장된 값이 다른 변수에 복사된다

013 변수에도 데이터 타입이 있다

다양한 정보를 표현하는 '데이터(값)'에 데이터 타입이 있듯이 변수에도 데이터 타입이 있습니다. 변수를 정의할 때에는 변수 이름과 '어떤 데이터 타입의 값을 담을 수 있는지'를 함께 표기합니다. 즉, 변수에는 어떠한 데이터라도 막 대입할 수 있는 것이 아닙니다. 

014 동일한 데이터 타입이 연속되면 배열이다

알고리즘에서 많은 양의 데이터를 저장하고 유지하기 위하여 사용하는 것이 배열입니다. 많은 양의 데이터를 다루는 '배열'에는 다음과 같은 원칙이 있습니다. 그것은 '원칙 : 배열에 담을 각각의 데이터들은 반드시 같은 종류여야만 한다'는 것입니다. 배열은 데이터 타입이 동일한 변수를 늘어 놓은 것이기 때문에, 배열 자체에도 데이터 타입이 있습니다.  

015 배열은 ‘배열명’이라는 이름으로 구별한다

배열 역시 변수와 마찬가지로 다른 변수 및 배열과 구분되고 원하는 배열을 선택할 수 있도록 고유의 이름을 붙입니다. 이것이 배열명입니다.

016 배열의 각 요소는 요소 번호라는 번호로 구분한다

017 배열은 관련된 값을 효율적으로 저장하기 위한 사물함이다

018 2차원 배열은 호텔의 객실 같은 것

019 배열의 각 요소는 2개의 첨자로 구별한다

020 문자열은 문자 데이터 배열이다

021 문자열의 길이는 문자 길이 변수 혹은 ‘보초 값’이 관리한다

COLUMN 관용적으로 사용되는 변수명

제 3 장 자료구조

022 대량 데이터를 효율적으로 관리하기 위한 메커니즘이 자료구조이다

대량 데이터를 효율적으로 관리하는 메커니즘을 자료구조라고 합니다.

023 다양한 종류의 자료구조들

024 책처럼 쌓이는 자료구조가 스택

025 계산대앞에 줄을 서듯 대기하는 자료구조가 대기 행렬 (큐)

026 끈으로 엮어서 데이터를 관리하는 것이 리스트

027 한쪽 방향에서 데이터를 찾아가는 단방향 리스트

028 양쪽 방향에서 데이터를 찾아가는 양방향 리스트

029 N번째 요소의 참조가 빠른 것은 배열, 느린 것은 리스트 구조

030 데이터의 삽입·삭제가 빠른 것은 리스트 구조, 느린 것은 배열

031 마지막 요소까지 이동하면 1번째 요소로 되돌아오는 링 버퍼

032 부모 하나에 자식 둘이 딸린 구조인 이진 트리

033 부모 노드의 값이 자식 노드의 값보다 항상 적은 이진 트리는 힙

034 해시 테이블은 배열과 리스트를 조합한 자료구조

035 정점과 간선으로 항목들의 관계를 그림으로 표현한 것이 그래프

COLUMN BASE를 0으로? BASE를 1로?

제 4 장 기본적인 알고리즘

036 1 ~ N의 합을 구하려면 반복 처리한다

037 수열의 값을 유지하려면 배열을 사용한다

038 배열 데이터의 합을 계산하려면 더한 값을 저장할 변수를 준비한다

039 배열 안의 요소의 개수를 구하려면 카운터를 준비한다

040 배열 데이터의 평균 값은 반복 처리를 통해 합계와 개수를 구한 후 계산한다

041 배열 데이터의 최대 값을 구하려면 최대 값을 저장할 변수를 준비한다

042 배열 데이터의 최소 값을 구하려면 최소 값을 저장할 변수를 준비한다

043 배열 데이터에 등수를 매기려면 순위를 저장할 또 다른 배열을 준비한다

044 시간의 크고 작음을 비교하려면 단위를 초 단위로 통일한다

045 시간차를 구할 때는 초 단위로 바꾸어 뺄셈하고, 다시 시간으로 바꾼다

046 두 변수의 값을 교환할 때는 임시 변수를 사용한다

047 두 수의 최대공약수는 유클리드 호제법으로 구한다

COLUMN 코드와 데이터는 어디에 있을까?

알고리즘을 컴퓨터에서 실제로 작동시키는 것은 '프로그램'입니다. 따라서 알고리즘은 현실 세계의 컴퓨터 프로그램밍과 밀접하게 관련되어 있습니다. 알고리즘을 구성하고 있는 2가지의 큰 요소인 '처리'와 '변수(자료구조)'는 각각 컴퓨터 프로그램의 중요성 2가지 요소인 '코드'와 '데이터'에 해당합니다. 즉, '처리'를 구현하는 것이 '코드'이며, '변수'를 구현한 것이 '데이터'입니다. 

제 5 장 정렬과 검색 

048 정렬(소트)이란 대상을 특정한 규칙에 따라 정렬하는 것

049 정렬 알고리즘에는 다양한 종류가 있다

050 다른 배열(양동이)에 데이터를 저장하고 정렬하는 ‘버킷 정렬’

051 아래 자릿수부터 윗 자릿수까지 버킷 정렬을 반복하는 ‘기수 정렬’

052 최소 값(최대 값)을 골라서 이미 정렬된 마지막 요소와 교환하는 ‘단순 선택 정렬’

053 이웃한 데이터들을 교환해 나가는 ‘단순 교환 정렬(버블 정렬)’

054 정렬된 데이터를 비교해서 올바른 위치에 삽입하는 ‘단순 삽입 정렬’

055 데이터 열을 일정한 길이의 그룹으로 나누어 정렬하는 ‘셸 정렬’

056 정렬된 여러 개의 데이터 열을 합체시키는 ‘병합(merge)’

057 병합(merge) 알고리즘을 이용하여 정렬하는 ‘병합 정렬’

058 기준 데이터와 크기를 비교해서 데이터를 2등분 하는 ‘퀵 정렬’

059 힙 구조를 이용하여 정렬하는 ‘힙 정렬’

060 검색이란 여러 개의 데이터 안에서 원하는 데이터를 찾아내는 것

061 처음부터 끝까지 샅샅이 데이터를 비교하는 ‘순차 검색(리니어 서치)’

062 정렬된 데이터 안에서 고속 검색하는 ‘이진 검색(바이너리 서치)’

063 주어진 문자열 안에서 원하는 문자열의 위치를 찾아내는 ‘문자열 검색’

064 비교할 필요가 없는 문자열은 건너 뛰고 고속으로 검색하는 ‘KMP 알고리즘’
065 문자열을 끝에서부터 검색하는 ‘BM 알고리즘’
COLUMN 관계형 데이터베이스를 이용한 정렬과 검색

제 6 장 그 외의 알고리즘들

066 미분을 활용하여 고차 방정식의 해를 구하는 ‘뉴턴법’

067 연립 방정식의 해를 구하는 ‘가우스 소거법’

068 사다리꼴의 면적을 더하여 정적분의 값을 구하는 ‘사다리꼴 공식’

069 그래프에서의 최적 경로를 구하는 ‘데이크스트라 알고리즘’

070 자연수 n이 소수인지 아닌지를 걸러 내는 ‘에라토스테네스의 체’

071 재귀호출을 이용하여 N의 팩토리얼 구하기

COLUMN 알고리즘과 플로우 차트(순서도)

제 7 장 알고리즘의 계산량

072 알고리즘의 계산량에는 시간 계산량과 영역 계산량이 있다

알고리즘의 좋고 나쁨을 평가할 때, 즉, 대상 알고리즘이 '얼마나 효율적인가'를 증명할 때에는 시간 계산량과 영역 계산량을 기준으로 삼습니다. 시간 계산량은 해당 알고리즘을 실행시 소요되는 시간을 뜻합니다. 영역 계산량이란 해당 알고리즘 실행시에 사용되는 '공간적 자원'의 크기입니다.

073 시간 계산량은 ‘연산?, ‘조건 비교?, ‘대입’ 등의 조작 횟수로 측정한다

074 알고리즘의 계산량은 ‘O(빅-오) 표기법’으로 표현한다

COLUMN 프로그래밍을 잘 하려면

참고 문헌

색인