4. Array Extra 배열

완전 검색 (Exaustive Search)

• 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
• Brute-force 혹은 generate-and-test 기법이라고도 불리 운다.
• 모든 경우의 수를 테스트 한 후, 최종 해법을 도출한다.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
• 모든 경우의 수를 생성하고 테스트 하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
• 자격검정평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

 

탐욕 알고리즘 (Greedy)

탐욕 알고리즘은 최적 해를 구하는 데 사용되는 근시안적인 방법

 

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택 들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하는 Greedy 접근이 된다.

탐욕 알고리즘의 동작 과정

• 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합 (Solution Set)에 추가한다.
• 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능 한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는 지를 검사한다.
• 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는 지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1)의 해 선택부터 다시 시작한다.

 

비트 연산자

비트 연산자

& 비트 단위로 AND 연산을 한다.

| 비트 단위로 OR 연산을 한다.

<< 피연산자의 비트 열을 왼쪽으로 이동시킨다. ( x2 )

>> 피연산자의 비트 열을 오른쪽으로 이동시킨다. ( /2 )

 

<< 연산자

1<<n : 2n** 즉 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.

 

& 연산자

i&(1<<j) : i의 j번째 비트가 1인지 아닌지를 검사한다.

거짓 - 0 반환.

 

비트 연산자를 활용해서 부분집합 생성하기

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)   # n : 원소의 개수

for i in range(1<<n):
    for j in range(n):
        if i & (1<<j):
            print(arr[j], end=', ')
    print()
print()

 

인덱스

인덱스라는 용어는 Database에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조를 일컫는다. Database 분야가 아닌 곳에서는 Look up table등의 용어를 사용하기도 한다.

 

인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다.

 

배열을 사용한 인덱스

대량의 데이터를 매변 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용할 수 있다.

 

원본 데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 배열을 정렬하기 때문에 속도가 빠르다.