9. 코딩테스트에서 자주 출제되는 기타 알고리즘

💡 동빈나 님의 이코테 2021 강의 몰아보기 를 보면서 공부한 내용을 정리하고 있습니다. 더 자세한 내용은 이것이 취업을 위한 코딩 테스트다 with 파이썬 을 참고해주세요 😊 학습 도구로는 리플렛 을 사용하고 있고 원본 소스코드는 동빈님의 Github 에서 확인할 수 있고 스스로 공부한 소스코드는 Github 에서 확인할 수 있습니다.

소수

  • 소수 : 1보다 큰 자연수 중에서 1과 자기 자신으로만 나누어 떨어지는 자연수

    • 6 : 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니다.

    • 7 : 1과 7만으로만 나누어 떨어지므로 소수이다.

  • 어떤 자연수가 소수인지 아닌지 판별해야하는 문제가 자주 출제됨

# 소수판별하기

def is_prime_number(number):
  if number == 1:
    return True
  
  for i in range(2, number-1):
    if number % i == 0:
      return False
  
  return True

print(is_prime_number(4), is_prime_number(7))

소수 알고리즘의 성능분석

  • 2부터 X-1까지의 모든 자연수에 대하여 연산을 수행해야한다.

  • 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X)

  • 확인하고자 하는 수가 커질수록 시간이 더 많이 걸리게 된다.

    • 예) 10억

약수의 성질 이용하여 시간복잡도 줄이기

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

    • 예를 들어 16의 약수는 1, 2, 4, 8, 16

    • 이때 2 * 8 = 16 의 경우는 8 * 2 = 16과 대칭을 이룬다.

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

    • 예를 들어서 16이 2로 나누어떨어진다면 8로도 나누어 떨어진다는 것을 의미함

import math 

def is_prime_number(num):
  if num == 1:
    return True
  
  for i in range(2, int(math.sqrt(num))+1):
    if num % i == 0:
      return False

    return True

print(is_prime_number(4), is_prime_number(7))
# False True

제곱근 특성을 이용했을 때 시간복잡도

  • 2 부터 X의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대하여 연산을 수행해야 한다.

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

다수의 소수판별

  • 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할때

    • 에라토스테네스의 체 알고리즘을 이용한다.

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

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

  • N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

  • 구체적인 동작과정

    1. 2부터 N까지의 모든 자연수를 나열한다.

    2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

    3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)

    4. 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

자세한 설명보기

  1. 2부터 26까지 나열하기

  2. 아직 처리되지 않은 수 중에서 가장 작은 수 2를 선택한다.

  3. 2의 배수를 모두 제거한다. (2는 제외)

  4. 3을 선택하고 3의 배수를 모두 제거한다.

  5. 5를 선택 후 5 배수를 모두 제거

  6. 최종적으로는 2, 3, 5, 7, 11, 13, 19, 23 이 남게 된다.

여기서도 약수의 특성을 이용할 수 있다. 수의 범위가 26까지이므로 제곱근인 5까지만 확인하면 모든 수들을 알 수 있게 된다.

import math

n = 10000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n+1))):
  if array[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)

  • 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.

    • 각 자연수에 대해 소수 여부를 저장해야하므로 메모리가 많이 필요함

    • 10억이 소수인지 아닌지를 판별해야할 때 에라토스테네스의 체를 사용할 수 있을까?

  • 메모리측면에서 비효율적으로 동작할 수 있다.

투 포인터

  • 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

  • 2, 3, 4, 5, 6, 7번 학생을 지목해야할 때 2번부터 7번까지의 학생이라고 부르곤 하는데

  • 리스트에 담긴 데이터에 순차적으로 접근해야할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

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

  • N개의 자연수로 구성된 수열

  • 합이 M인 부분 연속 수열의 개수를 구하라!

  • 수행 시간 제한은 O(N)

  • 예시

    • {1, 2, 3, 2, 5} 수열이 존재할 때, 합이 5인 부분 연속 수열의 개수를 구하기

      • 2, 3

      • 3, 2

      • 5

투 포인터 활용한 해결 아이디어

자세한 설명 보기

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

  2. 현재 부분 합이 M과 같다면 카운트 한다.

  3. 현재 부분합이 M보다 작다면 end 를 1 증가시킨다.

  4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.

  5. 모든 경우를 확인할 때까지 2번부터 4번의 과정을 반복한다.

예를 들면, M = 5 이고 수열이 = {1, 2, 3, 2, 5} 일때

  1. 시작 1, 끝 1, 합 1, 카운트 0

  2. 시작 1, 끝 2, 합 3, 카운트 0

  3. 시작 1, 끝 3, 합 6, 카운트 0

  4. 시작 2, 끝 3, 합 5, 카운트 1

  5. 시작 3, 끝 3, 합 3, 카운트 1

  6. 시작 3, 끝 2, 합 5, 카운트 2

  7. 시작 2, 끝 2, 합 2, 카운트 2

  8. 시작 2, 끝 5, 합 7, 카운트 2

  9. 시작 5, 끝 5, 합 5, 카운트 3

  10. 종료

n = 5
m = 5
data = [1, 2, 3, 2, 5]

end = 0
interval_sum = 0
count = 0

for start in range(n):
  while interval_sum < m and end < n:
    interval_sum += data[end]
    end += 1

  if interval_sum == m:
    count += 1
  
  interval_sum -= data[start]

print(count)
# 3

구간 합

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

  • 예를 들어서 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}

    • 두번째 - 4번째 : 20+30+40 = 90

구간 합 빠르게 계산하기 문제

  • N개의 정수로 구성된 수열이 존재

  • M개의 쿼리 정보가 주어진다.

    • 각 쿼리는 left, right로 구성된다.

    • 각 쿼리에 대해서 [left, right] 구간에 포함된 데이터들의 합을 출력해야한다.

  • 수행시간 제한은 O(N+M) 이다.

구간 합 빠르게 계산하기 해결

  • 접두사 합 : 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

  • N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다.

  • 매 M개의 쿼리정보를 확인할 때 구간 합은 p[right] - p[left-1] 이다.

  1. left = 1, right = 3 -> p[3]-p[0] = 60

  2. left = 2, right = 5 -> p[5]-p[1] = 140

  3. left = 3, right = 4 -> p[4]-p[2] = 70

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

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

left = 3
right = 4

print(prefix_sum[right] - prefix_sum[left-1])
# 70
Previous8. 기타 그래프 이론Next10. 개발형 코딩테스트

Last updated