정글 TIL 19(01.30)

오늘의 글쓰기

타인에게 어느정도 영향을 끼쳐야 하는게 적절한 것인지 잘 모르겠다. 사실 말한다고 바뀌는 것도 아니고 내가 그랬듯 타인도 자기가 살고싶은대로 살 것이다. 그렇다면 타인에게 전하는 충고는 무용지물인걸까? 그건 아닌듯 하지만, 그 반향이 너무 강하다. 언제나 선택에는 책임이 따른다. 그 책임이 아직 내가 버거운건가 싶기도 하다. 잘 모르겠다

알고리즘 문제 풀이

9251 LCS 아이디어만

이중 리스트의 테이블링 방법은 두 가지가 있습니다.
1. str1[i]의 문자와 str2[j]의 문자가 같다면 왼쪽 위(dp[i-1][j-1]) 값에 1을 더해 저장합니다.
2. 문자가 같지 않다면 왼쪽과 위의 값 중 더 큰 값을 저장합니다.
3. 저장 후 탐색 방법은 위 방법의 역순입니다.

12865 평범한 배낭 아이디어만

아이디어는 경우를 쪼개는 것입니다. 예를 들어
물건 ABCD를 담을 수 있고 총 무게가 7이라면,
물건 A를 담은 가치 + BCD를 담을 때 최대의 가치
이 경우도 또 쪼개면 B를 담은 가치 + CD를 담을 때 최대의 가치 ... 이런 방법으로 쪼갭니다.
그래서 이중 리스트로 작성하게 되는 것입니다.

물건을 stuff 리스트에 튜플 형식으로(weight, value)로 저장합니다.
인덱싱은 weigth는 stuff[i][0], value는 stuff[i][1]이 됩니다.

이중 리스트에서 탐색할 때
1. 탐색 값인 j가 weight보다 작으면, 위의 값을 그대로 가져옵니다.
2. 그외의 경우엔 (현재의 가치 + 위의값 중 무게만큼 뺀 요소)와 위의 값 중 더 큰 값을 저장합니다.

        weight = stuff[i][0] 
        value = stuff[i][1]
       
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] #weight보다 작으면 위의 값을 그대로 가져온다
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])