[알고리즘 기초] 02_배열 2 (Array 2) / Python

[알고리즘 기초] 02_배열 2 (Array 2) / Python

[알고리즘 기초] 02_배열 2 (Array 2) / Python

1. 배열 : 2차 배열

1.1 2차원 배열의 선언

• 1차원 List를 묶어놓은 List
• 2차원 이상의 다차원 List는 차원에 따라 index를 선언
• 2차원 List의 선언: 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함
• Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함

arr = [[0, 1, 2, 3], [4, 5, 6, 7]]

 

 

1.2 2차원 배열의 접근

• 배열 순회
  • n X m 배열의 (n * m) 개의 모든 원소를 빠짐없이 조사하는 방법

 

행 우선 순회

# i 행의 좌표
# j 열의 좌표

for i in range(len(Array)):
    for j int range(len(Arrary[i])):
        Array[i][j] #필요한 연산 수행

 

 

열 우선 순회

# i 행의 좌표
# j 열의 좌표

for j in range(len(Array[0])):
    for i in range(len(Array)):
        Array[i][j] #필요한 연산 수행, j당 i가 행의 수 만큼 돌아감

 

 

지그재그 순회

# i 행의 좌표
# j 열의 좌표

for i in range(len(Array)):
    for i in range(len(Array[0])):
        Array[i][j + ( m-1-2*j ) * ( i%2 )]
        #필요한 연산 수행

 

 

델타를 이용한 2차 배열 탐색

• 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법

ary[0...n-1][0...n-1]
dx = [0, 0, -1, 1] # 좌우
dy = [-1, 1, 0, 0] # 상하

for  in range (len (ary)):
    for y in range(len(ary[x])):
        textX = x + dx[y]
        testY = y + dy[y]
        test(ary[textX][textY])

 

 

전치 행렬

• 행렬의 중심 대각선을 기준으로 값을 교환.

# i : 행의 좌표, len(arr)
# j : 열의 좌표, len(arr[0])
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 3*3 행렬

for i in range(3):
    for j in range(3):
        if i < j:
            arr[i][j], arr[j][i] = arr[j][i]m, arr[i][j]

 

 

 

 

2. 부분집합 - 부분집합의 합

• 유한개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
• 완전검색으로 부분집합의 합을 풀기 위해서는, 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산한다.
• 집합의 원소가 n개 일때, 공집합을 포함한 부분집합의 수는 2^n개 이다.

ex) {1, 2, 3} -> 2 * 2 * 2 = 8가지
{ }
{1}, {2}, {3}
{1, 2}, {1, 3}, {2, 3}
{1, 2, 3}

 

 

각 원소가 부분집합에 포함되었는지를 loop를 이용하여 확인하고 부분집합을 생성하는 방법

bit = [0, 0, 0, 0]

for i in range(2):
    bit[0] = i
    for j in range(2):
        bit[1] = j
        for k in range(2):
            bit[2] = k
            for l in range(2):
                bit[3] = l
                print(bit)

 

 

비트 연산자

기호	실행	ex( a = 0011 1100, b = 0000 1101 )
'&'	비트 단위로 AND 연산을 한다.	(a & b) = 12 -> 0000 1100
'|'	비트 단위로 OR 연산을 한다.	(a | b) = 61 -> 0011 1101
'<<'	피연산자의 비트 열을 왼쪽으로 이동시킨다.	a << 2 = 240 -> 1111 0000
'>>'	피연산자의 비트 열을 오른쪽으로 이동시킨다.	a >> 2 = 15 -> 0000 1111

• '<<' 연산자
  • 1 << n : 2^n 즉, 원소가 n개일 경우의 모든 부분집합의 수를 의미한다.
• '&' 연산자
  • i & (1 << j) : i의 j번째 비트가 1인지 아닌지를 리턴한다.

 

 

비트 연산자를 이용한 부분집합의 합을 구하기

'''
10개의 정수를 입력받아 부분집합의 합이 0이 되는것이 몇개가 존재하는지를
계산하는 함수를 작성해 보자.
'''

arr = [-3, 3, -9, 6, 7, -6, 1, 5, 4, -2]
n = len(arr)
# arr = list(map(int, input().split()))

cnt = 0
for i in range(1, 1 << n):
    lists = []
    add = 0
    for j in range(n):
        if i & (1<<j):
            add += arr[j]

    if add == 0:
        cnt+=1
print(cnt)

 

 

 

 

3. 검색

• 저장되어 있는 자료 중에서 원하는 항모을 찾는 작업
• 목적하는 탐색 키를 가진 항목을 찾는 것
  • 탐색 키(search key) : 자료를 구분하여 익신할 수 있는 키
• 검색의 종류
  • 순차 검색 ( sequential search )
  • 이진 검색 ( binary search )
  • 해쉬 ( hash )

 

 

3.1 순차검색

• 일렬로 되어있는 자료를 순서대로 검색하는 방법
  • 가장 간단하고 직관적인 검색
  • 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용
  • 알고리즘이 단순하여 구현이 쉽지만, 수행시간이 급격히 증가하여 비효율적

 

• 정렬되어 있지 않은 경우
  • 첫번째 원소를 찾을 때는 1번 비교, 두번째는 2번 비교
  • 평균 비교 회수 (n+1)/2
  • 시간복잡도 : O
  • 검색 과정
    1. 첫번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다.
    2. 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
    3. 마지막에 이를 때 까지 검색대상을 찾지 못하면 실패

 

• 정렬되어 있는 경우
  • 자료가 오른차순으로 가정
  • 순차적으로 키값을 비교하여, 원소의 키 값이 대상의 키 값보다 크면 없다는 것으로 간주하고 종료

 

 

 

3.2 이진 검색 (Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하는 것으로 계속 진행
• 이진 검색을 위해서는 자료가 정렬된 상태여야 한다.
• 검색 과정
  1. 자료의 중앙에 있는 원소를 고른다.
  2. 중앙 원소의 값과 키 값을 비교한다.
  3. 작으면 중앙의 값보다 작은 구간 선택, 크면 중앙의 값보다 큰 구간 선택
  4. 반복한다.

# 구현
# 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
# 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

def binarySearch(a, key):
    start = 0
    end = len(a) - 1
    while start <= end:
        middle = start + (end - start) // 2
        if key == a[middle]:
            return middle
        elif key < a[middle]:
            end = middle - 1
        else:
            start = middle + 1
    return -1

key = int(input())
data = [2,4, 7, 9, 11, 19, 23]
print(binarySearch(data, key))

 

 

4. 인덱스

• Database에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료구조를 의미한다.
• 배열을 사용한 인덱스
  • 대량의 데이터 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용 할 수 있다.

 

4.1 셀력션 알고리즘

• 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 한다.
• 선택과정
  1. 정렬 알고리즘을 이용하여 자료 정렬하기
  2. 원하는 순서에 있는 원소 가져오기
• k번째로 작은 원소를 찾는 알고리즘
  • 1번부터 k번까지 작은 원소들을 찾아 내열의 앞쪽으로 이동시키고, k번째를 반환한다
  • k가 비교적 작을때 유용하며 O(kn)의 수행시간을 필요로 한다.

 

4.2 선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소들 부터 차례대로 선택하여 위치를 교환.
• 정렬 과정
  1. 주어진 리스트 중에서 최소값 찾기
  2. 리스트의 맨 앞에 위치한 값과 교환
  3. 나머지 리스트들을 대상으로 위의 과정을 반복
• 시간복잡도: O(n^2)
• Bubble Sort보다 시간복잡도가 작다