기타 알고리즘 - 1

Update: 2022.01.03 Updated: 2022.01.03

카테고리: Appendix

태그: 구간 합 소수의 판별 순열과 조합 에라토스테네스의 체 투 포인터 Python

1. 더 알아두면 좋은 알고리즘

소수의 판별

소수(Prime Number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다. 예를 들어 ‘6’은 1, 2, 3, 6으로 나누어떨어진다. 따라서 6은 소수가 아니다. 하지만 ‘7’은 1과 7을 제외하고는 나누어떨어지지 않는다. 그렇기 때문에 7은 소수이다. 또한 소수는 2보다 큰 자연수에 대하여 정의되므로, 1은 소수에 해당하지 않는다는 특징이 있다.

간혹 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 경우가 생긴다. 혹은 1부터 N까지의 모든 소수를 출력해야 하는 문제등이 출제될 수 있다. 그렇다면 가장 먼저 어떠한 수 X가 주어졌을 때 해당 수가 소수인지 아닌지를 판별하는 방법에 대해서 살펴보자. 가장 간단한 방법은 X를 2부터 X - 1까지의 모든 수로 나누어보는 것이다. 만약 2부터 X - 1까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 존재하면 X는 소수가 아니다.

# 소수 판별 함수
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))

False
True

이 코드의 실행 결과는 차례대로 False, Ture인 것을 확인할 수 있다. 4는 소수가 아니며, 7은 소수이기 때문이다. 시간 복잡도를 계산해보면 이 알고리즘의 시간 복잡도는 O(X)이다. 예를 들어 1,000,000이라는 수가 소수인지 확인해야 할 때는 1,000,000을 2부터 999,999까지의 모든 수에 대하여 하나씩 나누어야 한다. 따라서 이와 같이 알고리즘을 작성하면 몹시 비효율적이다.

이 알고리즘을 개선해서 하나의 수가 소수인지 판별하는 알고리즘을 O(X)보다 더 빠르게 동작하도록 작성할 수 있다. 자연수의 약수가 가지는 특징을 파악하고 있다면 그 원리를 쉽게 이해할 수 있다. 예를 들어 16이라는 수의 약수(Divisor)는 다음과 같다.

1, 2, 4, 8, 16

이때 모든 약수에 대하여, 가운데 약수를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

결과적으로 다음 5개의 등식이 성립하는 것을 확인할 수 있다.

1 x 16 = 16
2 x 8 = 16
4 x 4 = 16
8 x 2 = 16
16 x 1 = 16

여기에서 알 수 있는 점은 가운데 약수를 기준으로 해서 각 등식이 대칭적인 형태를 보인다는 것이다. 예를 들어 2 x 8 = 16은 8 x 2 = 16과 대칭이다. 그렇기 때문에 우리는 특정한 자연수 x가 소수인지 확인하기 위하여 바로 가운데 약수까지만 ‘나누어떨어지는지’ 확인하면 된다. 위의 예시에서는 4까지만 확인하면 된다. 즉, 2, 3, 4를 확인하여 나누어떨어지는지 확인한다. 다시 말해 제곱근까지만(가운데 약수까지만) 확인하면 된다는 점을 기억하자.

이해를 하기 위해 예시를 하나 더 확인해보자. 8이라는 수가 있을 때, 이 수의 약수는 다음과 같다.

1, 2, 4, 8

마찬가지로 약수를 앞뒤로 2개씩 묶으면 다음과 같다.

1 x 8 = 8
2 x 4 = 8
4 x 2 = 8
8 x 1 = 8

결과적으로 8도 마찬가지로 8의 제곱근까지만 확인하면 된다. 정확히는 8의 제곱은은 2.828…이므로 2까지만 확인하면 된다. 3부터는 확인할 필요가 없다. 따라서 다음과 같이 코드를 작성하면 시간 복잡도 O(X^1/2)에 소수를 판별할 수 있다.

import math

# 소수 판별 함수
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(X^1/2)인 것을 확인할 수 있다. 제곱근까지만 확인해도 된다는 점에서 시간 복잡도를 매우 많이 개선할 수 있다. 예를 들어 소수인지 아닌지 판별해야 되는 수가 1,000,000일 때는 반복문 상에서 2부터 1,000까지만 확인하면 되는 것 이다. 이렇게 우리는 하나의 수가 주어졌을 때, 그 수가 소수인지 아닌지 판별하는 알고리즘을 알 수 있었다. 하지만 하나의 수에 대해서 소수인지 아닌지 판별해야 하는 경우가 아니라 수의 범위가 주어졌을 때, 그 전체 수의 범위 안에서 존재하는 모든 소를 찾아야 하는 경우에는 느릴 수 있다.

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스의 체 알고리즘은 다음과 같다.

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

