Python Algorithm Chapter9
Python Algorithm
1. 배낭문제
한정된 배낭에 주어진 물건을 넣어서 물건의 최대 이익을 찾는 조합 최적화 문제
무차별 대입 방식(브루트포스 방식, 주먹구구 대입 방식): 넣을 수 있는 모든 물건의 조합 탐색 - 시간복잡도 :O(2의 N승)동적 계획법(DI): 하위 문제를 해결 하고 저장된 결과를 활용하여 큰 문제 해결 - 시간복잡도 :O(N*C)
N은 물건수, C는 배낭의 최대용량
knapsack()함수
가능한 각 물건 수에 대해 배낭의 최대 용량까지 반복
무게에 맞게 가능한 물건의 조합을 찾고, 총 가치를 비교하여 가장 높은 가치의 조합으로 할당한다.
그리고 표 끝에서부터 오른쪽에서 왼쪽으로 거꾸로 값의 변화가 있었는지를 살피며 최적의 조합을 찾는다.
2. 외판원 문제
시작 도시에서 끝 도시까지 여러 도시를 한번만 방문하는 최단경로
NP-난해 : 다항 시간에 풀 수 있는 알고리즘이 존재하지 않는 문제
외판원이 방문해야할 도시가 늘어날 수록 문제를 푸는 것이 점점 훨씬 어려워진다.
2.1 단순하게 접근하기
한 번에 방문 가능한 모든 도시 조합 확인하는 것, 즉 무차별 대입 접근 방식이 부적합하다.
모든 순열 찾기
- 백트래킹 사용 : 생성된 순열에서 계속 스왑을 하여 새로운 경로를 생성하고, 그 전의 상태로 백트래킹 할 수 있다.
- 순열 생성 :
itertools 모듈에 permutation() 함수사용 - 시간복잡도 :n!
브루트포스 탐색
경로 마지막에 원래 처음의 도시를 추가한다.
경로 리스트의 모든 경로를 전부 탐색하고 두 도시간의 거리 조회 테이블을 사용하여 경로 총 거리 계산한다.
2.2 더 좋은 방법
가능한 모든 순열을 다 고려하기에 순열의 수는 n!개가 나오므로 확장 가능한 방법이 아니다.
다음과 같은 방법으로 근사치를 구하는 것이 효율적이다.
- 동적 계획법
- 유전 알고리즘
3. 전화번호 니모닉
스마트폰 전화 앱의 번호 키판에는 문자가 포함되어있다.
전화번호의 모든 순열을 생성하고, 사전에서 순열에 포함된 단어를 찾는다.
처음부터 각 순열을 생성하고, 각 숫자와 일치하는 문자를 보면서 계속 문자를 결합해낸다 - 일종의 카티션 프로덕트