[1] Python 문제해결 - List

1. 완전검색 Exhaustive Search

: 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법.

  > 경우의 수가 작을 때 유용하다.

  > 완전검색으로 접근하여 해답을 도출한 후 성능 개선을 위해 다른 알고리즘을 사용하는게 좋음.

 

경우의 숫자들을 모두 나타내준다.

2. 탐욕 알고리즘 Greedy Algorithm

 : 최적의 해를 구하는데 사용되는 근시안적인 방법

 : 여러 경우 중 하나를 결정해야 할때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

 

수행 과정

A. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤 이를 부분 해 집합에 추가함

B. 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능한지를 확인

          즉 : 문제의 제약 조건을 위반하지 않는지를 검사함.

C. 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지를 확인

               : 아직 전체 문제의 해가 완성되지 않았다면 해 선택부터 다시 시작한다.

 

사용 예시 : 거스름돈 줄이기

해당 숫자가 몇개 존재하는가를 찾아내는대 사용한다.

다음은 Baby-Gin에 관한 예제이다.

BabyGin은 숫자 3개가 연속적일떄  Triple 숫자 3개가 동일할때 Run으로 표시하며 두개다 있을경우 Baby Gin이다.

 

 

OperatorDescriptionExample 참고자료. 연산자.

+	더하기	a + b = 30
-	빼기	a - b = -10
*	곱하기	a * b = 200
/	나누기	b / a = 2.0
%	나머지	b % a = 0
**	제곱	a ** c = 1000
//	몫	a // c = 3

3. 정렬 Sort

대표적인 정렬방식 [ 버블 정렬, 카운팅 정렬, 선택 정렬, 퀵 정렬, 삽입 정렬, 병합 정렬 ]

1) 버블 정렬 : 인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식이다.

 

과정 < 시간 복잡도 = O(n2) >

A. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

B. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨.

C. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블 정렬이라 함.

 

2) 카운팅 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬                       하는 효율적인 알고리즘.

 

과정 < 시간 복잡도 = O(n+k) : n은 리스트 개수 k는 정수의 최대값 >

A. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능, 각 항목의 발생 회수를 기록하기 위해, 정수 항목을 인덱스되는 카운트들의 리스트를 사용하기 때문임.

B. 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야함.