1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
에라토스테네스의 체
-> 소수를 판별하는 알고리즘
체로 치듯이 수를 걸러내서 '에라토스테네스의 체'라고 불림,
2 ~ N의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않는 숫자를 소수로 판별하는 방식
숫자마다 일일이 약수가 있는 검사X
이미 지워진 숫자는 바로 건너뜀, 실행시간이 매우 짦음
특정 범위에서 모든 소수를 찾을 때 제일 효율적인 알고리즘
시간 복잡도는 O(N log long N)
특정 숫자에서의 소수 판별은 그냥 2 ~ 루트 N까지의 for문을 돌리면서 특정 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.
구현(파이썬)
n = int(input())
# 체크리스트를 만들어야한다. 범위는 n+1로 왜냐면 저거 인덱싱으로 푸는 거임
lst = [0]*(n+1)
count = 0
for i in range(2,int(math.sqrt(n)+1)):
for j in range(i+1,n+1): # i 뒤에서 시작한다.
if(j%i==0):
lst[j]+=1 # 나누어 지면 체크
for i in range(2,len(lst)):
if lst[i]==0:
print(i,end=" ")
이분탐색 & 결정 알고리즘
이분탐색
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- start, middle, end 3가지 포인터 변수를 지정하여 원하는 데이터를 찾는다.
- O(logN)의 시간 복잡도를 가진다.
구현(파이썬)
n , m = map(int,input().split())
lst = list(map(int,input().split()))
# # 이거 내림차순으로 바꾸는 거
# lst.sort(reverse=True)
lst.sort()
print(lst)
s = 0
e = len(lst) - 1
while s<=e:
middle = (s+e)//2
if lst[middle] < m:
print(lst[middle])
s = middle + 1
elif lst[middle] > m:
print(lst[middle])
e = middle - 1
else:
break
# 몇 번째냐고 했으니까 플러스 1 해줘라
print(middle+1)
결정 알고리즘
- Parametric Search(파라매트릭 서치)
- 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다.
- 이진탐색에 사용했던 패턴을 기반으로 한다.
예제) 랜선자르기(결정알고리즘)
엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이
다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을
잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면
20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의
랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수
길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때
만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
구현(파이썬)
n, m = map(int,input().split())
lst = []
for _ in range(n):
lst.append(int(input()))
# print(lst)
# 결정 알고리즘에서 이분 탐색을 사용한다.
# 결정 알고리즘 -> 최댓값과 1을 잡고 이분 탐색 하기
# 들어오는 최댓값과 1로 시작해서 중간값으로 나눈 몫들의 합을 비교한다.
start = 1
last = max(lst) # 이게 더 낫다 이걸 쓰자 이건 n 밖에 안 걸림
# min max 활용 잘하자 파이썬은 이런 거 많다.
while start <= last:
# 미드 포인트 잡고
middle = (start + last)//2
# 먼저 갯수를 셉시다.
num = 0
for i in lst:
left = i//middle
num+=left
# 갯수로 판별해서 미들을 옮기자
if num < m:
last = middle - 1
elif num > m:
start = middle + 1
else:
break
print(middle)