アルゴリズムシミュレーション試験
15868 ワード
詳細について
模擬試験
Brute Forceテクノロジー-繰り返し/条件文を使用してすべてのコンテンツをテストする方法 シーケンス(Permutation)-繰り返しが許可されていない場合、n個の要素のうちr個の要素を以下に示す方法 再帰呼び出し-N個の数字の中からMを選択した場合、NとMが非常に大きい数字の場合、 .ビットマスク-バイナリ表現を使用する方法 BFS、DFSの利用方法
1つ目の方法よりも2つ目の方法の方が速い.
配列の重複文の使用方法とパフォーマンスについて理解しました
<アレイ方法のパフォーマンスの比較>
大略
通常のfor文が最も速く、最も効率的です.
filterも速いですが、大容量アレイを処理するとメモリがオーバーフローする可能性があります.(地図も似ています)
reduceの利用率が高い
ブログ参照
模擬試験
数学は数学を放棄する人の略語である.「囚人3人組」は模擬試験で数学の問題を全部撮りたいと思っている.最初の問題から最後の問題まで、執胞子は以下の通りである.
1番捕手の撮り方:1,2,3,4,5,1,2,3,4,5...
2番捕手の撮り方:2、1、2、3、2、4、2、5、2、2、3、2、4、2、5...
3番捕手の撮り方:3,3,1,1,2,2,4,5,5,3,3,1,2,2,4,5,5...
最初の問題から最後の問題までの正解が順番に並んでいる場合は、最も多くの質問に答えた人が誰なのか、答えを並べて返すように解答関数を書いてください.
せいげんじょうけん
試験には最大10000問が含まれている.
質問の答えは1 2 3 4 5のうちの1つです.
点数が一番高い人が何人かいる場合は、戻った値を昇順に並べてください.//########################### solution 1 ###########################
function solution(answers) { //조금 느렸다. answer을 filter 3번씩 해서?
let person1 = [1,2,3,4,5]
let person2 = [2,1,2,3,2,4,2,5]
let person3 = [3,3,1,1,2,2,4,4,5,5]
let gotAns1 = answers.filter((got,idx) => got === person1[idx%5]).length
let gotAns2 = answers.filter((got,idx) => got === person2[idx%8]).length
let gotAns3 = answers.filter((got,idx) => got === person3[idx%10]).length
let max = Math.max( gotAns1, gotAns2, gotAns3)
let result = []
if( gotAns1 === max){
result.push(1)
}
if( gotAns2 === max){ //else if 하니까 안됬음 왜?
result.push(2)
}
if(gotAns3 === max){
result.push(3)
}
return result;
}
//########################### solution 2 ###########################
function solution(answers) { // 훨씬 빠름
var answer = [];
const man1 = [1, 2, 3, 4, 5];
const man2 = [2, 1, 2, 3, 2, 4, 2, 5];
const man3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
let count = [0, 0, 0];
for(let i = 0; i < answers.length; i++) {
if(answers[i] == man1[i % man1.length]) count[0]++;
if(answers[i] == man2[i % man2.length]) count[1]++;
if(answers[i] == man3[i % man3.length]) count[2]++;
}
const max = Math.max(count[0], count[1], count[2]);
for(let i = 0; i < count.length; i++) {
if(max == count[i]) answer.push(i + 1);
}
return answer;
}
Point
answers.filter((got,idx) => got === person1[idx % person1.length]).length演算子「%」を使用する原理は、小さい数字(idx)を大きな数字(人1.の長さ)に分け、残りの数字は小さい数字を維持することです.
「完全探索」というキーワードのせいか、最近習ったdfsを思い出して複雑に書いていますが、実は完全探索の方法はいろいろあります.
//########################### solution 1 ###########################
function solution(answers) { //조금 느렸다. answer을 filter 3번씩 해서?
let person1 = [1,2,3,4,5]
let person2 = [2,1,2,3,2,4,2,5]
let person3 = [3,3,1,1,2,2,4,4,5,5]
let gotAns1 = answers.filter((got,idx) => got === person1[idx%5]).length
let gotAns2 = answers.filter((got,idx) => got === person2[idx%8]).length
let gotAns3 = answers.filter((got,idx) => got === person3[idx%10]).length
let max = Math.max( gotAns1, gotAns2, gotAns3)
let result = []
if( gotAns1 === max){
result.push(1)
}
if( gotAns2 === max){ //else if 하니까 안됬음 왜?
result.push(2)
}
if(gotAns3 === max){
result.push(3)
}
return result;
}
//########################### solution 2 ###########################
function solution(answers) { // 훨씬 빠름
var answer = [];
const man1 = [1, 2, 3, 4, 5];
const man2 = [2, 1, 2, 3, 2, 4, 2, 5];
const man3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
let count = [0, 0, 0];
for(let i = 0; i < answers.length; i++) {
if(answers[i] == man1[i % man1.length]) count[0]++;
if(answers[i] == man2[i % man2.length]) count[1]++;
if(answers[i] == man3[i % man3.length]) count[2]++;
}
const max = Math.max(count[0], count[1], count[2]);
for(let i = 0; i < count.length; i++) {
if(max == count[i]) answer.push(i + 1);
}
return answer;
}
1つ目の方法よりも2つ目の方法の方が速い.
配列の重複文の使用方法とパフォーマンスについて理解しました
<アレイ方法のパフォーマンスの比較>
大略
通常のfor文が最も速く、最も効率的です.
filterも速いですが、大容量アレイを処理するとメモリがオーバーフローする可能性があります.(地図も似ています)
reduceの利用率が高い
ブログ参照
Reference
この問題について(アルゴリズムシミュレーション試験), 我々は、より多くの情報をここで見つけました https://velog.io/@nala723/Algorithm모의고사テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol