Algorithm

소수의 판별

import math

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

print(prime(4))
print(prime(7))

False
True

int(math.sqrt(23))

에라토스테네스의 체

주어진 자연수 중 소수인 것만 골라내기

import math

n = 1000
array = [True for i in range(n+1)]

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
            
for i in range(2,n+1):
    if array[i]:
        print(i,end = ' ')

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

투 포인터

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

특정한 합을 가지는 부분 연속 수열 찾기

1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.

2. 현재 부분합이 M과 같다면 count한다.

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

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

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

n = 6 # 데이터 개수
m = 5 # 찾고 싶은 부분합
data = [1,3,2,3,4,5]

count = 0
interval_sum = 0
end = 0

for start in range(n):
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end+=1
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
    
print(count)

정렬되어 있는 두 리스트의 합집합

1. 정렬된 리스트 A와 B를 입력받는다.

2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.

3. 리스트 B에서 처리되지 않은 원소 중 가장 작은 우너소를 j가 가리키도록 한다.

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

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

n, m = 3,4
a = [2,7,4]
b = [4,8,1,7]
c = sorted(a)
d = sorted(b)

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

while i < n or j < m:
    if j >= m or (i < n and c[i] <= d[j]):
        result[k] = c[i]
        i += 1
    else:
        result[k] = d[j]
        j += 1
    k += 1
    
for i in result:
    print(i,end = '')

구간 합 계산

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

2. 매 M개의 Query 정보 \([L,R]\)을 확인할 때, 구간 합은 \(P[R] - P[L-1]\)이다.

n = 5
data = [10,20,30,30,3,10,2]

sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)
    
left = 3
right = 4
print(prefix_sum[right])
print(prefix_sum[left - 1])
print(prefix_sum[right] - prefix_sum[left - 1])

90
30
60

순열과 조합

순열

import itertools

data = [2,3,4]

for x in itertools.permutations(data,2):
    print(list(x))

[2, 3]
[2, 4]
[3, 2]
[3, 4]
[4, 2]
[4, 3]

조합

import itertools

data = [2,4,5,2]

for x in itertools.combinations(data,2):
    print(list(x),end = '')

[2, 4][2, 5][2, 2][4, 5][4, 2][5, 2]