알고리즘 | 배열 분할 정복 팁

직관적인 나눗셈

한 배열을 두 개의 배열로 나누는 연산은 분할 정복에서 자주 등장하는 소재이다. 배열이 짝수개라면 반반 나누기가 쉽겠지만, 홀수가 되면 배열을 쪼개는 일이 햇갈리고 시간을 소모하게 하는데, 이 시간을 아껴 효율적인 알고리즘 풀이를 위해 작성한다.
임의의 연속된 배열을 가지고 살펴볼 것인데 이는 배열의 인덱스를 다루는 것과 같기 때문이다. 퀵소트를 짤 때, 분할 탐색을 할 때, 우리가 자주 사용했던 변수 (start, end) or (left, right) 모두 여기에 해당한다.

• 배열이 닫힌구간 [a, b]일 때와 열린 구간일 때 [a, b).
• 배열의 원소의 개수가 짝수인 경우, 홀수인 경우로 나누어 정리한다.

[a, b]

양쪽 구간을 다 포함하는 구간을 다룰 때.
닫힌 구간 나눗셈이니 [a, mid], [mid + 1, b] 으로 나뉜다고 생각하자.

Case 예시

m = a + b값이라고 하자.

1. m = 짝수 Case : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2. m = 홀수 Case : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

양 끝 값이 a, b임으로 원소의 개수

n = 
짝수, if a + b == 홀수 
홀수, if a + b == 짝수

mid = (a + b) // 2 : 애매하면 왼쪽에 하나 더 준다.

• a + b가 홀수일 경우 균등하게 나뉜다. (n은 짝수개)

mid = (1 + 10)//2
# mid = 5
[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]

• a + b가 짝수일 경우 왼쪽에 하나 더 간다. (n은 홀수개)

mid = (1 + 11)//2
# mid = 5
[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11]

mid = (a + b -1) //2 : 애매하면 오른쪽에 하나 더 준다.

• a + b가 홀수일 경우 균등하게 나뉜다. (n은 짝수개)

mid = (1 + 10 + - 1)//2
# mid = 5
[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]

• a + b가 짝수일 경우 오른쪽에 하나 더 간다. (n은 홀수개)

mid = (1 + 11 - 1)//2
# mid = 5
[1, 2, 3, 4, 5], [6, 7, 8, 9, 10, 11] 

mid = (a + b + 1) // 2 : 무조건 왼쪽에 하나 이상 더 준다.

• a + b가 홀수일 경우 왼쪽에 두 개 더 준다. (n은 짝수개)

mid = (1 + 10 + 1)//2
# mid = 6
[1, 2, 3, 4, 5, 6], [7, 8, 9, 10]

• a + b가 짝수일 경우 왼쪽에 하나 개 더 간다. (n은 홀수개)

mid = (1 + 11)//2
# mid = 5
[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11]

• 특별한 경우가 아니면 항상 불균형을 만들기 떄문에 좋은 코드가 아니라고 생각한다.

[a, b)

파이썬의 range(1, 10)과 같이 열린 구간을 다룰 때를 알아보자.

• 열린 구간 나눗셈이니 [a, mid), [mid, b) 으로 나뉜다고 생각하자.

Case 예시

1. a + b = 홀수 Case : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
2. a + b = 짝수 Case : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)

원소의 개수 n = 
짝수, if a + b == 짝수
홀수, if a + b == 홀수

mid = (a + b) // 2 : 애매하면 오른쪽에 하나 더 준다.

• a + b가 짝수일 경우(n은 짝수) 균등하게 나뉜다.

mid = (1 + 11)//2
# mid = 6
[1, 2, 3, 4, 5, 6), [6, 7, 8, 9, 10, 11)

• a + b가 홀수일 경우 오른쪽에 하나 더 간다.

mid = (1 + 10)//2
# mid = 5
[1, 2, 3, 4, 5), [5, 6, 7, 8, 9, 10)

mid = (a + b + 1) // 2 : 애매하면 왼쪽에 하나 더 준다.

• a + b가 짝수일 경우 양쪽에 똑같이 나눈다.

mid = (1 + 11 + 1)//2
# mid = 6
[1, 2, 3, 4, 5, 6), [6, 7, 8, 9, 10, 11)

• a + b가 홀수일 경우 왼쪽에 하나 더 준다.

mid = (1 + 10 + 1)//2
# mid = 6
[1, 2, 3, 4, 5, 6), [6, 7, 8, 9, 10)

mid = (a + b -1) //2 : 애매하면 왼쪽에 하나 더 준다.

• a + b가 짝수일 경우 오른쪽에 두 개 더 간다.

mid = (1 + 11 - 1)//2
# mid = 5
[1, 2, 3, 4, 5), [5, 6, 7, 8, 9, 10, 11)

• a + b가 홀수일 경우 오른쪽에 하나 더 준다.

mid = (1 + 10 + - 1)//2
# mid = 5
[1, 2, 3, 4, 5), [5, 6, 7, 8, 9, 10)

• 특별한 경우가 아니면 항상 불균형을 만들기 때문에 좋은 코드가 아니라고 생각한다.