심화 알고리즘

1. numpy 없이, 2차원 리스트(행렬) Slicing 하기

2차원 행렬 board에서 M x N 행렬을 빼낸다고 가정하면

m = row 수
n = column 수

i = row 인덱스
j = column 인덱스

m, n = 3, 2
for i in range(len(board) + 1 - m):
    for j in range(len(board) + 1 - n):
        [row[j:j+n] for row in board[i:i+m]]

이런식으로 하면 될 것이다!

2. 최대공약수를 유클리드 호제법으로 구하고, 이어서 최소공배수까지 구하기

유클리드 호제법이란

숫자 a, b가 있을 때, [a를 b로 나눈 나머지와 b의 최대공약수] 와 [그냥 a 와 b의 최대공약수]가 같다는 것을 의미한다.

그렇다면, a를 b로 나눈 나머지를 b의 자리에, 원래 b를 a의 자리에 대입시키는 것을 b가 0이 될 때까지 반복한다.
그렇게 남는 a 값이 바로 최대공약수이다.

def gcd(a, b):
    while b > 0:
        (a, b) = (b, a % b)
    return a

최소공배수는 a, b의 곱을 a, b의 최대공약수로 나누면 간단하게 계산할 수 있다.

a * b // gcd(a, b)

사실 파이썬은 이보다 더 간단하게 최대공약수를 구할 수 있다!

기본으로 제공하는 math 라이브러리에 gcd()라고 최대공약수를 구하는 함수를 제공한다.

from math import gcd

최대공약수 = gcd(a, b)

3. 2차원 리스트 90도 회전하기

90도 회전했을 때 행, 열이 변하는 규칙을 정리하면 다음과 같다.

회전한 후 행 번호 = 회전하기 전 열 번호
회전한 후 열 번호 = N - 1 - 회전하기 전 행 번호

이러한 규칙을 코드로 나타내면 다음 코드와 같다.

3-1. 리스트를 시계방향으로 90도 회전하는 일반적인 방법

def rotated(array_2d):
    n = len(array_2d) # 행 길이
    m = len(array_2d[0]) # 열 길이 
    result = [[0] * n for _ in range(m)] # 회전한 결과를 표시하는 배열

    for i in range(n):
        for j in range(m):
            result[j][n-1-i] = array_2d[i][j]
    return result

**3-2. zip()과 *(asterisk)를 사용해서, 90도 회전을 간단하게 구현하는 방법**

def rotated(array_2d):
    list_of_tuples = zip(*array_2d[::-1])
    return [list(e) for e in list_of_tuples]

위 코드의 자세한 동작과정은 다음과 같다.

1. 배열을 역순으로 바꾼다.

array_2d = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

reversed_ = array_2d[::-1]
print(reversed_)
# [[7, 8, 9], [4, 5, 6], [1, 2, 3]]

2. 2차원 배열의 인자를 별표(*, Asterisk)로 unpacking하고 zip()으로 묶어준다.

unpacking은 괄호 안에 있던 데이터들을 풀어 각각으로 만들어 준다.
zip()은 각 인자들을 tuple로 묶어 zip object로 반환한다.

list_of_tuples = zip(*array_2d[::-1])
print(list_of_tuples)
# <zip object at 0x7f16a09c1540> -> (7, 4, 1), (8, 5, 2), (9, 6, 3)

3. tuple로 반환되는 요소를 리스트로 바꾸어준다.

return [list(e) for e in list_of_tuples]
# [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

4. 해싱 함수 직접 구현하기 (polynomial rolling method)

# 문자를 아스키 코드로 바꿔서, polynomial_hash를 직접 구현한다
def polynomial_hash(str):
    p = 31 # 메르센 소수
    m = 1_000_000_007 # 버킷 크기
    hash_value = 0
    for char in str:
        hash_value = (hash_value * p + ord(char)) % m
    
    print(hash_value)
    return hash_value

5. 크루스칼 알고리즘

def find(parent, x):
    # 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x: # 루트 노드는 부모 노드가 자신의 번호와 같다
        parent[x] = find(parent, parent[x])

    return parent[x]


# 두 원소가 속한 집합을 합친다
def union(parent, a, b):
    root_a = find(parent, a)
    root_b = find(parent, b)

    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b


# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

for i in range(1, v + 1): # 처음에는 부모 테이블을 자기 자신으로 초기화
    parent[i] = i

# 간선에 대한 정보를 입력받고, 비용순으로 정렬
for i in range(e):
    a, b, cost = map(int, input().split())

    edges.append((cost, a, b))

edges.sort()

# 간선을 하나씩 확인하면서, 사이클이 발생하지 않는 경우에만 집합에 포함
for cost, a, b in edges:
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        result += cost

print(result)

6. 위상 정렬

from collections import deque

v, e = map(int, input().split())

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)

