[Python] [알고리즘] 1. 배열

정렬

2개 이상의 자료를 특정 기준에 의해 재배열하는 것. 키는 자료를 정렬하는 기준이 되는 특정 값을 의미한다. 대표적인 정렬 방식의 종류로는 버블, 카운팅, 선택, 퀵, 삽입, 병합이 존재한다,

버블 정렬

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식을 의미한다. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

시간 복잡도 : O(n^2)

카운팅 정렬

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

제한사항

  • 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이 가능하다.(각 항목의 발생 수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
  • 카운트들을 위한 충분한 공간을 할당하려면 집합 내 가장 큰 정수를 알아야 한다.

시간 복잡도 : O(n+k) n은 리스트 길이, k는 정수의 최대값

카운팅 정렬은 자료의 값이 인덱스를 이용할 수 있고, 자료값의 범위를 알고 있고 자료의 수가 크지 않을 수록 유용하다.

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

완전 검색

문제를 해결할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 혹은 generate-and-test기법이라고도 하며, 모든 경우의 수를 테스트한 후 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.

그리디(탐욕) 알고리즘

최적해를 구하는 데 사용하는 근시안적 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간 최적이라고 생각되는 것을 골라 최종적 해답에 도달하는 것이다. 그 순간에는 최적이라고 하더라도 최종적인 해답이 최적이라는 보장이 없다.

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

배열 순회

n*m 배열의 n*m개의 모든 원소를 빠짐없이 조사하는 방법.

행 우선 순회

#i행의 좌표
#j열의 좌표
for i in range(n):
	for j in range(m):
		Array[i][j] #필요한 연산 수행

지그재그 순회

#i행의 좌표
#j열의 좌표
for i in range(n):
	for i in range(m):
		Array[i][j + (m-1-2*j)*(i%2)]
#필요한 연산 수행

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

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

arr[0... N -1][0... N-1] #N*N 배열
di[] <- [0,0,-1,1] #상하좌우
dj[] <= [-1,1,0,0]
for i : 0 -> N-1
	for j : 0 -> N-1:
		for k in range(4):
				ni <- i + di[k]
				nj <- i + dj[k]
				if 0 <= ni < N and 0 <= nj < N #유효한 인덱스의 경우


di = [0,1,0,-1]
dj = [1,0,-1,0]
N = 3
for i in range(N):
    for j in range(N):
        for k in range(4):
            ni, nj = i+di[k], i+dj[k]
            if 0<=ni<N and 0<=nj<N:
                print(i,j,ni,nj)

전치 행렬

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

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

부분집합 문제

집합의 원소가 n개일 때, 부분집합의 수는 2**n개 이다. 이는 공집합과 자기 자신을 포함한 경우의 수이다.

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

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

A = [1,2,3,4]
bit = [0] * 4
for i in range(2):
    bit[0] = i
    for k in range(2):
        bit[1] = k
        for j in range(2):
            bit[2] = j
            for l in range(2):
                bit[3] = l
                for p in range(4):
                    if bit[p]:
                        print(A[p], end=' ')
                print()

비트 연산자

비트: 정보를 저장할 수 있는 최소 단위. 8개를 묶으면 1바이트가 된다.

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

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

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

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

<< 연산자

1<<n: 2**n 즉, 원소가 n개일 경우의 모든 부분집합의 수

& 연산자

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

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

n = len(arr)
for i in range(1<<n): #1<<n:부분 집합의 수
    for j in range(n): # 원소의 수만큼 비트를 비교
        if i & (1<<j): # i의 j번 비트가 1인 경우
            print(arr[j], end=', ') #j번 원소 출력
    print()
print()

간결하게 생성하는 부분집합

ARR = [10,20,30]
N=3
n =3
for j in range(N):
    r = n & (1<<j)
    if r!= 0:
        print(ARR[j], end=' ')

T = int(input())
for tc in range(1, T+1):
    ARR = list(map(int, input().split()))
    n = len(ARR)

    for i in range(1<<n): #부분 집합의 개수
        sumV = 0
        cnt = 0
        subset =[]
        for j in range(n): #원소의 수만큼 비트 비교
            if i & (1<<j): #i의 j번 비트가 1인 경우
                subset.append(ARR[j])
                sumV += ARR[j]
                cnt += 1
                print(subset, sumV)

순차 검색

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

def seqSearch(a,n,key)
i<-0
while i < n and a[i] <key:
	i <- i+1
if i<n and a[i] == key:
	return i
else:
	return -1

이진 검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법으로, 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다. 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

검색 과정

자료의 중앙에 있는 원소를 고르고, 중앙 원소의 값과 찾고자 하는 목표를 비교한다. 목표 값이 중앙 원소의 값보다 작으면 왼쪽 값에 대해 새로 검색을 수행하고, 크다면 오른쪽 값에 대해 새로 검색한다.

def binarySearch(a,N,key)
	start = 0
	end = N-1
	while start <= end:
		middle = (start+end)//2
		if a[middle] == key : #검색 성공
			return True
		elif a[middle] > key:
			end = middle-1
		else:
			start = middle +1
	return False

선택정렬 O(n^2)

주어진 자료 중 가장 작은 값의 원소부터 차례대로 선택해 위치를 교환하는 방식. 주어진 리스트에서 최소값을 찾고, 그 값을 리스트의 맨 처음 값과 교환하고, 맨 처음 위치를 제외한 나머지 리스트를 대상으로 반복 작업을 해 위의 과정을 반복한다.

def selectionSort(a,N):
	for i in range(N-1):
		midIdx = i
		for j in range(i+1,N):
			if a[midIdx] > a[j]:
				minIdx = j
		a[i], a[minIdx] = a[minIdx], a[i]

'SSAFY > TIL' 카테고리의 다른 글

[Python] [알고리즘] 6. 큐  (0) 2023.02.20
[Python] [알고리즘] 5. 스택(3)  (0) 2023.02.16
[Python] [알고리즘] 4. 스택(2)  (0) 2023.02.15
[Python] [알고리즘] 3. 스택(1)  (0) 2023.02.15
[Python] [알고리즘] 2. String  (0) 2023.02.14
TAGS.

Comments