카운팅 정렬 (Counting Sort)
: 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
- 제한 사항
- 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
- 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.
- 시간 복잡도
: O(n+k) : n은 리스트 길이, k는 정수 최대값
카운팅 정렬 과정
카운팅 정렬 알고리즘
N = 6
K = 9 # 0~K
data = [7, 2, 4, 5, 2, 3] # 0~9, K=9
counts = [0] * (K+1)
temp = [0] * N # 정렬된 결과 저장
# counts 배열에 기록하기
for x in data:
counts[x] += 1
# counts의 누적합 구하기
for i in range(1, K+1):
counts[i] = counts[i-1] + counts[i]
# data의 마지막 원소부터 정렬하기
for i in range(N-1, -1, -1): # N-1번 인덱스 -> 0번 인덱스 (역순으로)
counts[data[i]] -= 1
temp[counts[data[i]]] = data[i]
print(temp)정렬 알고리즘 비교
완전 검색 (Exaustive Search)
: 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
Brute-force 혹은 generate-and-test 기법이라고도 불리운다.
모든 경우의 수를 테스트 한 후, 최종 해법을 도출한다.
일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
Baby-gin Game
- 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.
- 그리고, 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin으로 부른다.
- 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.
완전 검색을 활용한 Baby-gin 접근
<고려할 수 있는 모든 경우의 수 생성하기>
- 6개의 숫자로 만들 수 있는 모든 숫자 나열 (중복 포함)
- 예) 입력으로 [2,3,5,7,7,7]을 받은 경우, 아래와 같은 순열을 생성할 수 있다.
2 3 5 7 7 7
2 3 7 5 7 7
2 3 7 7 5 7
...
7 7 7 5 3 2
<해답 테스트하기>
- 앞의 3자리와 뒤의 3자리를 잘라, run와 triplet 여부를 테스트하고 최종적으로 baby-gin을 판단한다.
- 예) 2 3 5 7 7 7 => 해당없음 / triplet => baby-gin 아님!!
단순하게 순열 생성하기
- 예) {1,2,3}을 포함하는 모든 순열을 생성하는 함수
for i1 in range(1, 4):
for i2 in range(1, 4):
if i2 != i1:
for i3 in range(1, 4):
if i3 != i1 and i3 != i2:
print(i1, i2, i3)탐욕 (Greedy) 알고리즘
: 최적해를 구하는 데 사용되는 근시안적인 방법
여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
- 동작 과정:
- 해 선택: 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합에 추가한다.
- 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한지를 확인한다.
곧, 문제의 제약 조건을 위반하지 않는지를 검사한다. - 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인한다.
아직 전체 문제의 해가 완성되지 않았다면 1번 해 선택 과정부터 다시 시작한다.
탐욕 알고리즘을 활용한 Baby-gin
멋쟁이 토마토 개발자 🍅