에라토스테네스의 체 알고리즘은 그림으로 쉽게 이해할 수 있다. 예를 들어 N = 26일 때를 확인해보자. 알고리즘에 따라서 가장 먼저 2부터 26까지의 모든 자연수를 나열한다. 그 뒤에 알고리즘을 수행하면 된다.

step 0 : 초기 단계에서는 다음과 같이 2부터 26까지의 모든 자연수를 나열한다.

step 1 : 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다. 따라서 2를 제외한 2의 배수는 모두 제외한다.

step 2 : 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다. 따라서 3을 제외한 3의 배수는 모두 제외한다.

step 3 : 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다. 따라서 5를 제외한 5의 배수는 모두 제외한다.

step 4 : 이어서 마찬가지로, 남은 수 중에서 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거하는 과정을 반복한다. 이 과정을 거쳐 남아 있는 수는 모두 소수이며, 이렇게 2부터 26까지의 모든 소수를 찾았다. 최종적인 결과는 다음과 같다.

에라토스테네스의 체 알고리즘을 이용하여 1부터 N까지의 모든 소수를 출력하는 프로그램을 작성하면 다음과 같다. 예제에서는 N = 1,000으로 설정하였다. 또한 매 스텝마다 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다고 하였으나, 이 때 i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 된다. 그리고 가끔씩 문제에서 1이 소수인지 판별해야 하도록 입력 주건이 주어질 수 있는데, 1은 소수가 아니므로 그런 경우에는 다음 소스코드에 array[1]의 값으로 False를 넣어주는 부분을 추가해주면 된다.

import math

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

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
  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)으로 사실상 선형 시간에 동작할 정도로 빠르다. 예를 들어 N = 1,000,000일 때 약 4 정도로 매우 작은 수이다.

이처럼 에타로스테네스의 체 알고리즘은 매우 빠르게 동작하기 때문에 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 다만, 메모리가 많이 필요하다는 단점이 있다. 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하기 때문이다. 예를 들어 N = 1,000,000일 때는 2부터 1,000,000까지의 모든 수에 대한 정보를 담을 수 있는 크기의 리스트가 필요하다. 또한 10억이 소수인지 찾아야 하는 문제에서는 에라토스테네스의 체를 이용하기 어렵다.

따라서 에라토스테네스의 체를 이용해야 되는 문제의 경우 N이 1,000,000 이내로 주어지는 경우가 많다. 그렇게 하면 이론상 400만 번 정도의 연산으로 문제를 해결할 수 있으며, 메모리 또한 충분히 처리할 수 있는 크기만큼만 차지하기 때문이다.

투 포인터

투 포인터(Two Pointer) 알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다. 예를 들어서 한 반에 학생이 40명 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때, 우리는 번호로 한명씩 부르기보다는 ‘2번 부터 7번까지의 학생’이라고 부를수도 있다. 이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 ‘시작점’과 ‘끝점’ 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

이러한 투 포인터 알고리즘을 이용하여 ‘특정한 합을 가지는 부분 연속 수열 찾기’문제를 풀어보자. ‘특정한 합을 가지는 부분 연속 수열 찾기 문제’는 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 ‘특정한 합’을 갖는 수열의 개수를 출력하는 문제이다. 예를 들어 다음과 같이 1, 2, 3, 2, 5를 차례대로 원소로 갖는 리스트가 주어져 있다고 해보자.

이때 합계 값을 5라고 설정하면 다음과 같은 3가지 경우의 수만 존재한다.

그러면 이 문제를 투 포인터 알고리즘을 이용하여 풀어보자. 투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이다. ‘특정한 합을 가지는 부분 연속 수열 찾기 문제’에서는 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록한다. 특정한 부분합을 M이라고 할 때, 구체적인 알고리즘은 다음과 같다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(O)를 가리키도록 한다.
1. 현재 부분합이 M과 같다면 카운트한다.
1. 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
1. 현재 부분합이 M보다 크거나 같으면 start를 1 증가시킨다.
1. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

구체적인 과정을 살펴보기 위하여, 위 알고리즘을 통해 부분합이 5인 부분 연속 수열의 수는 몇 개 인지 계산해보자.

