✏️ 오늘 학습한 내용

1. 자료구조 & 알고리즘
2. Sort
3. Search
4. Recursion

---

🔎 자료 구조

자료 구조를 알아야하는 이유

• 기본적으로 제공하는 데이터 타입으론 해결할 수 없는 문제가 존재하기 때문이다.
  
  
• 해결하고자 하는 문제가 무엇이냐에 따라 효율성을 위해 사용되어야 하는 자료 구조가 다르다.

---

🔎 알고리즘

• [정의] 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합
  
  
• 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택

---

🔎 Sort

1) Sort 함수

a = [1,4,3,2,5]

a.sort()

a → [1,2,3,4,5]

a.sort(reverse=True)

a → [5,4,3,2,1]

b = sorted(a)

b → [1,2,3,4,5]

2) key 지정 정렬

L = ['abcd', 'xyz', 'spam']
sorted(L, key=lambda x: len(x))
# 문자열 크기 순 정렬

L = [{'name':'John','score':83},
{'name':'Paul','score':92}]

L.sort(key=lambda x : x['name'])
# name의 알파벳 순 정렬

L.sort(key=lambda x : x['score'], reverse=True)
# score의 내림차순 정렬

3) Sort 종류 별 시간 복잡도

source: https://danidani-de.tistory.com/45

---

🔎 Search

1) Linear search - O(n)

2) Binary search - O(log n)

# 코드 구현
def solution(L, x):
    answer = -1
    left = 0
    right = len(L)-1
    
    while left<=right :
        mid = (left+right)//2
        if L[mid] == x :
            return mid
        elif L[mid] < x :
            left = mid+1
        else :
            right = mid-1
        

    return answer

---

🔎 Recursion

1) Recursion의 단점

Recursion의 경우 O(n), for문의 경우 O(n)으로 시간 복잡도는 같지만,
재귀는 n만큼 함수 호출을 하므로 효율성이 떨어짐

2) Fibonacci 구현

# 재귀
def fib(x) :
    if x < 2 :
        return x
    return fib(x-1) + fib(x-2)
        
# for
def solution(x):
    fb = [ 0 for _ in range(x+2) ]
    fb[0] = 0
    fb[1] = 1
    for i in range(x-1):
        fb[i+2] = fb[i+1] + fb[i]
    answer = fb[x]
    # answer = fib(x)
    return answer

---

✍ 어려웠던 내용 & 새로 알게 된 내용

배낭 문제(Knapsack Problem)

백준 12865
DP(동적계획법)을 사용

N, K = map(int, input().split())
W=[0]
V=[0]
dp=[[0]*(K+1) for _ in range(N+1)]
for _ in range(N) :
    w, v = list(map(int, input().split()))
    W.append(w)
    V.append(v)


# dp[i][j] : 0~i번째까지의 물건들을 따져봤을 때 최대가치, j는 넣을 수 있는 무게
for i in range(1,N+1) :
    for j in range(1,K+1) :
        # 넣을 수 있는 무게보다 i번째 물건이 무거운 경우
        if j < W[i] :
            # i번째 물건을 넣지 않았을 때, 이전의 가치를 그대로 유지
            dp[i][j] = dp[i-1][j]
        # i번째 물건을 넣을 수 있다면
        else :
            # 이전의 최대 가치와 i번째 물건을 넣었을 때의 가치를 비교
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])

# 처음 i=1 일때, 첫 번째 물건을 넣을 수 있는 무게에 도달하면 -> 최대가치가 V[1]으로 갱신됨
# i=2 일때, 두 번째 물건을 넣을 수 있는 무게에 도달하면 -> 첫 번째 물건을 넣었을 때와 가치를 비교
# + 무게를 점차 늘려 무게마다의 최대가치를 갱신
# 이를 반복하여, 적은 무게부터 dp를 차곡차곡 채워서 최대가치를 찾음

print(dp[N][K])