개미전사 풀이-동적프로그래밍(파이썬)

최근 혼자서 캐글 머신러닝(캐글)모델 만드느라 알고리즘을 좀 멀리했다 

어제 마지막 제출을 하며 혼자서 꺠달은게 많다 다음포스팅은 아마 이것에관한 포스팅이될것이다

 

나동빈님의 동적프로그래밍 강의 영상에서 나온 첫번째 문제이다

가볍게 풀고 할거하려고했는데 문제가 너무어려워서 며칠동안 손놓고 딴거(머신러닝)하다가 오늘다시 손봐서 다시 풀었다

 

슬슬 백준에서도 알고리즘에대해서 다루는것같은데 아직 난 모르는게 너무 많다

 

결론부터 말하자면 나는 동적프로그래밍으로 안풀었다(ㅋㅋㅋㅋㅋㅋㅋ)

그리고 이게 백준문제가 아니라 정답체크가 완벽히 되지않아서 내가 쓴답이 틀렸을 확률이 높다

 

푼 이후에는 동빈나 선생님의 풀이를 보면서 어떻게 다이나믹 프로그래밍을 이용해 풀었는지

차근차근 배워보았다

 

문제 소개

* 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다.

(뭔가 개미와 메뚜기의 역할이 바뀐것같지만 넘어가도록하자)

메뚜기 마을에는 여러개의 식량창고가 있는데 식량창고는 일직선으로 이어져있습니다.

* 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여

식량을 빼앗을 예정입니다. 이때  메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 

식량창고가 공격받으면 바로 알아챌수 있습니다.

* 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 

식량창고를 약탈해야 합니다.

 

* 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하세요

입력예시

4

1 3 1 5

출력예시

8

 

나의풀이

처음에는 어떤방식으로 접근해야할지도 감이 잘 안잡혔었다 그러다 입력 리스트의 모든 조합을 알아내면 되겠다! 라는 생각이 들었다 조합을 구하는방법은 원래 알고있었기에 마음이 놓였다

def 조합2(thelist):
    for i in range(len(thelist)-1):
        for j in range(i+1,len(thelist)):
            print(thelist[i],thelist[j])

조합2([1,2,3,4])

문제는 조합의 요소개수가 고정되있지 않다는것이였다

예를들어 출력으로 1 3 1 5 가 주어진다면 1 3 1 5 의 조합을 구성하는 요소의 개수가 

1개일때부터 4개일때까지 모두 구해야한다

 

따라서 리스트와 조합요소개수까지 받는 새로운 함수를 만들어야했다

 

여기서부터 좀 어려웠는데 조합요소개수가 늘어날때마다 반복문 개수도 늘어난다는 규칙은

발견했지만 머리를 쥐어짜도 반복문 중첩을 어떻게 설정하지? 에대한 해답은 나오지않았다

하지만 파이썬으로 만들수없는건 없다는 사실을 알고있었기에 답답했다

 

결국 구글에서 조합만드는법을 좀 찾아봤다 

사실 파이썬 기본 모듈로 쉽게 구할수있는 방법이 있는것같긴했는데 관심없었다

문제는 뒷전이고 어떻게 조합을 구할수있는지가 궁금했다

답은 재귀함수를 이용하는것이였다 반복문 중첩이 입력값에 따라 달라진다면

그에대한 답은 재귀함수인것같다

def 조합(thelist,num):
    chosen=[]
    if len(thelist)<num:
        return
    elif num == 1: # 재귀끝
        for i in thelist:
            chosen.append([i])
        return chosen
    elif num > 1: # 재귀 구현
        for i in range(len(thelist)-(num-1)):
            for j in 조합(thelist[i+1:],num-1):
                chosen.append([thelist[i]]+j)
        return chosen
print(조합([1,2,3,4,5],3))

아직도 재귀함수에대한 숙련도가 낮은것같다 구글링전에 구현을 할수있었으면 좋앗을텐데

 

조합을 응용해 문제에 쓰일 개미조합을 만들었다

def 개미조합(array,num):
    chosen=[]
    if len(array)<num:
        return
    elif num == 1: # 재귀끝
        for i in array:
            chosen.append([i])
        return chosen
    elif num > 1: # 재귀 구현
        for i in range(len(array)-(num)):
            for j in 개미조합(array[i+2:],num-1):
                chosen.append([array[i]]+j)
            
            
        return chosen
print(개미조합([1,2,3,4,5],2))

1부터 리스트의 요소개수까지의 range를 모두 개미조합에 대입하여

전체 리스트에서 나올수있는 모든 개미조합을 구할수있었다

 

그후 모든 개미조합의 합을구해 최대값을 출력하였다

# 개미전사
def 개미개미조합(array,num):
    chosen=[]
    if len(array)<num:
        return
    elif num == 1: # 재귀끝
        for i in array:
            chosen.append([i])
        return chosen
    elif num > 1: # 재귀 구현
        for i in range(len(array)-(num)):
            for j in 개미개미조합(array[i+2:],num-1):
                chosen.append([array[i]]+j)
        return chosen



int(input())
a=list(map(int,input().split()))
모든개미조합=[]
sumlist=[]

for i in range(1,len(a)+1):
    for i in 개미조합(a,i):
        모든개미조합.append(i)

for i in 모든개미조합:
    if type(i)==int:
        sumlist.append(i)
    else:
        sumlist.append(sum(i))

print(max(sumlist))

이제 나동빈님의 풀이를 보자

특정 인덱스까지의 최대값을 표시하고 이를 갱신하는방식으로 접근

입력  1  3  1  5 일때

인덱스 0  1   2  3

            1   3  3   8

d[i]의값은 d[i-1] 와 d[i-2] + d[i] 중에 더 큰것이 된다

 

여기까지 듣고 동적프로그래밍방식으로 구현이 가능하겠다 싶어 코딩해보았다

# 동적 프로그래밍 방식의 접근

n=int(input())
a=list(map(int,input().split()))
d=[0]*(n+1)

d[1]=a[0]
d[2]=max(d[1],a[1])

for i in range(2,len(a)):
    d[i+1]=max(d[i], d[i-1]+a[i])

print(d[len(a)])

심플하고 와닿는 풀이방식이다 

부분은 전체와 같다는점에서 재귀 풀이방식과 비슷하지만 훨씬 간단한느낌이다