Algorithm_02

알고리즘	평균 수행시간	최악 수행시간	알고리즘 기법	비고
버블정렬	O(n**2)	O(n**2)	비교와 교환	코딩이 가장 손쉽다
카운팅 정렬	O(n+k)	O(n+k)	비교환 방식	n이 비교적 작을 때만 가능하다
선택정렬	O(n**2)	O(n**2)	비교와 교환	교환의 회수가 버블, 삽입정렬보다 작다.
퀵 정렬	O(n log n)	O(n**2)	분할 정복	최악의 경우 O(n**2)이지만, 평균적으로는 가장 빠르다
삽입정렬	O(n**2)	O(n**2)	비교와 교환	n의 개수가 작을 때 효과적이다.
병합정렬	O(n log n)	O(n log n)	분할정복	연결리스트의 경우 가장 효율적인 방식

순열

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열한 것
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다
  -그리고 nPr은 다음과 같은 식이 성립한다

nPr = n * (n-1) * (n-2) * ... * (n-r+1)

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 접근이 된다.
• 동작과정
  • 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합에 추가한다.
  • 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다.
  • 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되 않았다면 1)의 해 선택부터 다시 시작한다.

Ex) Baby Gin

num = 456789 # Baby Gin 확인할 6자리 수
c = [0] * 12 # 6자리 수로부터 각 자리 수를 추출하여 개수를 누적할 리스트

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] -= 3
        tri += 1
        continue
    if c[i] >= 1 and c[i+1] >= 1 and c[i+2] >= 1:
        c[i] -= 1
        c[i+1] -= 1
        c[i+2] -= 1
        runt += 1
        continue
    i += 1
if run + tri ==2 : print("Baby Gin")
else: print("Lose")