Algorithm - Two Pointer, 순열과 조합, 최소 공배수와 최대 공약수

투 포인터

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

 

예시

1. 특정 합을 가지는 부분 연속 수열 찾기
arr = [1, 2, 3, 2, 5]

tmp합이 원하는 합을 넘지 않고, end가 배열의 길이를 넘지 않는 범위를 반복하면서 tmp_sum에 값을 더해준다.

그리고 만약 원하는 값과 같다면 카운트를 해준다. tmp_sum에서 시작 인덱스의 해당 값을 빼주고 시작 인덱스를 바꾼 뒤 다시 반복

arr = [1, 2, 3, 2, 5]
n = len(arr)
m = 5	# 특정 값

ans = tmp_sum = end = 0

for start in range(n):
    while tmp_sum < m and end < n:
        tmp_sum += arr[end]
        end += 1
    if tmp_sum == m:
        ans += 1
    tmp_sum -= arr[start]
print(ans)

2. 정렬된 두 리스트의 합집합 결과
arr1 = [1, 3, 5]
arr2 = [2, 4, 6, 7]

각 배열의 길이를 넘지않는 범위만큼 반복을 진행하는데, j가 배열의 크기를 넘어섰거나 배열 1의 값이 배열 2의 값보다 작거나 같을 때 배열 1의 값을 result에 추가하고, 배열 1의 인덱스(i)를 증가시킨다. 그 외는 배열 2의 값을 result에 추가하고 j를 증가시키고 반복

arr1 = [1, 3, 5]
arr2 = [2, 4, 6, 7]
n, m = len(arr1), len(arr2)

result = [0] * (n + m)
i = j = k = 0

while i < n and j < m:
    if j >= m or (i <n and arr1[i] <= arr2[j]):
        result[k] = arr1[i]
        i += 1
    else:
        result[k] = arr2[j]
        j += 1
    k += 1

print(result)

 

순열과 조합

itertools 사용

from itertools import permutations, combinations

arr = [1, 4, 6, 7, 8]
# arr에서 3개의 원소를 골라 순서를 정해 나열
permutation = list(permutations(arr, 3))
# arr에서 3개의 원소를 골라 순서 없이 나열
combination = list(combinations(arr, 3))

 

반복문 (재귀) 사용

item = []
def permutation(arr, n):
    if len(item) == n:
        print(item)
        return

    for i in range(len(arr)):
        if arr[i] not in item:
            item.append(arr[i])
            permutation(arr, n)
            item.pop()

permutation([1, 3, 4], 2)

def combination(arr, n):
    item = []
    if n > len(arr):
        return item
    if n == 1:
        for i in arr:
            item.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for tmp in combination(arr[i + 1:], n - 1):
                item.append([arr[i]] + tmp)
    return item

print(combination([1, 4, 6, 2], 3))

 

 

최소공배수와 최대공약수

반복문

작은 수를 기준으로 1까지 역방향으로 반복을 하면서 a와 b 둘 다 i로 나누어 떨어지는 수가 최대공약수

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

 

유클리드 호제법

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

 

라이브러리

import math
math.gcd(a, b)

시간 차이 : 라이브러리 < 유클리드 호제법 < 반복문

 

최소공배수

def lcm(a, b):
    return a * b / gcd(a, b)