기타 알고리즘

소수 판별

소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수이다.

• 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니다.
• 7은 1, 7(자기 자신)을 제외한 자연수로 나누어떨어지지 않기 때문에 소수이다.

python으로 구현한 소수 판별(기본)

def isPrimeNum(x) :
    for i in range(2, x) :
        # 2 ~ (x-1) 중 나누어 떨어지는 수가 있으면 소수가 아님
        if(x % i == 0) :
            return False
        return True

print(isPrimeNum(4))
print(isPrimeNum(7))

➡️ 2부터 (x-1)까지 모든 자연수에 대하여 연산을 수행해야 하기 때문에
시간 복잡도는 $O(X)$ 이다.

약수의 성질
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.

예를 들어, 16의 약수는
1 2 4 8 16 --> (1, 16), (2, 8)은 대칭이다.

따라서 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다.

python으로 구현한 소수 판별(개선) - 약수의 성질

import math

def isPrimeNum(x) :
    # math 라이브러리를 굳이 사용하지 않아도 된다.
    # for i in range(2, int(math.sqrt(x)) + 1) :
    
    # x의 제곱근까지만 실행
    for i in range(2, int(x**(1/2)) + 1) :
        if(x % i == 0) :
            return False
        return True

print(isPrimeNum(4))
print(isPrimeNum(7))

---

특정 범위 안에 존재하는 모든 소수 찾기

에라토스테네스 알고리즘

다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘.

1. 2부터 N까지의 모든 자연수를 나열한다
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2. 3. 과정을 반복한다.

에라토스테네스 알고리즘 구현 :

#include <iostream>
#include <cmath>

using namespace std;

void Eratosthenes(int n, bool* arr) {
    for (int i = 2; i <= sqrt(n); i++)
    {
        // 남은 수를 제외한 남은수의 배수들 지우기(false 만들기)
        if(arr[i]) {
            int j = 2;
            while(i * j <= n) {
                arr[i * j] = false;
                j += 1;
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if(arr[i]){
            cout << i << " ";
        }
    }
}

int main(void){

    // 2 ~ 1,000까지 소수의 개수 구하기
    int n = 1000;

    // 2 ~ 1,0000 True로 초기화 (True : 소수, False : 소수 아님)
    bool* arr = new bool[n+1];
    memset(arr, true, n+1 * sizeof(bool));

    Eratosthenes(n, arr);


    return 0;
}

---

투 포인터(Two Pointers), 특정한 합을 가지는 부분 수열 찾기

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 위치를 기록하면서 처리하는 알고리즘

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

• N개의 자연수로 구성된 수열이 있습니다.
• 합이 M인 부분 연속 수열의 개수를 구하시오.
• 수행 시간 제한은 O(N)입니다.

아이디어

1. 시작점과 끝점이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분 합이 M과 같으면, 카운트
3. 현재 부분 합이 M보다 작으면, end 증가
4. 현재 부분 합이 M보다 크거나 같다면, start 증가
5. 모든 경우를 확인할 때까지 2. ~ 4. 과정 반복

문제 풀이

n = 5
m = 5 # 특정한 합
arr = [1, 2, 3, 2, 5]

cnt = 0
local_sum = 0
start, end = 0, 0

for start in range(n) :
    local_sum = arr[start]  
    while True :
        local_sum += arr[end]
        if start == end :
            local_sum -= arr[start]
        if end >= n :
            break
        elif m == local_sum :
            cnt += 1
            break
        elif local_sum < m :
            end += 1
        elif local_sum > m :
            break


print(cnt)

---

투 포인터(Two Pointers), 구간합 계산하기

구간 합(Inerval Sum) 문제 설명

• N개의 정수로 구성된 수열이 있다.
• M개의 쿼리 정보가 주어진다.
  각 쿼리는 Left와 Right로 구성된다.
  각 쿼리에 대하여 [Left, Right] 구간에 포함된 값들의 합을 출력해야 한다.
• 수행 시간 제한은 O(N + M) 이다.

아이디어
접두사 합(Prefix Sum) : 배열의 맨 앞부터 특정 위치까지 합을 미리 구해 놓는 것

• N개의 수 위치 각각에 대하여 접두사 합을 계산하여 배열 P에 저장한다.
• M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1]이다.

구간합 문제 풀이 :

n = 5

data = [10, 20, 30, 40, 50]

prefix_sum = 0
prefix = [0]
for i in data : 
    prefix_sum += i
    prefix.append(prefix_sum)

left, right = 1, 3
print(prefix[right] - prefix[left - 1])

---

순열 (Permutation)

순열이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것.

1, 2, 3에서 2개를 선택하여 나열
➡️ (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)

python의 iterools library을 사용하여 순열(Permutations)을 간단하게 구현할 수 있다.
단, permutations() 함수를 통해 결과는 list가 아니다. 따라서 list로 casting하여 결과를 받는 것이 일반적이다.

python의 iterools library의 permutations() 함수

import itertools

data = [1, 2, 3]

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

---

조합 (Combination)

조합이란 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하여 나열하는 것.

1, 2, 3에서 2개를 선택하여 나열
➡️ (1,2), (1,3), (2,3)

python의 iterools library을 사용하여 순열(Combination)을 간단하게 구현할 수 있다.
단, combinations() 함수를 통해 결과는 list가 아니다. 따라서 list로 casting하여 결과를 받는 것이 일반적이다.

python의 iterools library의 combination() 함수

import itertools

data = [1, 2, 3]

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