홈앤서비스 SK BROADBAND

파이썬 알고리즘의 기초와 시간 복잡도 기반의 최적화 요령까지 배운다!

이 책은 25가지 알고리즘을 통해 파이썬 프로그래밍 입문을 막 끝낸 사람이 기초 알고리즘 학습에 어떻게 접근해야 하는지 알려준다. 또한 파이썬 프로그래밍을 공부한 지 오래된 사람을 위해 파이썬 프로그래밍과 자료구조의 기초를 복습할 수 있도록 도와준다. 코딩 테스트나 기술 면접에 대비해 알고리즘을 배운다면 코드의 처리 성능을 나타내는 시간 복잡도까지 알 필요가 있다. 시간 복잡도는 기술 면접의 단골 질문이며, 똑같이 문제를 해결했더라도 시간 복잡도를 고려해 코드를 작성한 사람이 좋은 개발자로 성장할 가능성이 크다고 평가하기 때문이다. 따라서 처리 성능이 좋은 알고리즘 코드를 작성할 때 시간 복잡도의 개념을 어떻게 활용하는지 소개해 기술 면접이나 코딩 테스트를 준비하는 사람에게도 도움이 되도록 한다.

1장 파이썬의 기본 및 자료구조 알아보기

1.1 프로그래밍 언어 선택
1.1.1 목적에 따라 프로그래밍 언어 선택하기
1.1.2 파이썬을 선택하는 이유
1.1.3 프로그램 실행 방식의 차이 알아보기
1.2 파이썬 개요
1.2.1 파이썬의 특징
1.2.2 파이썬 실행하기
1.2.3 대화형 모드로 파이썬 사용
1.2.4 스크립트 파일로 저장
1.2.5 문자 인코딩에 주의하기
1.2.6 주석
1.3 사칙 연산과 우선순위
1.3.1 파이썬의 기본 계산
1.3.2 소수 계산
1.3.3 자료형 확인
1.4 변수, 대입, 리스트, 튜플
1.4.1 변수
1.4.2 대입
1.4.3 리스트
1.4.4 튜플
1.5 문자와 문자열
1.5.1 문자와 문자열 다루기
1.5.2 문자열 연결
1.6 조건 분기와 반복
1.6.1 조건 분기
1.6.2 긴 줄의 작성 방법
1.6.3 반복
1.7 리스트 내포
1.7.1 리스트 생성
1.7.2 조건을 지정해 리스트 생성
1.8 함수와 클래스
1.8.1 함수 작성
1.8.2 값에 의한 전달과 참조에 의한 전달
1.8.3 변수의 유효 범위
1.8.4 객체 지향과 클래스

2장 기본적인 프로그램 작성하기

2.1 순서도 그리기
2.1.1 처리의 흐름 표현하기
2.1.2 자주 쓰이는 기호 배우기
2.1.3 간단한 순서도 그리기
2.2 FizzBuzz 구현하기
2.2.1 코딩 테스트에 자주 나오는 문제
2.2.2 3의 배수일 때 ‘Fizz’ 출력
2.2.3 5의 배수일 때 ‘Buzz’ 출력
2.2.4 3과 5의 공배수일 때 ‘FizzBuzz’ 출력
2.3 자판기에서 거스름돈 계산하기
2.3.1 거스름돈의 매수를 최소화하려면?
2.3.2 거스름돈 계산
2.3.3 리스트와 반복문으로 프로그램을 간단하게 만들기
2.3.4 잘못된 입력에 대응하기
2.4 기수 변환
2.4.1 10진수와 2진수
2.4.2 10진수를 2진수로 변환
2.4.3 2진수를 10진수로 변환
2.5 소수 판정하기
2.5.1 소수를 구하는 방법
2.5.2 소수인지 알아보는 프로그램 만들기
2.5.3 빠르게 소수를 구하는 방법 고려하기
2.6 피보나치 수열 만들기
2.6.1 피보나치 수열이란?
2.6.2 피보나치 수열을 프로그램으로 구하기
2.6.3 메모이제이션으로 처리 속도 향상시키기

3장 복잡도 학습하기

3.1 계산 비용, 실행 시간, 시간 복잡도
3.1.1 좋은 알고리즘이란?
3.1.2 프로그램을 작성해 처리 시간 측정하기
3.1.3 알고리즘의 성능을 평가하는 복잡도
3.1.4 FizzBuzz 복잡도 알아보기
3.1.5 곱셈 복잡도 알아보기
3.1.6 부피를 구하는 복잡도 알아보기
3.1.7 복잡도 비교하기
3.1.8 최악 시간 복잡도와 평균 시간 복잡도
3.2 자료구조에 따른 복잡도 차이
3.2.1 연결 리스트의 개념
3.2.2 연결 리스트 삽입하기
3.2.3 연결 리스트 삭제하기
3.2.4 연결 리스트 읽기
3.2.5 리스트와 연결 리스트의 구분
3.3 알고리즘 복잡도와 문제 복잡도
3.3.1 복잡도 클래스
3.3.2 지수 시간 알고리즘
3.3.3 계승을 계산하는 알고리즘
3.3.4 어려운 P ≠ NP 예상

4장 다양한 검색 방법 배우기

