Algorithms etc part1 (기타 알고리즘 파트1)

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

11. Algorithms ETC part1¶

Objective¶

1. Erathosthenes's Sieve (에라토스테네스의 체)
2. Two Pointers (투포인터 알고리즘)
3. 순열과 조합
4. 예시 문제

1. Erathosthenes's Sieve (에라토스테네스의 체)¶

1-1. 소수(Prime Number)¶

• 소수(Prime Number) 란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수 입니다.

1-2. 소수 판별 알고리즘¶

• 소수 판별 알고리즘 문제들이 자주 출제 됩니다.
• 하나의 수에 대해 소수 판별하는 알고리즘은 아래와 같습니다.
  • 첫번째 방법은 X를 2부터 X-1까지의 모든 수로 나누어 보는 것이며 시간 복잡도가 $O(X)$로서 비효율적입니다.
  • 두번째 방법은 X부터 X의 제곱근까지 수로 나누어보는 것이며 시간 복잡도가 $O(X^{1/2})$ 입니다.

1-3. Erathosthenes's Sieve (에라토스테네스의 체)¶

• 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘입니다.
• N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있습니다.
• 알고리즘의 다음과 같습니다.
  1. 2부터 N까지의 모든 자연수를 나열합니다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은수 i를 찾습니다.
  3. 남은 수중에서 i의 배수를 모두 제거합니다. (i는 제거하지 않습니다.)
  4. 더 이상 반복할 수 없을 때까지 2,3 과정을 반복합니다. (이때 N의 제곱근 까지만 증가시켜 확인해 주면 됩니다.)
• 시간 복잡도는 $O(NloglogN)$ 이며 사실상 선형 시간에 동작할 정도로 빠릅니다.
• 다만 메모리를 많이 차지하기 때문에 10억이 소수인지 찾아야 하는 문제에서는 에라토스테네스의 체를 이용하기 어렵습니다.
• 따라서 N이 1,000,000 이내로 주어지는 경우가 많습니다.

In [3]:

