[TIL: 0202] 알고리즘 정렬 - 카운팅 정렬, 그리디

ryun·2023년 2월 2일

TIL

목록 보기

13/34

카운팅 정렬

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

A : 7 2 5 3 4 5 3 5
0~9 숫자가 각각 몇 개씩 있는가?
cnt = [0] * 10
for x in A:
	cnt[x] += 1

제한 사항
정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 배열을 사용하기 때문
시간복잡도
O(n + k): n은 리스트 길이, k는 정수의 최대값

[0, 4, 1, 3, 1, 2, 4, 1]을 카운팅 정렬하는 과정

Data에서 각 항목들 발생 회수를 세고, 정수 항목들로 직접 인덱스되는 카운트 배열 counts에 저장
정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 조정
앞에서부터 누적된 합으로 변경
counts[1]을 감소시키고 Temp에 1을 삽입1까지 4개의 숫자가 있다고? 1을 감소시키고 Temp에서 4번째 자리에 1을 갖다 놓는다
0까지는 숫자가 1개
1까지는 총 4개의 숫자 > 1보다 작은 애를 포함해서 4게 (0과 1)
count[4]를 감소시키고 temp에 4를 삽입
count[2]를 감소시키고 temp에 2를 삽입

카운팅 정렬 코드

정렬 알고리즘 비교

Baby-gin Game

0-9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 변호를 갖는 경우를 run이라고 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet
6장의 카드가 run과 triplet으로만 구성된 경우가 baby-gin
baby-gin 여부를 판단하는 프로그램 작성해라
미리 정해진 배열을 사용

완전 검색

문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
Brute-force 또는 generate-and-test 기법
모든 경우의 수를 테스트한 후, 최종 해법을 도출
경우의 수가 상대적으로 작을 때 유용

완전 검색을 활용한 Baby-gin 접근

고려할 수 있는 모든 경우의 수 생성
6개 숫자로 만들 수 있는 모든 숫자 나열 (중복 포함)

순열

서로 다른 것 중 몇 개를 뽑아서 한 줄로 나열하는 것

단순하게 순열 생성

{1, 2, 3}을 포함하는 모든 순열을 생성하는 함수
동일한 숫자가 포함되지 앗아쓸 때, 각 자리 수 별로 루프문을 이용해 구현

탐욕(Greedy) 알고리즘

최적해를 구하는데 사용되는 근시안적 바업
각 선택할 때 최적의 선택 > 선택으로 인해 최종적인 해답이 만들어져도 그 전체가 최적이라는 보장은 없다
무조건 현재 상황에서 최적의 선택
해 선택 > 실행 가능성 검사 > 해 검사

baby-gin을 그리디로 풀이

연속적으로 1 이상인 애가 나타나면 run, 한자리가 3 이상이면 triplet
run 먼저 조사하면 안되는 경우가 있다
따라서 triplet 을 먼저 검사 후 데이터 완전 삭제

*인덱스 구분하는 것보다 두 칸 더 만들어놓고 쓰는게 좋다 (run과 triplet 검사할 때를 위한 여분의 칸)

*붙어서 들어온 숫자 입력받는 방법

for i in range(6):
	c[num % 10] += 1 # 일의 자리 알아내기
    num //= 10 # 일의 자리 날리기

i = 0
tri = run = 0
while i < 10:
	if c[i] >= 3: # triplete 조사 후 데이터 삭제
    	c[i] -= 1
        tri += 1
        continue; # i 증가 없이 반복문 건너뜀
	if c[i] >= 1 and c[i+1] >= 1 and c[i+2] >= 1: # run 조사 후 데이터 삭제
    	c[i] -= 1
        c[i + 1] -= 1
        c[i + 2] -= 1
        run += 1
        continue
    i += 1
if run + tri == 2 : print('Baby Gin')
else: print('Lose')

*그자리 다시 조사하는 경우 만약 123123이면 다시 조사해야 run을 두 번 이상 알아낼 수 있다