- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
소수(Prime Number)
-
소수란 1보다 큰 자연수 중에서, 1과 자기 자기자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수
- 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니다.- 7은 1과 1을 제외하고는, 나누어 떨어지지 않으므로 소수이다.
-
코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다.
-
소수의 판별: 기본적인 알고리즘
# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
# 2부터 (x - 1)까지의 모든 수를 확인하며
for i in range(2, x):
# x가 해당 수로 나누어 떨어진다면
if x % i == 0:
# 소수가 아님
return False
return True
print(is_prime_number(4))
print(is_prime_number(7))
import math
# 소수 판별 함수 (2이상의 자연수에 대하여)
def is_prime_number(x):
# 2부터 x의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(x)) + 1):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
# 소수가 아님
return False
return True
print(is_prime_number(4))
print(is_prime_number(7))
에라토스테네스의 체 알고리즘
- 다수의 자연수에 대하여 숫 여부를 판별할 때 사용하는 대표적인 알고리즘이다.
- 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.
- 에라토스테네스의 체 알고리즘의 구체적인 동작 과정은 다음과 같다.
import math
# 2부터 1,000까지의 모든 수에 대하여 소수 판별
n = 1000
# 처음에는 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
array = [True for i in range(n + 1)]
# 에라토스테네스의 체 알고리즘 수행
# 2부터 n의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(1000)) + 1):
# i가 소수인 경우(남은 수인 경우)
if array[i] == True:
# i를 제외한 i의 모든 배수를 지우기
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=' ')
투 포인터(Two Pointers)
- 투 포인터 알고리즘은, 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
- 흔히 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때, 간단히 '2번부터 7번까지의 학생'이라고 부르고는 한다.
- 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.
- 특정한 합을 가지는 부분 연속 수열 찾기
# 데이터의 개수 N
n = 5
# 찾고자 하는 부분합 M
m = 5
# 전체 수열
data = [1, 2, 3, 2, 5]
count = 0
interval_sum = 0
end = 0
# start를 차례때로 증가시키며 반복
for start in range(n):
# end를 가능한 만큼 이동시키기
while interval_sum < m and end < n:
interval_sum += data[end]
end += 1
# 부분합이 m일 때 카운트 증가
if interval_sum == m:
count += 1
interval_sum -= data[start]
print(count)
구간 합(Interval Sum)
- 구간 합 문제: 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제
- 구간 합 빠르게 계산하기
# 데이터의 개수 N과 데이터 입력받기
n = 5
data = [10, 20, 30, 40, 50]
# 접두사 합(Prefix Sum) 배열 계산
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] - prefix_sum[left - 1])
안녕하세요.