오늘 한줄 요약
삽질 마스터
새로 배우게 된 것
- LCS(Subsequence)
- 컴퓨터 시스템에서의 스택과 레지스터
- 행렬 곱셈 순서(11049.Py)
LCS
(이거 그러고보니 어제 했잖아)
-
개념
연속하지 않아도 순서만 지켜도 되며,
LCS[i][j]는 두 문자열의 가장 긴 부분 수열 -
점화식
if str1[i-1] == str2[j-1]:
LCS[i][j] = LCS[i-1][j-1] + 1
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])SubString과의 차이점은 연속하지 않아도 된다는 점.
문자열 같은 경우 이전문자와 연결 되어야 하기에 2차원 DP 테이블 내 대각선 원소를 체크한다.
그렇지만 부분 수열 같은 경우 연속될 필요가 없기 때문에 같은 글자라면 그 전까지의 결과에 1을 더하기만 하면 된다.
다른 글자라면, 둘을 비교해서 더 긴 LCS 길이를 갖고 온다.
컴퓨터 시스템에서 스택과 레지스터의 차이
- 스택
- 프로시저 호출시 지역변수와 매개변수 저장용도
- 또한 함수의 제어 흐름 역시 관리
- 함수가 다른 함수를 호출할때 반환 주소와 이전 주소의 스택 프레임을 저장
- 레지스터
- 프로세서 내부 고속 메모리, 자주 접근하는 변수 혹은 중간 계산값 저장용도 사용
행렬 곱셈 순서
- 왜 DP인가
N개의 행렬 곱셈 연산 수를 M1 * M2 * ... * Mi * Mi+1 * ... *Mn 라고 하자.
그럼 가장 마지막에 곱해지는 것들은 무엇인가? 를 찾아보자.
행렬 곱셈은 2개의 행렬을 곱할때,
예를 들어 p * q 와 q * r, 두 행렬을 곱하면 p * r 짜리 행렬이 나온다.
결국 두개씩 묶어서 행렬 곱셈을 진행할 것이고,
그렇다면 가상의 점 i를 기준으로 두개의 행렬을 계산한다면?
전체의 값이 앞쪽 묶음 + 뒤쪽 묶음 + 그 둘 곱셈 으로 부분 문제로 분할이 된다.
또한 그 앞쪽 묶음 역시 동일한 형태로 범위만 작아진채 부분 문제가 된다.
이래서 DP다.
DP[1][N] = DP[1][i] + DP[i + 1][N] + p[1]*p[i + 1]*p[n + 1]점화식은 위와 같이 도출할 수 있다.
유튜브에서 신찬수 교수님 강의 3번 보고 겨우 도출해냈다.
P는 입력으로 보통 주어지는 각 행렬의 행과 열 이다.
N은 행렬에 개수 이다.
그럼 여기서 우리가 모르는 값은 딱 하나 i
이 i를 1부터 N -1까지 반복문으로 돌려보면서 그중 가장 작은 값을 선택하면 된다.
즉 Bottom-UP 방식으로 필요한 값을 다 구해놓고 최소값을 선택하면서
2차원 배열을 채운다.
공부하다가 아쉬운 점
이해가 안간다
그래서 이해가 갈때까지 삽질 하면서 3회독 때리니까
큰 그림 정도는 그릴 수 있게 되었다.
