알고리즘) 코드1

 

 

 

이항계수

//n,k는 끝범위를 정해준거고 , 반복문 안에서는 i,j로 ?
//icj인거니깐, 원래 재귀에서 n==k 체크햇던걸
//i==j체크하나 ?

 

//i는1부터, j는0부터인가 ?

 

 

 

부분합

 

• //if문에서 통과되면 이것까지 더해도 최대라는 의미인가 ????
  • 네, 맞습니다. if(sumArr[i-1] > 0)의 의미는 "현재 원소 arr[i] 이전에 끝나는 최대 부분 합이 양수라면, 이를 현재 원소와 합치는 것이 무조건 이득이다"라는 뜻입니다.
  • 반대로 0 이하라면, 이전 것들을 다 버리고 현재 위치 i에서부터 새로 시작하는 것이 최대합을 만드는 데 유리하기 때문에 p[i] = i가 되는 것입니다.
• //이때는 double maxValue필요없나
  • b2 함수에서는 endOfList라는 변수가 최대값이 발생하는 **위치(인덱스)**를 기억하고 있습니다.
  • sumArr[endOfList]가 곧 maxValue 역할을 하기 때문에, 별도의 maxValue 변수를 선언하지 않아도 최대값을 비교하고 찾을 수 있습니다. 오히려 인덱스를 저장해두는 것이 나중에 리스트를 잘라낼 때 더 유용합니다.

 

 

 

현재 코드 마지막 줄에 sumArr[...]를 자르려고 하셨는데, sumArr은 누적된 합계들이 저장된 배열입니다. 문제에서 요구하는 출력은 원본 데이터이므로, **원본 배열인 arr**에서 구간을 잘라내야 합니다.

• 수정 전: return sumArr[...]
• 수정 후: return arr[...] (원본 데이터에서 추출)

 

 

 

 

 

가방 문제 

 

W랑 비교하는게 아니라 

w[i] <= j

(인덱스는 또 i네 )

 

 

 

• int W가 따로 주어지나?: 네, 보통 배낭의 총 용량 W는 외부에서 인자로 주어집니다.

 

배열 크기에서 n 어케 정할지 

 

 

 

1번 인덱스가 1번 물건

데이터를 아예 1번 인덱스부터 넣는 방식입니다. 

• 데이터 준비: p = {0, 10, 20, 30, 40} (길이 5)
• 개수 n: p.length - 1 (실제 물건 개수 4)

 

전략 B: 함수 안에서 인덱스를 -1 해주기

데이터 배열은 0번부터 꽉 차 있는데, 함수 인자 i는 "몇 번째 물건"인지를 나타낼 때입니다.

• 데이터 준비: p = {10, 20, 30, 40} (길이 4)
• 개수 n: p.length (4)

함수 내부: p[i-1] (i가 4일 때 p[3]을 가져오므로 

 

 

DP 테이블(P)의 크기는 왜 n+1 인가?

이건 데이터 배열(p, w)과는 별개의 문제입니다. **"물건을 0개 선택했을 때"**라는 상태를 저장해야 하기 때문입니다.

• 물건이 4개라면, 우리가 알고 싶은 상태는 총 5가지입니다:
  • 물건 0개 고려함 (인덱스 0)
  • 물건 1개 고려함 (인덱스 1)
  • 물건 2개 고려함 (인덱스 2)
  • 물건 3개 고려함 (인덱스 3)
  • 물건 4개 고려함 (인덱스 4)
• 그래서 P 배열은 무조건 new int[n + 1][W + 1]이 되어야 합니다.

 

 

 

 

 

w=0	w=1	w=2	w=3	w=4
i=0 (물건없음)	0	0	0	0	0
i=1 (물건 A)	0	?	?	?	?
i=2 (물건 B)	0	?	?	?	?
i=3 (물건 C)	0	?	?	?	?

 

 

 

분할정복법으로 했을때는 배열에서 가져오면 안되고 

재귀 호출의 부재: P[i-1][j]라고 쓰면 단순히 배열의 값을 가져올 뿐입니다. 그 값이 아직 0이라면? 값을 구하기 위해 함수 자신(d2)을 다시 호출해야 합니다.

 

 

 

1. p.length가 4라면: 물건은 0, 1, 2, 3번 인덱스에 있습니다.
2. DP 테이블 P의 행은 5개(0~4)여야 합니다: "물건 0개 사용" 상태가 필요하기 때문입니다.

 

 

그니깐 반복문의 기준을 dp를 기준으로 해서 둘다 등호(안쪽 바깥 둘다 등호넣고,

 p,w배열 접근할떄만 -1빼서 접근하는건가 , 매개변수로 주어질떄는 

 

 

 

 

 j-1을 할 필요 없이 j 그 자체를 사용하면 됩니다.<

이떄는 왜 -1안하지 언제-1을 하는거지,

음, 이건, P배열의 무게에 들어갈 무언가라서 그런가 

 

정보가 들어있는 배열(p, w)을 참조하느냐" 아니면 **"용량 수치 그 자체를 쓰느냐