파이썬으로 풀어보는 기초 알고리즘

파이썬 sw 문제해결 기본

완전검색

가능한 모든 순열을 나열해서 해답을 찾는 방식

ex) baby-gin

탐욕알고리즘 (Greedy Algorithm)

ex) 거스름돈 줄이기: 해 선택 → 실행가능성 검사 → 해 검사

ex) baby-gin

⇒ 탐욕알고리즘 접근은 해답을 찾지 못하는 경우도 있다

정렬 (Sort)

두개이상의 자료를 특정 기준에 의해 오름차순/내림차순으로 재배열하는것

버블정렬, 카운팅, 선택, 퀵, 삽입, 병합 등이 있음

버블정렬

인접한 두개의 원소를 비교하며 자리 교환

시간복잡도? O(n2)

def BubbleSort(a):
	for i in range(len(a)-1, 0, -1):
		for j in range(0, i):
			if a[j] > a[j+1]:
				a[j], a[j+1] = a[j+1], a[j]

카운팅 정렬

집합에 각 항목이 몇개있는지 세는 작업을 하는 효율적인 알고리즘

정수형 자료에만 적용 가능

시간복잡도? O(n+k)

ex) [0, 4, 1, 3, 1, 2, 4, 1]

1. 각 항목의 발생 회수를 세고 이를 count list에 저장: [1, 3, 1, 1, 2]
2. 앞에 위치할 항목 개수를 반영하기 위해 count list의 원소를 조정? 앞의 항목의 개수를 count_list에 더함. : [1, 4, 5, 6, 8]
3. 데이터 마지막부터 적용: count list[1]을 감소시키고 TEMP에 1을 삽입? 마지막 숫자가 1이므로 count list의 1 자리를 1 감소 (4-1=3) ⇒ TEMP data의 4번째 (1+3)에 1 적어줌
4. 이전 과정을 반복