2차원 배열 dp - 코딩테스트 공부
2차원배열을 이용하여 최솟값을 구하는 문제인데, 그리디로 접근해서 풀다가 오래걸려서 풀이를 봤다.
dp와 그리디는 한 끗 차이라더니...아무튼.
풀이는 이렇다.
dp[i][j]는 i알고력, j코딩력에 도달할때의 최소시간 이다.dp[alp][cop]를 0으로 초기화해준다. 현재 가지고있는 알고력, 코딩력에 도달하는 시간은 0이기 때문이다.- dp 테이블을 채워준다.
for(let i = alp; i<=max_alp_req; i++){
for(let j = cop; j<=max_cop_req; j++){
//다음 알고력 도달할때의 최소시간은, 공부해서 1을 더하거나 문제를 풀었을 때 이다.
if(i<max_alp_req) dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1);
//코딩력도 마찬가지
if(j<max_cop_req) dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1);
//여기가 핵심로직!
for(let k = 0; k<problems.length; k++){
const [alp_req, cop_req, alp_rwd, cop_rwd, cost] = problems[k];
//현재 알고력, 코딩력으로 도달할수 없는 문제라면, 넘어간다.
if(i < alp_req || j < cop_req) continue;
//문제중 필요한 최대 알고력, 최대 코딩력을 넘지 않도록 유의한다.
const nI = Math.min(i+alp_rwd, max_alp_req);
const nJ = Math.min(j+cop_rwd, max_cop_req);
//아무튼 현재 알고력+문제풀기, 현재코딩력+문제풀기 인덱스에 있는 최소시간과 와 현재에 cost를 더한값을 비교한다.
dp[nI][nJ] = Math.min(dp[nI][nJ], dp[i][j] + cost);
}
}
}2차원 배열 dp는 접근법이 잘 생각나지 않는다.
그림을 그려보거나 어떻게 해야할까 감이 잡히지 않는다. 혹시 2차원 dp 감 잡는법 아시는분이 있으면 댓글로 남겨주세요...!!😥
그리고 이상하게 시간초과가 났었다.
for...of와 for문
실패한게 for...of문이고 성공한게 단순 for문이다.
속도차이가 왜 그렇게 날까?
for...of는 이터레이터를 사용하여 next()를 호출해 다음 엘리먼트를 가져온다.
이에비해 for문은 인덱스를 직접 조작하기때문에 속도 차이가 벌어진다.
=> 코딩테스트 문제 풀땐 왠만하면 for문을 사용하자.
ts challenge
두가지 ts challenge를 파헤쳐보자
get tuple length
튜플의 길이를 구해오는 타입을 정해야한다.
처음에는 단순히 이렇게 접근했다.
사용할때 에러는 없지만, 구현부에 에러가 발생한다. T에 length라는 프로퍼티가 있는지 없는지 모른다
따라서 length라는 프로퍼티도 같이 넣어주면 될 것 같다.
type Length<T extends {length:number}> = T['length']
하지만 number타입을 받았을때는 에러가 발생한다. 물론 문제의 목적은 배열의 길이를 반환하는 유틸타입이기에 이게 맞는 것 같다.
추천을 두번째로 많이 받은 사람의 정답을 보았다.
type Length<T> = T extends { length : infer R } ? R : never;infer로 조건문을 이용한다. length 프로퍼티가 들어있으면, length프로퍼티에 넣어주고, 아니라면 never를 넣어준다.
이러면 number에 오류가 발생하지 않는다. 하지만 배열의 길이를 반환하는 유틸타입이기에 length프로퍼티가 없다면, 오류를 반환하는게 타입적으로 더 맞는 것 같다!
MyExclude
T에서 U에 할당할 수 있는 타입을 제외하는 내장 제네릭 Exclude<T, U>를 이를 사용하지 않고 구현하세요.
이는 분산 조건부 타입을 응용하면 된다.
type MyExclude<T, U> = T extends U ? never : T
MyExclude<'a' | 'b' | 'c', 'a'> // 'b' | 'c'유니온타입이 조건부타입에 들어왔을 경우, 타입 평가시간에 묶인 타입 하나하나마다 조건을 검사하여 처리한다.
//이렇게 순서대로 들어온다.
'a' extends 'a' ? never : 'a'
'b' extends 'a' ? never : 'b'
'c' extends 'a' ? never : 'c'따라서 never를 만난 'a'는 자연스레 없어져 타입에 'b'|'c'만 남아있다.
유니온 타입이 조건부를 만나면 전개되는 것에 유의하자!