step 0 : 알고리즘에 따라서 초기 단계에서는 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다. 이때 현재의 부분합은 1이므로 무시한다.

step 1 : 이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킨다. 현재 부분합은 3이므로 이번에도 마찬가지로 무시한다.

step 2 : 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다. 현재 부분합은 6이므로 이번에도 마찬가지로 무시한다.

step 3 : 이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킨다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트한다.

step 4 : 이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킨다. 현재 부분합은 3이므로 무시한다.

step 5 : 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트 한다.

step 6 : 이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킨다. 현재 부분합은 2이므로 무시한다.

step 7 : 이전 단계에서의 부분합이 2였기 때문에 end를 1 증가시킨다. 현재 부분합은 7이므로 무시한다.

step 8 : 이전 단계에서의 부분합이 7이었기 때문에 start를 1 증가시킨다. 현재 부분합은 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트한다.

결과적으로 카운트된 경우의 수는 3이다. 따라서 부분합이 5가 되는 부분 연속 수열의 개수를 3개인 것을 알 수 있다. 이러한 과정을 코드로 구현하면 다음과 같다. 투 포인터 알고리즘은 구현 가능한 방식이 매우 많다는 특징이 있다. 필자는 시작점(start)을 반복문을 이용하여 증가시키며, 증가할 때마다 끝점(end)을 그것에 맞게 증가시키는 방식으로 구현하였다. 이 문제를 투 포인터 알고리즘으로 해결할 수 있는 이유는 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 이동시키면 항상 합이 증가하기 때문이다. 만약에 리스트 낸 원소에 음수 데이터가 포함되어 있는 경우에는 투 포인터 알고리즘으로 문제를 해결할 수 없다.

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)

3

이 밖에도 투 포인터 알고리즘은 ‘정렬되어 있는 두 리스트의 합집합’같은 문제에 효과적으로 사용할 수 있다. 이 문제에서는 이미 정렬되어 있는 2개의 리스트가 입력으로 주어진다. 이때 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것이 문제의 요구사항이다.

이 문제를 풀기 위해서는 2개의 리스트 A, B가 주어졌을 때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키면 된다. 이 문제에서는 기본적으로 이미 정렬된 결과가 주어지므로 리스트 A와 B의 원소를 앞에서부터 확인하면 된다.

1. 정렬된 리스트 A와 B를 입력받는다.
1. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.
1. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다.
1. A[i]와 B[j] 중에서 더 작은 원소를 결과 리스트에 담는다.
1. 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2 ~ 4번의 과정을 반복한다.

이 알고리즘 또한 그림을 통해서 이해해보자.

step 0 : 초기 단계에서는 두 리스트의 모든 원소가 들어갈 수 있는 크기의 결과 리스트를 하나 생성한다. 또한 i가 리스트 A의 첫 번째 원소를 가리키도록 하고, j가 리스트 B의 첫 번째 원소를 가리키도록 한다.

step 1 : 현재 i와 j가 가리키고 있는 두 원소를 비교한다. A[i] = 1, B[j] = 2이다. A[i] < B[j]이므로 결과 리스트에 i가 가리키고 있는 원소를 담는다. 이후에 i를 1 증가시킨다.

step 2 : 현재 i와 j가 가리키고 있는 두 원소를 비교한다. A[i] = 3, B[j] = 2이다. A[i] > B[j]이므로 결과 리스트에 j가 가리키고 있는 원소를 담는다. 이후에 j를 1 증가시킨다.

step 3 : 현재 i와 j가 가리키고 있는 두 원소를 비교한다. A[i] = 3, B[j] = 4이다. A[i] < B[j]이므로 결과 리스트에 i가 기리키고 있는 원소를 담는다. 이후에 i를 1 증가시킨다.

step 4 : 현재 i와 j가 가리키고 있는 두 원소를 비교한다. A[i] = 5, B[j] = 4이다. A[i] > B[j]이므로 결과 리스트에 j가 가리키고 있는 원소를 담는다. 이후에 j를 1 증가시킨다.

step 5 : 현재 i와 j가 가리키고 있는 두 원소를 비교한다. A[i] = 5, B[j] = 6이다. A[i] < B[j]이므로 결과 리스트에 i가 가리키고 있는 원소를 담는다. 이후에 i를 1 증가시킨다.

