Python Algorithm Chapter2

Python Algorithm

검색 문제

1. 선형 검색

모든 요소를 순서대로 전부 다 확인하는 검색. 가장 간단, 자연스럽고 명백한 방법.

• 시간복잡도 : O(n)

2.이진 검색

검색하려는 자료 구조가 미리 정리가 되어있는 경우 가능하다.

중간 위치의 자료를 탐색하여 절반씩 줄여나가는 방식

순서

• 해당 자료 구조의 중간 위치를 확인한다.
• 검색 자료가 중간 위치보다 앞이면 앞의 절반만 다시 검색대상으로 설정한다.
• 검색 자료가 중간 위치보다 뒤면 뒤의 절반만 다시 검색대상으로 설정한다.

• 해당 자료를 찾을 때 까지 반복한다.

• 시간복잡도 : O(lgn)
• 정렬 시간복잡도 : O(nlgn)

3. 제네릭 검색

파이썬의 모든 시퀀스에서 선형,이진 검색이 동작하도록 일반화 할 수 있다.

TypeVar를 이용하여 모든 타입에 대해 검색이 가능하도록 할 수 있다.

Comparable 클래스를 구현하여 비교 연산이 가능하도록 구현하여 검색을 할 수 있다.

4.미로 찾기

출발 지점부터 도착 지점까지 경로를 찾아보자.

4.1 깊이 우선 탐색

막다른 지점에 도달하여 되돌아 오기 전까지의 깊이로 경로를 탐색한다.

자료구조는 스택을 사용한다.

• 파이썬의 List로 스택을 구현한다.
• 후입선출(LIFO) 원칙 , 오른쪽 끝요소 제거 반환
• 방문한 곳은 다시 방문하지 않는다.

4.2 너비 우선 탐색

출발 지점에서 가까운 노드를 순차적으로 탐색하여 최단 경로를 탐색한다.

일반적으로 너비 우선 탐색이 깊이 우선 탐색보다 목표 지점을 늦게 찾는다. 아닌 경우도 있다. BUT, 최단 경로를 찾는다는 장점이 있다.

목표 지점이 출발지점에서 가까운 위치에 있다면 더 빠른 경우도 있다.

자료구조는 큐를 사용한다.

• 파이썬의 deque으로 큐를 구현한다.
• 선입선출(FIFO) 원칙 , 왼쪽 끝요소 제거 반환
• 덱을 사용한 이유는 popleft 매서드를 사용하기 위함.

깊이 우선 탐색과 다른 자료구조, 같은 알고리즘으로 완전히 다른 결과를 낸다.

4.3 A* 알고리즘

비용 함수와 휴리스틱 함수를 사용하여 목표 지점에 빨리 도달할 가능성이 있는 경로 탐색

목표 지점에 도달하는 비용을 과대 평가하지 않는 허용가능한 휴리스틱이어야한다.

비용 + 휴리스틱의 합을 사용하여 가장 낮은 것을 선택한다.

자료 구조는 우선순위 큐를 사용한다.

• 파이썬의 리스트를 이진 heap으로 유지한다.
• 우선 순위가 가장 높은 요소 : 총 비용이 가장낮은 요소
• heappush, heappop 메서드를 사용한다.

유클리드 거리 VS 맨하튼 거리

• 유클리드 거리 : 두 지점의 직선 거리
• 맨하튼 거리 : 격자 공간에서 수평과 수직 거리의 합 거리

미로 찾기에서는 맨하튼 거리가 더 부합한다.

5. 선교사와 식인종 문제

세 명의 선교사와 식인종이 배를 타고 오른쪽에서 왼쪽으로 건너가야한다. 이때 양끝 지점에서는 항상 선교사가 식인종보다 많아야 한다.

해당 문제를 알맞게 잘 표현한다면, 앞의 깊이 우선 탐색, 너비 우선 탐색 A* 알고리즘을 제너릭하게 구현했기 때문에 사용할 수 있다.

6. 적용

대부분의 소프트웨어에서 필수임. 자료구조에 알맞은 검색 알고리즘 사용해야한다.

오늘 배운 가장 기초적인 알고리즘은 발전된 다른 검색 알고리즘의 기초가 된다.