[Python] 배열

배열의 필요성

 - 다수의 변수로는 하기 힘든 작업을 쉽게 할수있도록 도와준다.

 

1차원 배열

 - 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때

 - 배열 이름 (리스트 이름)

      Arr = list(), Arr = [] 

 

1차원 배열 접근

Arr[0] = 10; Arr 의 0번재 원소에 10을 저장

Arr[idx] = 20; Arr의 idx 번째 원소에 20을 저장

 

 

정렬

- 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값( 오름차순 : ascending), 혹은 그반대 내림차순(descending) 으로 재배열

 

종류

  -  버블 , 카운팅, 선택, 퀵, 삽입, 병합

 

버블

- 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

 

과정

 1. 첫 번째 원소부터 오름 / 내림 선택 (기본은 오름)하여 정렬한다

 2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

 3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블정렬

 

ex ) [55, 7, 78, 12, 42]

 1. 싸이클 - 7.55.78.12.42 > 7.55.78.12.42 > 7.55.12.78.42 > 7.55.12.42/78 

 2. 싸이클 - 7.12.55.42.78 > 7.12.42/55/78 > 끝난거 같지만 한번더한다.

 3. 싸이클 - 7.12/55/42/78

 4. 싸이클 - 7/12/55/42/78

 5. 싸이클 - x 

def BubbleSort(a) : # 정렬할 List\
    for i in range(len(a)-1, 0, 1)  : #범위의 끝 위치 
        for j in range(o,i) :
            if a[j] > a[j+1] :
                a[j], a[j+1] = a[j+1], a[j] #Swap 하는거대신 ^^^^^^^^^^^^^^^^^^^ 이놈사용#temp = a#a = c#c = temp

카운팅

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

제한 사항

 - 정수나 정수 표현이 가능한 자료만 가능 : 각 항목의 발생 회수 기록 위해, 정수 항목 인덱스 되는 카운트들의 배열을 사용하기 떄문.

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

과정

 - 정렬된 집합에서 각 항목의 앞에 위차할 항목의 개수를 정렬한다.

 

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

count = [0] *(4+1)

 = 0 1 2 3 4 

    1 3 1 1 2 > [0 ,1 1 1, 2, 3, 4 4]

 

def Countion_Sort(A, B, k)
#A [] -- 입력 배열 (1 to k)
#B [] -- 정렬된 배열.
#C [] -- 카운트 배열
 
c = [0]*k
for i in range(0,len(B)):
    C[A[i]] += 1
 
for i in range(0, len(B)):
    C[i] += C[i-1]
 
for I in range(len(B)-1, -1, -1) :
    B[C[A[i]]-1] = A[i]
    C[A[i]] -= 1

 
for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1 :
            for i3 in range(1, 5):
                if i3 != i1 and i3 != i2:
                    print(i1,i2,i3)

 

 

 

 

ex) Baby-Gin Game 

0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고,

3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.

그리고, 6장의 카드가 run,triplet으로만 구성된 경우를 baby-gin으로 부른다

6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.

 

ex) Baby-gin 조건

 - 667767 = triplet (666,777)

 - 054060 = run 1, triplet 1 (456,000)

 - 101123 = x (123, 011) (111, 023) 베이비진은아님

 

조심해얄 것

- 입력 받은 숫자를 정렬한 후 확인 >123123 일경우 11 22 33 으로 오히려 확인이 불가할수도있음(탐욕 알고리즘적)

 

우리는 완전 검색을 사용해야한다.

그럴려면 

1. 고려할 수 있는 모든 경우의 수 생성하기

2. 테스트하기.