2024년 1월 1일 알고리즘 문제풀이

문제

난이도

Lv.2

코드

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

from heapq import heappop, heappush
def solution(A,B):
    n = len(A)
    arr_A = [False for _ in range(n)]
    arr_B = [False for _ in range(n)]
    arr = []
    def dfs(tmp,arr_A,arr_B):
        if arr and tmp > arr[0]:
            return
        if not arr_A.count(False) and not arr_B.count(False):
            if not arr or tmp < arr[0]:
                heappush(arr,tmp)
        for i in range(n):
            if arr_A[i]:
                continue
            for j in range(n):
                if arr_B[j]:
                    continue
                arr_A[i] = True
                arr_B[j] = True
                dfs(tmp+(A[i]*B[j]),arr_A,arr_B)
                arr_A[i] = False
                arr_B[j] = False
    dfs(0,arr_A,arr_B)
    return arr[0]

처음엔 DFS로 시도했다. 여러 case가 규칙성 없이 나타날 수 있다고 생각했기 때문이다. 하지만 시간초과가 발생했다. 불필요한 탐색을 줄이기 위해, 값을 최소힙에 저장하도록 했다. DFS 과정 상 재귀 중에 이미 최소힙에 존재하는 최솟값을 넘어선 경우 탐색을 중단하도록 했다. 하지만 시간초과가 계속 발생했다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from heapq import heappop, heappush
def solution(A,B):
    answer = 0
    n = len(A)
    heap_A = []
    heap_B = []
    for i in range(n):
        heappush(heap_A,A[i])
        heappush(heap_B,-1*B[i])
    for i in range(n):
        a = heappop(heap_A)
        b = heappop(heap_B)
        answer += a*b*(-1)
    return answer

문제에서 주어진 예시를 살펴보다가, 양쪽의 최솟값과 최댓값을 순차적으로 곱해서 더하는 값이 답이지 않을까 생각했다. 처음에는 가장 큰 값과 가장 작은 값, 그 다음 두번째로 큰 값과 두번째로 작은 값을 곱하여 더해주는 방식. 매번 탐색하기엔 너무 복잡할 것 같아 배열을 최소힙으로 변경했다. 나머지 하나는 최댓값을 찾아야 하기 때문에 음수로 변형하여 최소힙을 설정해주었다.

결국 답은 구했는데 왜 이게 답인지 모르겠다. 저 코드가 이해가 안되는 건 아닌데, 왜 저때가 최솟값이지? 찾아보니 재배열 부등식의 개념이라고 한다. 교과과정에는 안나오고 경시대회 수학에서 나오는 개념이라는데.. 궁금하니 조금 알아봤다.

재배열 부등식

img

출처 : 나무위키

위 내용인데, 그리디 알고리즘의 예시 중 하나이다. 쉽게 말하면, 정렬된 두 수열의 원소의 곱의 합은 두 수열이 반대 방향으로 정렬되어 있을 때 가장 작고, 같은 방향으로 정렬되어 있을 때 가장 크다는 내용이다.

다음은 증명이다. 글씨는 양해 바람.

img

위 증명으로 얻을 수 있는 결론은, 오름차순 정렬되어 있는 두 수열에서 임의의 순서 변화가 발생할 경우 값은 무조건 작아진다는 의미이다. 바꿔 말하면, 두 수열이 똑같이 정렬되어 있을때 가장 큰 값을 가진다는 것.

우리의 경우는 최댓값이 아닌 최솟값이 필요한데, 두 수열을 같은 방향으로 정렬이 아닌 반대 방향으로 정렬하면 결과를 얻을 수 있다. 아래 참고.

img

위와 같이, 두 수열이 정 반대로 정렬되어 있을때 임의의 순서의 변화가 발생한다면 값은 무조건 커진다는 의미이다.

이제 왜 DFS나 BFS로 모든 경우를 탐색할 필요가 없는지 이해됐다.