[python] 백준 1026 : 보물

정?렬도 정렬인데, 매 순간 선택을 해야하는 문제입니다.

정수 집합 B의 배열은 고정되어있는 상황에서 배열 A를 전체합이 최소가 되게 옮겨야합니다. 이때 전체 합이 최소려면, B배열에서 값이 큰 요소일수록 A배열의 값이 작은요소를 할당해주면 됩니다. 큰수 x 작은수로 상쇄시키는거지요. 

 

이 논리를 머릿속으로 대충 구현해봅시다.

 

입력값으로 두 리스트 A,B를 만듭니다. B가 고정이므로, B의 최솟값부터 크기 오름차순으로 값의 리스트내 위치를 추출합니다... 그 위치값을 리스트로 만들어... 어쩌구..... 너무 복잡한데...

어제 정렬만 실컷하다보니 뇌가 살짝 정렬에 찌든것같습니다. 사실 정렬할필요가 없는 문제입니다.

 

아주 단순하게, 극단적으로, 리스트 B의 최댓값과 리스트 A의 최솟값을 곱해주면됩니다. 계산된 최솟,최댓값은 각 리스트에서 제거합니다. 이제 또 남은 리스트의 최댓값과 최솟값을 곱해줍니다. 그리고 이전 결과에 더해줍니다. 이 계산을 반복하면 됩니다. 극단적으로 지금 현 상황에서의 최솟값을 찾는다는점에서 탐욕 알고리즘과 비슷하다고 볼수있네요.

 

탐욕 알고리즘(greedy algorithm)을 인공지능 수업에서 트리구조 모델을 배울때 잠깐 스치듯 들었었는데 핵심은 어떤 절차/ 단계에서 그냥 그 순간에 최적의 상황을 찾는 알고리즘입니다. 바나나 7개를 지금 4개먹고 저녁에 3개먹을래? 지금 3개먹고 저녁에 4개먹을래...? 할때 바로 지금 4개를 선택해버리는거죠.

 

탐욕 알고리즘은 항상 최적의 결과를 도출하는것은 아닙니다. 전체를 고려하지않고 순간순간의 최적값만 선택하다보니 계산시간은 빠르고 간단하지만 최적은 아니죠. 애초에 탐욕 알고리즘의 목적은 최적의 값이 아닌, 최적에 근사하는 값을 도출하는것에 있습니다. 

그리디 알고리즘 예시

앗 또 발그림 등장! 탐욕 알고리즘의 동작 예시를 들어보자면, 위와같은 트리구조에서 노드의 적힌 값의 합이 최대가 되도록 간선을 따라간다고 했을때, 최적해는 10+4+6 = 20 이지만, 탐욕 알고리즘은 첫번째 갈림길에서 4로 가지않고 7로 갑니다. 그 순간의 최적의 해이기 때문이죠. 노드 7로 간후 1,2 중에선 그 순간의 최적해인 2를 선택할겁니다.

결국 10+7+2 = 19로 최적해는 아니지만 최적해에 근사한값이 나오게됩니다. 이게 탐욕 알고리즘의 동작방식입니다.

 

이제 문제로 돌아와봅시다. "근데 우리는 최적해에 근사한값이 아니라.. 최적해를 구해야하잖아...? "

 

걱정마십쇼. greedy algorithm은 상황에 따라 최적해를 구하는데 쓰일수있습니다. (근사가 아닌, 최적해 그 자체요)

주로 계산 원리가 극단적인 문제상황에서 탐욕 알고리즘이 유용하게 쓰일수있습니다.

 

이 문제의 경우도 그렇습니다. 우리는 무조건 B의 큰값에는 A의 작은값을 할당해주면 됩니다. 다른 요소들이야 어찌되든 상관없이, 반복되는 상황에서 그냥 B의 최댓값과 A의 최솟값 곱해줌.. ☜ 이거 반복하면 됩니다. 이런 문제에선 탐욕 알고리즘으로 정해를 구할수있겠지요.

 

n=int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
      
val = 0

while a:
    val_a = min(a)
    val_b = max(b)

    val += val_a * val_b

    a.remove(val_a)
    b.remove(val_b)

print(val)

전체 코드입니다. a,b리스트를 입력받았습니다.

while 반복문을 이용해줍시다. while a:는 리스트 a가 완전히 텅 빌때까지 반복하는겁니다.

min, max를 이용해 각 a의 최솟값, b의 최댓값을 추출해줍니다. 그리고 그 값을 곱해준뒤, 전체 val값에 저장해주죠.

마지막으로 반복문에서 이번 시행에 계산에 사용된 최댓값과 최솟값은 remove를 이용해 리스트에서 제거해줍니다.

그렇담 찐 최대최소값이 제거됐으므로 이제 두번째로 큰 수가 max, 두번째로 작은수가 min이 되겠지요? (약간 메없산왕 느낌.. 그시절 바르샤는 어디가고 지금은....) 이 시행을 반복하면 처음에 우리가 의도했던대로 리스트 b의 최댓값부터 내림차순으로 a의 최솟값부터 오름차순값이 할당됩니다. 

 

외전) pop과 remove의 차이?

사실 이거땜에 처음엔 오류가떴습니다. 원래는 반복문 마지막에 최댓,최솟값을 리스트에서 제거해주는 과정에서 a.pop을 썼습니다. 이게 문제인줄 몰랐는데 a.remove로 바꾸니 잘 돌아가더군요.

a.pop은 해당값을 리스트에서 제거해줌과 동시에 해당값을 반환합니다. 즉 a.pop(3)을 하면 리스트의 3번째 요소가 제거되면서 리스트의 3번째 요소를 반환하는, 변수값이 포함된 줄입니다. 이 줄을 그냥 어떠한 처리도없이 반복문을 돌리려했으니 오류가뜬거죠. a.remove는 그냥 반환없이 깔끔히 제거해줍니다.

또한 pop은 리스트의 위치값으로 판단합니다. a.pop(3)은 리스트에서 3을 제거하는것이 아닌, 리스트의 3번째 요소를 제거하며 반환하는거죠. 그러나 a.remove(3)은 리스트에서 '3'이란 요소를 제거하는겁니다. 만약 3이 중복될때는 가장 앞쪽에 있는 3만 제거합니다. (그렇기에 중복값이 들어가도 계산할땐 상관없던것이죠.)

 

만약 pop을 사용할때 가변적인 min(a)의 위치를 모르겠다면..? -> a.index(min(a))을 써줍시다.  (index는 해당 값의 리스트내에서의 위치를 반환해줍니다.)

 

오늘도 한문제를 야물딱지게 풀어봤읍니다. 사실 조금더 고난도문제를 도전하고있었지만 알고리즘 기초에대해 더 공부하고 풀어야겠다는 생각이 들더군요. 따로 알고리즘 공부한거나 C, Java 공부한것도 올려보겠읍니다. (사실 공부한게 없어서 못올리고있읍니다.. 이틀뒤에 알고리즘 책 반납해야되는데 호메다닥 읽어봐야겠네요)