알고리즘) 행렬 곱셈 &다양한 dp문제풀이들(부수적..)

 

 

 

 

 

 

 

 

 

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + A[i][j]; 

**"지금 내 방(dp[i][j])의 최고 점수"**는
= **"위쪽 방에서 내려온 점수"**와 "왼쪽 방에서 넘어온 점수" 중 **더 큰 것(Math.max)**을 고른 다음,
+ **"이 방 바닥에 있는 점수(A[i][j])"**를 더한 값이다!

 

(둘다 더한거는 이항계수 

 

(인덱스도 다름)

 

 

dp[0][j] = dp[0][j-1] + A[0][j];

 

**"지금 내가 도착한 방의 누적 총점(dp[0][j])"**은
= "바로 이전 방까지 모아온 총점(dp[0][j-1])" 에다가
+ "방금 도착한 이 방 바닥에 떨어져 있는 점수(A[0][j])" 를 더한 것이다.

 

 

(배열이 서로 다르네)

 

 

 

 

 

 

 

행렬경로문제

일단 초기화를 해야하네 (피보나치이건, 뭐건 간에) 

(바로 알수있는 수직, 수평인 부분들)

 

 

 

 

 

(재귀는 항상 helper가 있어야한다는거....<웹프로그래밍 중간고사)

아주 오랫동안 기억 나겟구만

1. 메모리 초기화 문제: fibo2가 호출될 때마다 new int[n]으로 새로운 빈 배열을 계속 만듭니다. 기껏 계산해서 저장해 놔도, 다음번 함수 호출 시 빈 배열로 초기화되어 기억을 잃습니다. (메모장 역할을 할 배열은 함수 밖이나 매개변수로 전달해야 합니다.)
2. 인덱스 초과 에러(IndexOutOfBounds): 자바에서 new int[n]을 하면 인덱스는 0부터 n-1까지만 생깁니다. 따라서 arr[n]에 접근하면 에러가 납니다. 크기를 n + 1로 만들어야 합니다.

 

 

1. 반복문 질문 답변 ("등호 들어가야 하나?"): 네! n번째 값을 구해야 하므로 i <= n이 맞습니다.
2. 계산 논리 오류: arr[i] = arr[n-1] + arr[n-2]라고 쓰셨습니다. 이렇게 되면 루프를 도는 내내 똑같은 값만 더하게 됩니다. **현재 위치 i를 기준으로 앞의 두 값을 더해야 하므로 arr[i-1] + arr[i-2]**가 되어야 합니다.

 

 

 

 

 

 

c 배열 안에 들어있는 값은 어떤 '그룹 번호' 같은 것이 아니라, 시작 인덱스 숫자 그 자체입니다!

 

 

1. "삼항연산자 말고 조건문으로 하는게 낫나? 삼항연산자도 뒤에 뭐 써줄 수 있었던가"
   • 조건문(if-else)을 쓰시는 게 맞습니다!
   • 자바의 삼항연산자 ? : 는 값을 하나만 반환할 때 씁니다. 지금처럼 b[i]도 업데이트하고 c[i](포인터)도 같이 업데이트해야 하는 '두 가지 이상의 동작'을 할 때는 if-else가 정석입니다. 아주 잘 선택하셨어요.
2. "포인터를 위한 배열 또 필요하나?ㅇㅇㅇ
3. "끝나는 지점의 포인터를 봐야하나?"
   •  maxIndex가 바로 **'가장 합이 큰 배열이 끝나는 지점(엔드 포인트)'**입니다.
   • 그럼 시작 지점은? 당연히 c[maxIndex] 안에 들어있겠죠!
4. "자바도 슬라이싱 되던가 / return System.arraycopy()"
   • 파이썬의 arr[start:end] 같은 문법은 없지만, 자바에서 배열을 슬라이싱해서 짤라주는 아주 편한 도구가 있습니다.
   • 바로 Arrays.copyOfRange(원본배열, 시작인덱스, 끝인덱스+1) 입니다.

 

 

 

 

 

최적화 1: 반복문(for) 합치기

현재 코드는 배열 b를 채우는 for문 1개, 그리고 최댓값을 찾는 for문 1개로 총 두 번 반복을 돕니다.
이걸 굳이 두 번 돌 필요 없이, 배열 b의 값을 계산할 때마다 최댓값을 갱신해주면 반복문 하나로 끝낼 수 있습니다.

💡 최적화 2: 배열 b 아예 없애기 (메모리 절약 - 진짜 카다네 알고리즘)

사실 이 알고리즘(카다네 알고리즘, Kadane's Algorithm)의 진짜 묘미는 배열 b를 아예 만들 필요가 없다는 것입니다.

for문 안을 잘 보시면 b[i]를 계산할 때 오직 바로 직전 값인 b[i-1]만 필요합니다. b[0]이나 b[i-2] 같은 예전 값들은 다시 쓰지 않죠.
따라서 배열을 통째로 만들지 않고, 직전 값 하나만 변수에 저장해두면 메모리를 엄청나게 아낄 수 있습니다.

 

 

 

 

 

return B[n][k];

배열 자체를 원하는게 아니라, 그 배열의 인덱스에 있는, 그 원소를 원하는거니깐 

 

• n 과 k : 【최종 목표 지점】 (고정됨)
  • 이것은 '의뢰인'이 우리에게 던져준 숙제입니다. "5개 중에 2개 고르는 법 좀 구해줘!" ➔ n=5, k=2.
  • 이 값은 계산이 끝날 때까지 절대 변하지 않습니다. 표의 맨 끝, 우리가 최종적으로 도달해야 할 도착지입니다.
• i 와 j : 【현재 내가 일하고 있는 위치】 (계속 변함)
  • 이것은 표를 채우기 위해 움직이는 '나(혹은 로봇)'의 현재 위치(좌표)입니다.
  • for 문이 돌면서 i=0, 1, 2... / j=0, 1, 2... 로 계속 변합니다.

 

 

 

⭕ 정답인 Math.min(i, k)

• 컴퓨터에게 이렇게 명령하는 겁니다. "가로로 칠할 때, 네가 지금 가진 개수(i)를 넘지 마! (3개 중에 4개를 뽑을 순 없으니까). 그리고 애초에 의뢰인이 원한 게 k개니까, 그 이상은 칠할 필요도 없어!"

⭕ 정답인 j == 0 || j == i

• 이건 컴퓨터에게 이렇게 명령하는 겁니다. "네가 지금 색칠하고 있는 그 칸(j)이 0번째 칸이니? 아니면 네가 지금 가지고 있는 개수(i)랑 똑같이 다 뽑는 칸이니? 그럼 거기에 1을 칠해!"

 

 

 

 

 

 

 

내가 음수인지 양수인지보다 앞까지의 수+ 나자신햇을때 나의 원래값보다 큰지가 중요한ㄱ사ㅇㅇㅇ

 

현재까지의 최대 합 = Math.max(앞까지의 합 + 나 자신,    나 자신)

==  "앞까지의 합이 0보다 큰가(양수인가)?" 

 

부분합의 최대 

 

 

💡 생각의 전환 포인트: "시작점"이 아니라 "끝점"을 기준으로 생각하기

질문자님의 생각: "여기서 시작하는 부분 리스트 중에 뭐가 제일 클까?"
천재들의 생각: "여기서 끝나는 부분 리스트 중에 뭐가 제일 클까?"

이 작은 관점의 차이가 엄청난 마법을 만듭니다.

왜 "끝점"을 기준으로 생각할까요?

어떤 인덱스 i에서 끝나는 가장 큰 부분 리스트의 합을 구하려면, 딱 두 가지 경우밖에 없기 때문입니다.

1. 앞에서 이어져 오던 합에 나를 포함시킨다. (과거 + 나)
2. 앞에 놈들 다 버리고 나부터 새롭게 시작한다. (오직 나)

그럼 언제 앞의 합을 버리고 새롭게 시작해야 할까요?
바로 "이전까지 더해온 합이 음수(-) 일 때" 입니다.

 

 

 

 

 

 

 

 

 

분할 정복의 핵심은 **"큰 문제나 작은 문제나 푸는 방식(규칙)이 완벽히 똑같아야 한다"**는 것입니다.

• 만약 행렬을 십자가로 자르지 않고 가로로만 한 번 싹둑 잘라서 위/아래 2조각(직사각형)으로 만들었다고 가정해 봅시다.
• 원래 문제는 "정사각형 행렬 곱하기" 였는데,
• 쪼개고 나니 "직사각형 행렬 곱하기" 로 문제의 성질(모양)이 변해버렸습니다.
• 이렇게 되면 원래 쓰던 곱셈 공식을 작은 조각에 그대로 재사용(재귀 호출)할 수가 없게 되어 알고리즘이 꼬여버립니다.