소수 판별
소수란 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)까지 모든 자연수에 대하여 연산을 수행해야 하기 때문에
시간 복잡도는 이다.
약수의 성질
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
예를 들어, 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))특정 범위 안에 존재하는 모든 소수 찾기
에라토스테네스 알고리즘
다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘.
- 2부터 N까지의 모든 자연수를 나열한다
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다)
- 더 이상 반복할 수 없을 때까지 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)입니다.
아이디어
- 시작점과 끝점이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같으면, 카운트
- 현재 부분 합이 M보다 작으면, end 증가
- 현재 부분 합이 M보다 크거나 같다면, start 증가
- 모든 경우를 확인할 때까지 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))