[동빈나]이코테 2021 강의 몰아보기 (13)(2021.1.16)

본 내용은 해당 강의 토대로 작성

기타 알고리즘

1. 소수 (Prime Number)

• 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))

• O(X) 시간 복잡도

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭
• 가운데 약수(제곱근)까지만 확인하면 된다.

개선된 알고리즘

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))

• O(N^1/2) 시간 복잡도

2. 에라토스테네스의 체

• 특정한 수의 범위 안에 존재하는 모든 소수를 찾을 수 있다.
• 다수의 자연수에 대해서 소수 여부를 판별
• N보다 작거나 같은 모든 소수를 찾음

동작 과정

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

동작 예시

1. 2부터 26까지의 모든 자연수를 나열 (N - 26)

2	3	4	5	6
7	8	9	10	11
12	13	14	15	16
17	18	19	20	21
22	23	24	25	26

2. 아직 처리하지 않은 가장 작은 수 2를 제외한 2의 배수 모두 제거

###

2	3		5
7		9		11
	13		15
17		19		21
	23		25

3. 3의 배수 모두 제거

2	3		5
7				11
	13
17		19
	23		25

4. 5의 배수 모두 제거

2	3
7				11
	13
17		19
	23

5. 최종 결과

2	3
7				11
	13
17		19
	23

위의 약수의 성질을 이용해서, 제곱근(5)가지만 수행하여도 구할 수 있다.

에라토스테네스의 체 알고리즘

import math
n = 1000 # 2 부터 1,000까지의 모든 수에 대해서 소수 판별
# 처음엔 모든 수가 소수(True)인 것을 초기화(0, 1 제외)
array = [True for i in range(n + 1)]

# 에라토스테네스의 체 알고리즘 수행
# 2부터 n의 제곱근까지의 모든 수를 확인
for i in range(2, int(math.sqrt(n)) + 1):
  if array[i] == True: # i가 소수인 경우(남은 수인 경우)
      # 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=' ')

에라토스테네스의 알고리즘 성능 분석

• 사실상 선형 시간에 가까울 정도로 매우 빠름
  • O(NloglogN)
• 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용
• 하지만, 각 자연수에 대한 소수 여부를 저장해야하므로 메모리가 많이 요구 된다.

4. 투 포인터 (Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 데이터의 범위를 표현

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

문제 설명

• N개의 자연수로 구성된 수열
• 합이 M인 부분 연속 수열의 개수를 구하여라
• 수행 시간은 O(N)

문제 해결 아이디어

• 투 포인터를 활용하여 문제를 해결한다.
  1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
  2. 현재 부분 합이 M과 같다면, 카운트한다.
  3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
  4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

예시

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

s
1	2	3	2	5
e

M = 5

부분합: 1

현재 카운트: 0

2. 이전 단계의 부분합이 M보다 작으므로 end 1증가

s
1	2	3	2	5
	e

M = 5

부분합: 3

현재 카운트: 0

3. end 1 증가

s
1	2	3	2	5
		e

M = 5

부분합: 6

현재 카운트: 0

4. 이전 부분합이 M보다 크므로 start 1 증가

	s
1	2	3	2	5
		e

M = 5

부분합: 5

현재 카운트: 1

5. 이전 부분합이 5이므로 start 1 증가

		s
1	2	3	2	5
		e

M = 5

부분합: 3

현재 카운트: 1

6. 위 과정을 반복하면 총 카운트는 3이다.

투 포인터 알고리즘

n = 5 # 데이터의 개수 N
m = 5 # 찾을 부분합 M
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)

5. 구간 합 (Interval sum)

• 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산

문제 설명

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

문제 해결 아이디어

• 접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것
• N개의 수 위치 각각에 대해서 접두사 합을 계산하여 P에 저장
• 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1]

	10	20	30	40	50
0	10	30	60	100	150
p[0]	p[1]	p[2]	p[3]	p[4]	p[5]

접두사 합 알고리즘

# 데이터의 개수 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])