step 6 : 이제 리스트 A에 있는 모든 원소가 결과 리스트에 담기게 되었다. 따라서 남은 리스트 B에 있는 모든 원소를 리스트에 담으면 된다. 따라서 먼저 j가 가리키는 원소를 결과 리스트에 담고, j를 1 증가시킨다.

step 7 : 이어서 리스트 B의 마지막 원소까지 결과 리스트에 담는다. 최정적으로 결과 리스트에는 두 리스트의 모든 원소가 정렬된 형태로 저장된 것을 확인할 수 있다.

결과적으로 정렬된 리스트 A와 B의 데이터 개수 각각 N, M이라고 할 때, 이 알고리즘의 시간 복잡도는 O(N + M)이 된다. 단순히 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문이다. 이 과정을 코드로 구현하면 다음과 같다.

# 사전에 정렬된 리스트 A와 B 선언
n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

# 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
result = [0] * (n + m)
i = 0
j = 0
k = 0

# 모든 원소가 결과 리스트에 담길 때까지 반복
while i < n or j < m:
  # 리스트 B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때
  if j >= m or (i < n and a[i] <= b[j]):
    # 리스트 A의 원소를 결과 리스트로 옮기기
    result[k] = a[i]
    i += 1
  # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
  else:
    # 리스트 B의 원소를 결과 리스트로 옮기기
    result[k] = b[j]
    j += 1
  k += 1

# 결과 리스트 출력
for i in result:
  print(i, end = '')

1 2 3 4 5 6 8

이 ‘정렬되어 있는 두 리스트의 합집합’알고리즘의 경우 병합 정렬(Merge Sort)과 같은 일부 알고리즘에서 사용되고 있다는 점까지 기억하자.

구간 합 계산

코딩 테스트나 알고리즘 대회의 앞부분 문제에서는 구간 합을 구해야 하는 문제가 종종 출제된다. 구간 합 문제란 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다. 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기에서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다.

이러한 구간 합 계산 문제는 여러 개의 쿼리(Query)로 구성되는 문제 형태로 출제되는 경우가 많다. 다수의 구간에 대해서 합을 각각 구하도록 요구된다. 예를 들어 M개으 쿼리가 존재한다고 가정해보자. 각 쿼리는 Left와 Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다. 결과적으로 M개의 쿼리가 주어졌을 때, 모든 쿼리에 대하여 구간의 합을 출력하는 문제가 전형적인 ‘구간 합 계산’문제이다.

만약 M개의 쿼리 각각, 매번 구간 합을 계산한다면 이 알고리즘은 O(NM)의 시간 복잡도를 가진다.

왜냐하면, M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 모두 계산하라고 요구(첫 번째 수부터 N번째 수까지)할 수도 있기 때문이다. 결과적으로 O(NM)의 시간 복잡도를 가지는 것이다.

그렇다면 N = 1,000,000이고, M = 1,000,000인 상황처럼 데이터의 개수가 매우 많을 때, O(NM)의 시간 복잡도로 동작하는 알고리즘으로는 문제를 해결할 수 없을 것이다.

항상 우리가 알고리즘을 설계할 떄 고려할 점은, 여러 번 사용될 만한 정보는 미리 구해 저장해 놓을수록 유리하다는 것이다. 확인해보면 쿼리는 M개이지만 N개의 수는 한 번 주어진 뒤에 변경되지 않는다. 따라서 N개의 수에 대해서 어떠한 ‘처리’를 수행한 뒤에 나중에 M개의 쿼리가 각각 주어질 때마다 빠르게 구간 합을 도출할 수 있도록 하면 어떨까?

구간 합 계산을 위해 가장 많이 사용되는 기법이 바로 접두사 합(Prefix Sum)이다. 각 쿼리에 대해 구간합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다. 여기에서 접두사 합이란 리스트의 맨 앞 부터 특정 위치까지의 합을 구해 놓은 것을 의미한다.

구체적으로 접두사 합을 이용하여 구간 합을 빠르게 계산하는 알고리즘은 다음과 같다.

구간 합 빠르게 계산하기 알고리즘

1. N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.
1. 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] - P[L - 1]이다.

예를 들어 다음과 같이 5개의 데이터가 있다고 해보자.

이 5개의 데이터에 대해서 접두사 합을 계산하면 다음과 같다.

위에서 설명한 알고리즘대로 매 쿼리가 들어왔을 때, P[R] - P[L - 1]을 계산하면 바로 구간 합을 구할 수 있게 된다. 따라서 매 쿼리당 계산 시간은 O(1)이 된다. 결과적으로 N개의 데이터와 M개의 쿼리가 있을 때, 전체 구간 합을 모두 계산하는 작업은 O(N + M)의 시간 복잡도를 가진다.