4.1 선형 검색
4.1.1 일상에서의 검색
4.1.2 프로그래밍의 검색
4.1.3 선형 검색 함수 정의하기
4.2 이진 검색
4.2.1 검색 범위를 반으로 나누기
4.2.2 데이터 증가 시 비교 횟수 고려하기
4.3 트리 구조 탐색
4.3.1 계층 구조 데이터의 검색 고려하기
4.3.2 너비 우선 탐색 구현하기
4.3.3 깊이 우선 탐색 구현하기
4.4 다양한 예제 구현하기
4.4.1 미로 탐험(보초병) 문제
4.4.2 8퀸 문제
4.4.3 n퀸 문제
4.4.4 하노이의 탑
4.4.5 폴더에서 다른 폴더나 파일 찾기
4.4.6 틱택토

5장 데이터 정렬에 걸리는 시간 비교하기

5.1 일상생활에서의 정렬
5.1.1 정렬이 필요한 상황
5.1.2 정렬 알고리즘을 배우는 이유
5.2 선택 정렬
5.2.1 작은 요소 고르기
5.2.2 선택 정렬의 구현
5.2.3 선택 정렬의 복잡도
5.3 삽입 정렬
5.3.1 정렬된 리스트에 데이터 추가하기
5.3.2 뒤에서부터 데이터 이동하기
5.3.3 삽입 정렬 구현하기
5.3.4 삽입 정렬의 복잡도
5.4 버블 정렬
5.4.1 이웃끼리 데이터 교환하기
5.4.2 버블 정렬 구현하기
5.4.3 버블 정렬 개선하기
5.5 힙 정렬
5.5.1 리스트를 효율적으로 사용하는 자료구조 알아보기
5.5.2 마지막에 넣은 데이터부터 꺼내는 스택
5.5.3 스택 구현하기
5.5.4 처음에 넣은 데이터부터 꺼내는 큐
5.5.5 큐 구현하기
5.5.6 트리 구조로 표현하는 힙
5.5.7 힙에 요소 추가하기
5.5.8 힙에서 요소 꺼내기
5.5.9 힙의 구성에 걸리는 시간
5.5.10 힙 정렬 구현하기
5.5.11 범용적인 힙 정렬 구현하기
5.5.12 라이브러리 활용
5.6 병합 정렬
5.6.1 리스트를 분할한 후 병합해 정렬하기
5.6.2 병합 정렬 구현하기
5.6.3 병합 정렬의 복잡도
5.7 퀵 정렬
5.7.1 분할한 각 리스트 안에서 정렬하기
5.7.2 퀵 정렬 구현하기
5.7.3 퀵 정렬의 복잡도
5.8 처리 속도 비교하기
5.8.1 복잡도 비교하기
5.8.2 실제 데이터로 비교하기
5.8.3 안정 정렬

6장 실무에 도움되는 알고리즘 알아보기

6.1 최단 경로 문제
6.1.1 수치화한 비용을 생각하기
6.1.2 모든 경로 조사하기
6.1.3 그래프를 만들어 생각하기
6.2 벨만-포드 알고리즘
6.2.1 변의 가중치에 주목하기
6.2.2 초깃값으로 무한대 설정하기
6.2.3 비용 갱신하기
6.2.4 프로그램 작성하기
6.2.5 벨만-포드 알고리즘에서 주의할 점
6.3 데이크스트라 알고리즘
6.3.1 정점에 주목해 최단 경로 찾기
6.3.2 데이크스트라 알고리즘 구현하기
6.3.3 복잡도를 생각하여 처리 속도 향상하기
6.3.4 힙에 의한 우선순위가 있는 큐 구현하기
6.3.5 데이크스트라 알고리즘에서 주의할 점
6.4 A* 알고리즘
6.4.1 불필요한 경로를 최대한 탐색하지 않기
6.4.2 비용의 추정값 고려하기
6.4.3 A* 알고리즘 구현하기
6.5 완전 탐색 알고리즘
6.5.1 인덱스가 없는 문자열에서 특정 문자열 찾기
6.5.2 일치하는 문자 위치를 앞에서부터 찾기
6.5.3 완전 탐색 알고리즘 구현하기
6.6 보이어-무어 알고리즘
6.6.1 완전 탐색 알고리즘의 문제점
6.6.2 문자열 끝부터 비교해 패턴에 포함되지 않는 문자 건너뛰기
6.6.3 처리 시간 비교하기
6.7 역폴란드 표기법
6.7.1 연산자를 앞에 놓는 폴란드 표기법
6.7.2 연산자를 뒤에 두는 역폴란드 표기법
6.8 유클리드 호제법
6.8.1 최대공약수를 효율적으로 구하기
6.8.2 고급 알고리즘 배우기

부록 A 파이썬 개발 환경 구축하기

A.1 파이썬의 처리 시스템 알아보기
A.2 파이썬 개발 환경 설치하기
A.2.1 윈도우에 설치하는 경우
A.2.2 macOS에 설치하는 경우
A.3 아나콘다로 파이썬 설치하기
A.3.1 윈도우에 설치하는 경우
A.3.2 macOS에 아나콘다 설치하기
A.4 파이썬 가상 환경 만들기
A.5 여러 버전의 파이썬으로 전환하기
A.6 패키지 설치 및 삭제
A.7 파일이나 프로그램을 실행할 때 문제가 발생하는 경우

부록 B 이해도 Check! 정답