글 읽기 - (시간초과) JS로는 비트마스크 풀이가 불가능한가요?

amunre21 2년 전 0

그냥 전역배열을 이용해서 brute force로 풀었다가 비트마스크를 이용해서 다시 풀어보려고 했는데 시간초과를 통과하지 못 하고 있습니다..

이리저리 코드를 돌려보다가 brute force방식으로 무식하게 모든 조합을 구해서 풀었던것이 비트연산을 사용한코드보다 2배넘게 빠르다는 것을 발견하고 구글에 검색해보니 java script는 비트 연산 시 부동 소수점 숫자형을 정수형으로 변환 후 비트연산을 하고 다시 원래타입으로 되돌린다. .. 라는군요.

이러면 비트연산으로서의 장점이 전혀 없는것같은데, 제 코드가 문제인걸까요? 혹은 시간을 좀 더 늘려달라고 요청해야될까요... 아니면 JS는 비트연산을 활용한 문제풀이를 포기해야할까요?

혹시 몰라 일단 코드 첨부합니다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let stats = [];    //능력치 저장 배열
let min = Number.POSITIVE_INFINITY;
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성  
  let n = input.splice(0,1);  
  let bit_check = 0;
  //능력치 배열에 값 입력  
  for(let i =0;i<n;i++){
    stats.push(input[i].split(' ').map(el => el*1));
  };  
  //문제풀이용 재귀함수실행
  re(0,n,n/2,0,-1,bit_check);
  console.log(min)
  process.exit();
});

//팀들의 능력치값의 합을 계산하는 함수
let cal_re = function(n,bit_check){
  let sum_a = 0;
  let sum_b = 0;  
  let list_a = [];
  let list_b = [];
  //비트연산이 너무 느려서 따로 팀을 나눠주는 배열을 만들었습니다.  
  for(let i=0; i<n; i++){
    let i_pow = Math.pow(2,i);
    if((i_pow&bit_check)===i_pow)list_a.push(i);
    else list_b.push(i);
  }
  //모든 경우의 시너지값을 합산
  for(let i=0; i<(n/2); i++){
    for(let j=0; j<(n/2); j++){
      if(i!==j){
        sum_a+=stats[list_a[i]][list_a[j]];
        sum_b+=stats[list_b[i]][list_b[j]];        
      }
    }
  }  
  return sum_a-sum_b;
}

//N/2명의 팀원을 구성하는 모든 경우를 위한 재귀함수
let re = function(cnt,n,m,start,back,bit_check){
  
  if(cnt==m){  
    //해당 조합의 start팀과 link팀의 차이 계산, 전역적인 min값과 비교연산하여 갱신함
    min = Math.min(min, (Math.abs(cal_re(n,bit_check))));
    return ;
  }
  for(let i=start;i<n;i++){    
    let two_pow = Math.pow(2,i)
    //비트연산으로 중복체크합니다.
    if(((two_pow&bit_check)!==two_pow)&&i>back){      
      re(cnt+1,n,m,start,i,(bit_check|two_pow));
    }
  }
  return ;
}

paxbun 2년 전 1

JS의 number 타입은 64비트 부동소수점 타입을 사용하도록 되어있습니다. 정수나 실수 타입이 따로 있지는 않고요 (BigInt 제외). 제가 문제를 정확히 본 건 아닌데, 비트마스크 방식을 쓰면서 가장 좋은 퍼포먼스를 내고 싶으시다면 Uint32Array 같은걸 사용하시는 건 어떨까요?

amunre21 2년 전 0

@paxbun 좋은 정보 감사합니다. unit32array 같은 32비트 정수배열형식도 있군요!...

그런데 unit32array나 unit8array등의 차이는 어레이의 크기차이인 것 같은데, 제 경우는 시간초과가 문제입니다.

어레이의 자료크기를 바꿔주는것이 퍼포먼스 시간에 영향이 있을까요?

+ uint8array를 사용해서 비트마스크는 아니지만 boolean 배열을 만들어서 풀어봤는데 그 경우도 시간초과가 나는 것 같습니다.

++ 혹시 길이가 2짜리인 unit32array를 이용해서 그 안에 2진수를 담으라는 말씀일까요?

paxbun 2년 전 1

@amunre21 네 제가 C++로 풀 때도 uint32_t 하나만 필요했는데, Uint32Array에 정수 하나만 넣으셔서 푸시면 될 것 같아요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(시간초과) JS로는 비트마스크 풀이가 불가능한가요?

amunre21 2년 전 0

paxbun 2년 전 1

amunre21 2년 전 0

paxbun 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말