직전 포스팅에 다 작성하기엔 양이 많아 1, 2로 나눴다.
구간 합
구간 합 문제는 리스트 내 특정 구간의 모든 수를 합한 값을 구하는 문제이다. 여러 개의 쿼리로 구성되는 문제 형태로 출제되는데, 보통 다수의 구간에 대한 각각의 합을 구하도록 요구된다.
- 10, 20, 30, 40, 50
리스트가 있을 때 두 번째 수부터 세 번째 수까지의 합은 50, 두 번째부터 네 번째 수까지의 합은 90이다. N개의 수와 M개의 쿼리가 주어져 각각의 구간 합을 매번 구한다면 O(NM) 의 시간복잡도를 가진다. 그렇기 때문에 데이터가 많아질 경우 해결할 수 없을 것이다.
따라서 prefix sum 기법을 이요하면 된다. 접두사 합이란 리스트 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다. 이를 이용하면 시간복잡도는 O(N+M) 으로 줄어든다.
- N개의 수에 대한 접두사 합을 계산하여 배열 P에 저장한다.
- 매 M개의 쿼리 정보 [Left, Right]를 확인할 때, 구간 합은 P[Right] - P[Left-1] 이다.
위에 있는 5개 수에 대한 접두사 합을 계산해보자.
- 0, 10, 30, 60, 100, 150
3개의 쿼리가 주어졌을 때, 구간 합을 구하는 과정은 아래와 같다.
- 첫 번째 수부터 세 번째 수까지의 구간 합
- P[3] - P[1-1] = 50
- 두 번째 수부터 다섯 번째 수까지의 구간 합
- P[5] - P[2-1] = 140
- 네 번째 수부터 다섯 번째 수까지의 구간 합
- P[5] - P[4-1] = 90
순열과 조합
순열과 조합에 대해서는 다음 포스팅에서 한 번 더 다룰 것이다.
- 순열 : 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것
- 조합 : 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것
직접 구현할 수도 있지만 알고리즘 문제에서는 모든 경우를 다 출력하도록 요구하는 경우가 많아 itertools 라이브러리를 이용하면 손쉽게 출력할 수 있다.
참고
- 이것이 취업을 위한 코딩 테스트다