예를 들어 다음과 같이 쿼리 3개가 있다고 했을 때, 구간 합을 구하는 과정을 확인해보자.

1. 첫 번째 쿼리는 첫 번째 수부터 세 번째 수까지의 구간 합을 물어보는 [1, 3]이라고 해보자. 이 경우, P[3] - P[0] = 60이 답이 된다.
1. 두 번째 쿼리는 두 번째 수부터 다섯 번째 수까지의 구간 합을 물어보는 [2, 5]라고 해보자. 이 경우, P[5] - P[1] = 140이 답이 된다.
1. 세 번째 쿼리는 세 번째 수부터 네 번째 수까지의 구간 합을 물어보는 [3, 4]라고 해보자. 이 경우, P[4] - P[2] = 70이 답이 된다.

결과적으로 접두사 합을 활용한 구간 합 계산 소스코드는 다음과 같다. 아래 예시에서는 하나의 쿼리만 존재한다고 가정해보았다.

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

70

순열과 조합

이번에는 파이썬을 활용하여 순열과 조합을 계산하는 방법에 대해서 알아보자. 다양한 알고리즘 문제에서는 순열과 조합을 찾는 과정을 요구하곤 한다. 파이썬은 순열과 조합 라이브러리를 기본적으로 제공하고 있으므로 이를 간단히 이용할 수 있다.

실제로 예제를 확인하기 전에, 먼저 경우의 수에 대해서 알아보자. 경우의 수란 한 번의 시행에서 ‘일어날 수 있는 사건의 가지 수’를 의미한다. 예를 들어 시행을 ‘동전 던지기’라고 했을 때, 일어날 수 있는 사건은 {앞면, 뒷면} 중 하나이다. 다시 말해 가능한 경우의 수는 2가지이다. 다른 예시로, 시행을 ‘주사위 던지기’라고 했을 때 일어날 수 있는 사건은 {1, 2, 3, 4, 5, 6}중 하나이므로 가능한 경우의 수는 6가지이다.

순열과 조합은 실제 코딩 테스트에서 필요한 경우가 많기 때문에, 어떻게 사용할 수 있는지를 알고 있어야 한다. 사실 순열과 조합은 재귀 함수 혹은 반복문을 이용해서 직접 구현할 수도 있지만, 실제 코딩 테스트에서 이를 직접 구현하는 것은 매우 번거롭다. 다행히도 파이썬3 버전 이상에서는 순열과 조합 기능을 제공하는 라이브러리를 기본으로 제공하고 있다. 먼저 순열에 대해서 확인해보자.

기본적으로 순열(Permutation)이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것을 의미한다. 이를 nPr이라고도 표현하며 경우의 수를 계산하는 공식은 nPr = n! / (n - r)! 이다. 다만, 코딩 테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)을 다 출력하도록 요구하기도 한다. 이럴 때는 파이썬의 itertools 라이브러리를 이용한다.

다음은 1부터 4까지의 수 중에서 2개를 뽑아 한 줄로 세우는 모든 경우를 구하는 코드이다. 이때 permutations() 함수를 호출해 나온 결과의 원소들은 리스트 형태가 아니기 때문에 이를 손쉽게 다루기 위해서는 리스트로 바꿔줘야 한다. 그래서 list()를 이용하는 것이 일반적이다.

import itertools

data = [1, 2]

for x in  itertools.permutations(data, 2):
  print(list(x))

[1, 2]
[2, 1]

이어서 조합(Combinations)에 대해서도 다루어보자. 조합이란 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것을 의미한다. 조합 nCr의 형태로 표현하며, 경우의 수를 계산하는 공식은 nCr = n! / r! * (n - r)! 이다. 순열에서는 [1, 2, 3]에서 서로 다른 2개의 원소를 뽑아 나열할 때 가능한 모든 순서를 고려하기 때문에 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]가 존재한다. 하지만 조합에서는 [1, 2], [1, 3], [2, 3]만 존재한다. 파이썬에서 조합을 이용하기 위해서는 itertools의 combinations() 함수를 사용하면 된다. 사용 방법은 순열 함수와 동일하다.

import itertools

data = [1, 2, 3]

for x in itertools.combinations(data, 2):
  print(list(x), end = ' ')

[1, 2], [1, 3], [2, 3]

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Seok Min, Lee