def check_prime(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

import math

def check_prime_2(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

In [4]:

print(check_prime(4))
print(check_prime(7))
print(check_prime_2(4))
print(check_prime_2(7))

False
True
False
True

In [6]:

import math

# 에라토스테네스의 체 구현 1
def sieve_1(n):
    array = [True for i in range(n+1)]
    array[0] = False
    array[1] = False
    
    for i in range(2, int(math.sqrt(n)+1)):
        if array[i] == True:
            j = 2
            while i*j<=n:
                array[i*j] = False
                j += 1
    return array

# 에라토스테네스의 체 구현 2
def sieve_2(n):
    sieve = [True] * n
    sieve[0] = False
    sieve[1] = False
    
    for i in range(2, int(math.sqrt(n)+1)):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return sieve

In [7]:

array = sieve_1(100)
for index, value in enumerate(array[:10]):
    print(f'{index} is prime : {value}')

0 is prime : False
1 is prime : False
2 is prime : True
3 is prime : True
4 is prime : False
5 is prime : True
6 is prime : False
7 is prime : True
8 is prime : False
9 is prime : False

In [8]:

array2 = sieve_2(100)
for index, value in enumerate(array2[:10]):
    print(f'{index} is prime : {value}')

0 is prime : False
1 is prime : False
2 is prime : True
3 is prime : True
4 is prime : False
5 is prime : True
6 is prime : False
7 is prime : True
8 is prime : False
9 is prime : False

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

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 을 의미합니다.
• 리스트에 담긴 데이터를 순차적으로 접근해야 할 때, 시작점 과 끝점 2개의 점으로 접근할 데이터 범위를 표현 할 수 있습니다.

2-1. '특정합을 가지는 부분 연속 수열 찾기'¶

• 양의 정수로만 구성된 리스트가 주어졌을때, 그 부분 연속 수열 중에서 '특정한 합'을 같는 수열의 개수를 출력하는 문제입니다.
• 투 포인터 사용
• 알고리즘은 다음과 같습니다.
  1. 시작점(start)과 끝점(end)가 첫번째 원소의 인덱스(0)를 가리키도록 합니다,
  2. 현재 부분합이 M과 같다면 카운트합니다.
  3. 현재 부분합이 M보다 작으면 end를 1 증가 시킵니다.
  4. 현재 부분합이 M보다 크거나 같으면 start를 1 증가 시킵니다.
  5. 모든 경우를 확인할때까지 2번 ~ 4번의 과정을 반복합니다.

In [17]:

def find_sequence(arr, m):
    n = len(arr)
    cnt = 0
    interval_sum = 0
    end = 0
    
    for start in range(0, n):
        
        while interval_sum < m and end < n:
            interval_sum += arr[end]
            end += 1
        
        if interval_sum == m:
            cnt += 1
        interval_sum -= arr[start]
                
    return cnt

print(find_sequence([1,2,3,2,5], 5))

3

2-2. '정렬되어 있는 두 리스트의 합집합'¶

• 이미 정렬되어 있는 2개의 리스트가 입력으로 주어지며, 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산 하는 것이 문제입니다.
• $O(N+M)$ 를 요구합니다. N, M은 주어진 두 리스트의 크기입니다.
• 알고리즘은 다음과 같습니다.
  1. 정렬된 리스트 A 와 B를 입력받습니다.
  2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 합니다,
  3. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 합니다.
  4. A[i], B[j] 중 에서 더 작은 원소를 결과 리스트에 담습니다.
  5. 리스트 A와 B 에서 더 이상 처리할 원소가 없을 때까지 2 ~ 4 번까지의 과정을 반복합니다.

In [44]:

def union_lst(a,b):
    n, m = len(a), len(b)
    result = [0] * (n + m)
    i, j, k = 0, 0, 0
    
    while i < n or j < m:
        if j == m or (i < n and a[i] < b[j]):
            result[k] = a[i]
            i += 1
            k += 1
        elif i==n or (j < m and a[i] >= b[j]):
            result[k] = b[j]
            j += 1
            k += 1
            
    return result

In [45]:

a = [1,3,5]
b = [2,4,6,8]

print(union_lst(a,b))

[1, 2, 3, 4, 5, 6, 8]

2-3. '구간 합 계산'¶

• 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제입니다.
• M개의 쿼리에 대해, 매번 구간합을 계산하면 $O(MN)$ 시간 복잡도를 가집니다.
• 구간 합계산을 위해 가장 많이 사용되는 기법이 Prefix Sum (접두사 합) 입니다.
• 접두사 합이란 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미합니다.
• Prefix Sum 을 활용시 M개 쿼리에 대한 구간 합의 시간복잡도는 $O(M+N)$ 입니다.
• 알고리즘은 다음과 같습니다.
  1. N개의 수에 대하여 접두사 합(Prefix)을 계산하여 매열 P에 저장합니다.
  2. 매 M개의 쿼리 정보 [L,R] 을 확인할 때, 구간 합은 P[R] - L[L-1] 입니다.

In [49]:

def prefix_sum(data, left, right):
    prefix_sum = [0]
    sum_value = 0
    
    for i in data:
        sum_value += i
        prefix_sum.append(sum_value)
        
    return prefix_sum[right] - prefix_sum[left-1]

data = [10,20,30,40,50]
print(prefix_sum(data,3,4))

70

3. 순열과 조합¶

• 순열(Permutation) 이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것을 의미한다.
• 조합(Combination) 이란 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것을 의미한다.

In [60]:

from itertools import combinations, permutations

data = [1,2]
per = list(permutations(data,2))
print(per)


data2 = [1,2,3,4]
for x in list(combinations(data2,3)):
    print(x)

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

4. 예시 문제¶

4-1. 소수 구하기¶

• https://github.com/ndb796/python-for-coding-test 참고
• https://www.acmicpc.net/problem/1929
• 에라토스테네스의 체

In [75]:

import math


def sieve(n, m):
    arr = [True] * (n+1)
    arr[0] = False
    arr[1] = False
    
    for i in range(2, int(math.sqrt(n))+1):
        if arr[i] == True:
            for j in range(i+i, n+1, i):
                arr[j] = False
       
    result = []
    for i in range(m, n+1):
        if arr[i]:
            result.append(i)
    return result

In [76]:

m, n = map(int, input().split())
print(sieve(n, m))

3 16
[3, 5, 7, 11, 13]

4-2. 암호 만들기¶

• https://github.com/ndb796/python-for-coding-test 참고
• https://www.acmicpc.net/problem/1759
• 조합

In [90]:

from itertools import combinations

def get_candid(str_lst, l):
    vowels = {'a','i','o','u','e'}
    str_lst.sort()
    cand_lst = list(combinations(str_lst, 4))
    
    for cand in cand_lst:
        
        cnt = 0
        for element in cand:
            if element in vowels:
                cnt += 1
        if cnt >= 1 and l-cnt >=2:
            print(''.join(cand))
    

In [92]:

l, c = map(int, input().split())
str_lst = list(map(str, input().split()))
get_candid(str_lst, l)

4 6
a t c i s w
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw