Target sum dp버전 (복습)
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
// row -> 몇 개의 요소가 관여하였는가 ?
// col -> nums의 모든 요소들을 전부다 합한것의 * 2 + 1만큼의 크기를 가져야된다.
const sum = nums.reduce((a,b)=>a+b);
const dp = [...new Array(nums.length + 1)].map(()=>[...new Array(sum * 2 + 1)].map(()=>0));
dp[0][sum] = 1;
for(let row=0;row<nums.length;row++){
for(let col=0;col<dp[row].length;col++){
if(dp[row][col] !== 0){
dp[row+1][col-nums[row]] += dp[row][col]
dp[row+1][col+nums[row]] += dp[row][col]
}
}
}
return dp[nums.length][target + sum] ?? 0;
};Binary Matrix
가장 가까운 0과의 거리로 데이터 값을 변경하는 문제이다.
1을 발견하면 -> 해당 1로 부터 BFS를 실시하여 0을 발견하면 그 값을 저장시키도록 할 수 있으나, 비용이 매우커서 시간초과가 발생하게 된다.
해결 코드
distance를 레벨로 생각하고 풀자. + 새로운 결과 배열을 만들자.
0과의 최소거리가 0인 것들을 큐에 전부 집어넣는다. (루트에서 갈 수 있는 모든 자식들인 것임)
큐에서 이를 빼내면서 결과배열(해당 인덱스에)에 0을 저장한다. 빼낸 인덱스에서 갈 수 있는 자식들을 모두 넣는데, 이 때 최소 거리가 계산되지 않은 것들만 넣는다. (이미 들어간 것들은 0과의 최소거리가 구해졌으므로 넣지 않는다.)
고로 다음 반복에서 큐에 들어있는 것들은 모두 0과의 최소거리가 1인 경우 인셈. 꺼내면서 1을 저장해주고, 꺼낸 요소에서 갈 수 있으면서 최소거리가 계산되지 않은 요소들을 큐에 넣어준다.
이를 반복하면 모든 요소들의 0과의 최소거리가 저장된다.
다음은 위 아이디어로 구현한 코드 중 가장 성능이 좋은 코드이다.
var updateMatrix = function(matrix) {
const d = [[0,1],[0,-1],[1,0],[-1,0]]
const result = Array.from({length: matrix.length}, () => []);
const visit = [];
let queue = [];
let distance = 0;
// add all zeros to the queue
for(let i = 0; i < matrix.length; i++) {
for(let j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] === 0) {
result[i][j] = 0;
queue.push([i, j, 0])
}
}
}
while(queue.length){
const [r , c , lev] = queue.shift();
for(i=0;i<d.length;i++){
const [dr,dc] = d[i];
if(validate(r+dr,c+dc) && result[r+dr][c+dc] === undefined){
result[r+dr][c+dc] = lev+1;
queue.push([r+dr,c+dc,lev+1]);
}
}
}
return result;
function validate(r,c){
return matrix[r] !== undefined && matrix[r][c] !== undefined;
}
};
var updateMatrix = function(matrix) {
const d = [[0,1],[0,-1],[1,0],[-1,0]]
const result = Array.from({length: matrix.length}, () => []);
// [ [], [], [] ] 이 생성된다.
let queue = [];
let distance = 0;
for(let i = 0; i < matrix.length; i++) {
for(let j = 0; j < matrix[0].length; j++) {
// 0인 것들을 큐에 넣어준다. 0과의 최소거리 값이 레벨이 되므로, 최소거리가 0인 요소들을 모두 큐에 넣는다.
if(matrix[i][j] === 0) queue.push([i, j])
}
}
while(queue.length){
const nextQueue = [];
for([r,c] of queue){
if(result[r][c] === undefined){
result[r][c] = distance;
for(let i=0;i<d.length;i++){
const [dr,dc] = d[i];
if(validate(r+dr,c+dc)) nextQueue.push([r+dr,c+dc]);
}
}
}
distance++;
queue = nextQueue;
}
return result;
function validate(r,c){
return matrix[r] !== undefined && matrix[r][c] !== undefined;
}
};
더미 코드
var updateMatrix = function(matrix) {
const d = [[0,1],[0,-1],[1,0],[-1,0]]
const result = Array.from({length: matrix.length}, () => []);
let queue = [];
let distance = 0;
// add all zeros to the queue
for(let i = 0; i < matrix.length; i++) {
for(let j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] === 0) {
result[i][j] = 0;
queue.push([i, j, 0])
}
}
}
while(queue.length){
const [r , c , lev] = queue.shift();
result[r][c] = lev;
for(i=0;i<d.length;i++){
const [dr,dc] = d[i];
if(validate(r+dr,c+dc) && result[r+dr][c+dc] === undefined){
if(!queue.find(([tr,tc])=>(tr === r+dr && tc === c+dc)))
// 틀린 코드인 것 같다. 큐에 있는지를 점검할게 아니라 이미 큐에 들어갔었는지를 판단해야한다.
queue.push([r+dr,c+dc,lev+1]);
}
}
}
return result;
function validate(r,c){
return matrix[r] !== undefined && matrix[r][c] !== undefined;
}
};
Frontend Ninja