# 각 노드에 연결된 간선 정보를 담기 위해, 연결 리스트 초기화
graph = [[] for i in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    # b의 진입차수를 1 증가
    indegree[b] += 1

# 위상 정렬 함수
def topoloy_sort():
    result = [] # 결과를 담을 리스트
    dq = deque()

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            dq.append(i)

    while dq:
        now = dq.popleft()

        result.append(now)

        # 해당 원소와 연결된 노드들의 진입차수를 1씩 빼기
        for next in graph[now]:
            indegree[next] -= 1

            if indegree[next] == 0:
                dq.append(next)

    for i in result:
        print(i, end=" ")

topoloy_sort()

7. 소수 알고리즘 2가지

7-1) 특정한 수 하나가 소수인지 판별하고 싶을 때

import math

# 딱 한개의 수를 위한 소수 판별 함수
def is_prime_num(x):
    # 2부터 ~ x의 제곱근까지 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어지면, 소수가 아니다
        if x % i == 0:
            return False
    
    return True

print(is_prime_num(4)) # False
print(is_prime_num(7)) # True

7-2) 여러 개의 수가 소수인지 아닌지 판별하고 싶을 때 -> 에라토스테네스의 체

import math

n = 1000 # 2 ~ 1000까지의 모든 수에 대하여 소수 판별

# 처음에는 0과 1을 제외한 모든 수가 소수(True)인 것처럼 초기화
array = [True for i in range(n + 1)] 

# 에라스토스테네스의 체
for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True: # i가 소수인 경우(= 남은 수인 경우)
        # i를 제외한, i의 모든 배수를 지운다
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

※ 시간 복잡도는 O(NloglogN) 으로 거의 O(N)일 정도로 빠르지만,

메모리가 많이 필요하다는 단점이 있으므로, N이 1,000,000 (백만) 이내로 주어진다면 사용할 만하다.

8. 투 포인터 (Two Pointers) 알고리즘

리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

투 포인터 알고리즘을 활용하여 풀 수 있는 대표적인 문제로는 "특정한 합을 가지는 부분 연속 수열 찾기" 가 있다.

1) 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.

2) 현재 부분합이 M과 같다면 -> 카운트한다.

3) 현재 부분합이 M보다 작으면 -> end를 1 증가시킨다.

4) 현재 부분합이 M보다 크거나 같으면 -> start를 1 증가시킨다.

5) 모든 경우를 확인할 때까지, 2 ~ 4번까지의 과정을 반복한다.

※ 단, 이러한 투 포인터 알고리즘 구현은 -> 리스트 원소 중에 음수 데이터가 있다면, 문제를 해결할 수 없다!

예를 들어, arr = [1, 2, 3, 2, 5] 이고 M = 5라면

N = 5 # 데이터의 개수 N
M = 5 # 찾고자 하는 부분합 M

arr = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며, 반복
for start in range(N):
    # end를 가능한만큼 이동시킨다
    while interval_sum < M and end < N:
        interval_sum += arr[end]
        end += 1
    
    # 부분합이 m일 때 카운트 증가
    if interval_sum == M:
        count += 1
    interval_sum -= arr[start]

print(count) # 3

이 외에도 투 포인터 알고리즘은 "정렬되어 있는 두 리스트의 합집합" 같은 문제에도 효과적이다.

이 문제에서는 이미 "정렬되어 있는 2개의 리스트"가 입력으로 주어진다.

이때 두 리스트의 모든 원소를 합쳐서 정렬된 결과를 계산하는 것이 문제의 요구사항이다.

1) 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리킨다.

2) 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리킨다.

3) A[i]와 B[j] 중에서 더 작은 원소를 -> 결과 리스트에 담는다.

4) 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지, 2 ~ 4번의 과정을 반복한다.

# 사전에 정렬된 리스트 A와 B 선언
N, M = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

result = [0] * (N + M)
i = j = k = 0

# 모든 원소가 결과 리스트에 담길 때까지 반복한다
while i < N or j < M:
    # 리스트 B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때
    if j >= M or (i < N and a[i] <= b[j]):
        # 리스트 A의 원소를 result로 옮긴다
        result[k] = a[i]
        i += 1
    # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
    else:
        # 리스트 B의 원소를 result로 옮긴다
        result[k] = b[j]
        j += 1
    
    k += 1

print(*result) # 1 2 3 4 5 6 8

9. 구간 합 계산

구간 합 계산을 위해 가장 많이 사용되는 기법이 바로 접두사 합(Prefix Sum)이다.

각 쿼리에 대해 구간합을 빠르게 계산하기 위해서는, N개의 수의 위치 각각에 대해여 접두사 합을 미리 구해 놓으면 된다.

접두사 합 : 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것

1) N개의 수에 대하여 접두사 합을 계산하여, 배열 P에 저장한다.

2) 매 M개의 쿼리 정보 [L, R]가 들어오면, 구간 합은 P[R] - P[L - 1] 이다.

# 데이터의 개수 N과 전체 데이터 선언
N = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산, 만약 쿼리가 [3, 4] 였다면?
print(prefix_sum[4] - prefix_sum[2]) # 70

'알고리즘과 코딩 테스트 > 파이썬 문법' 카테고리의 다른 글

기초 (0)	2023.02.03