우크라이나어 하는 개발자

버블 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

const bubbleSort = (arr) => {
  for (let i = arr.length; i >= 0; i--) {
    let noSwap = true
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        noSwap = false
      }
    }
    if (noSwap) break
  }
  return arr
}

선택 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

const selectionSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[lowest] > arr[j]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      swap(arr, i, lowest)
    }
  }
  return arr
}

삽입 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    console.log(arr)
    let currentValue = arr[i]
    for (let j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      arr[j + 1] = arr[j]
      arr[j] = currentValue
    }
  }
  return arr
}

오픈튜토리얼스 8.13 ~ 8.26  머신러닝야학에서 배운

레몬에이드 판매량 예측, 보스턴 집값 예측, 붓꽃 분류를 tensorflow.js로 만들었습니다.

오픈튜토리얼스 머신러닝야학 내용은 아래 링크를 참조해 주세요!

https://opentutorials.org/course/4570

nodejs version: 12.18.3

tensorflow.js version: 2.3.0

전체 코드

  const lemonadeCSV = await readCSV('./data/lemonade.csv')

  // 데이터를 tensor 형태로 만들기
  const temperature = []
  const sales = []
  for (let i = 0; i < lemonadeCSV.length; i++) {
    temperature.push(Number(lemonadeCSV[i]['온도']))
    sales.push(Number(lemonadeCSV[i]['판매량']))
  }

  const independent = tf.tensor1d(temperature)
  const dependent = tf.tensor1d(sales)

  independent.print()
  dependent.print()

  // 모델 만들기
  const input = tf.input({ shape: [1] })
  const output = tf.layers.dense({ units: 1 }).apply(input)
  const model = tf.model({
    inputs: input,
    outputs: output
  })

  model.compile({ optimizer: tf.train.adam(), loss: tf.losses.meanSquaredError })
  model.summary()

  // 모델 학습
  const { history: { loss: loss } } = await model.fit(independent, dependent, { epochs: 15000 })

  // 마지막 loss 출력
  console.log(loss[loss.length - 1])

  // 판매량 예측
  model.predict(tf.tensor1d([40])).print()

CSV 데이터 가져오기

tf.data.csv() 함수가 작동하지 않아 csv를 읽어오는 함수를 만들게 되었습니다. ㅠㅠ

node.js fs 모듈과 csv-parser npm 모듈을 사용하였습니다.

ReadStream을 사용하여 csv 파일을 읽고 객체 배열 형태로 값을 반환합니다.

const fs = require('fs')
const csv = require('csv-parser')

/**
 * 
 * @param { string } csvFilePath csv 파일 주소
 * 리턴값은 [{'a':'1', 'b':'2'}] 객체 배열 형태입니다.
 */
const readCSV = (csvFilePath) => {
  return new Promise((resolve, reject) => {
    const dataSet = []
    const readStream = fs.createReadStream(csvFilePath)
    readStream.pipe(csv()).on('error', () => { return reject(new Error('Error reading file')) }).on('data', (data) => { dataSet.push(data) }).on('end', () => { resolve(dataSet) })
  })
}

module.exports = readCSV

데이터를 Tensor 형으로 만들기

  const temperature = []
  const sales = []
  for (let i = 0; i < lemonadeCSV.length; i++) {
    temperature.push(Number(lemonadeCSV[i]['온도']))
    sales.push(Number(lemonadeCSV[i]['판매량']))
  }

  const independent = tf.tensor1d(temperature)
  const dependent = tf.tensor1d(sales)
 
 /*
 Tensor
    [20, 21, 22, 23, 24, 25]
Tensor
    [40, 42, 44, 46, 48, 50]
*/

모델 만들기

tensorflow.js와 python tensorflow 다른점은 apply를 사용해 layer를 쌓고

parameter 값을 Object로 사용한다는 점입니다.  

  const input = tf.input({ shape: [1] })
  const output = tf.layers.dense({ units: 1 }).apply(input)
  const model = tf.model({
    inputs: input,
    outputs: output
  })

  model.compile({ optimizer: tf.train.adam(), loss: tf.losses.meanSquaredError })
  model.summary()

model Summary :

_________________________________________________________________
Layer (type)                 Output shape              Param #
========================================
input1 (InputLayer)          [null,1]                  0
_________________________________________________________________
dense_Dense1 (Dense)         [null,1]                  2
========================================
Total params: 2
Trainable params: 2
Non-trainable params: 0
_________________________________________________________________

모델 학습과 예측

model.fit()은 history를 반환하고 history에는 지금까지 loss 값을 가지고 있습니다.

결과: 

0.015542778186500072

Tensor 
     [[78.7350845],]

  // 모델 학습
  const { history: { loss: loss } } = await model.fit(independent, dependent, { epochs: 15000 })

  // 마지막 loss 출력
  console.log(loss[loss.length - 1])

  // 판매량 예측
  model.predict(tf.tensor1d([40])).print()

가장 간단한 lemonade 판매량 예측이었습니다. 하지만 python이 아니라 javascript로 하고 자료도 많지 않아서 tensorflow.js API reference 와 튜토리얼을 보면서 했습니다. 

tensorflow.js API reference 는 사용법이 자세히 나와있지 않아 구글링을 많이 하였습니다.

https://js.tensorflow.org/api/2.3.0/

제출 코드

function solution(answers) {
  let matchCount = new Object();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  for (let i = 0; i < answers.length; i++) {
    let order1 = i % supoza1.length;
    let order2 = i % supoza2.length;
    let order3 = i % supoza3.length;

    if (answers[i] === supoza1[order1]) {
      matchCount[1] = ++matchCount[1] || 1;
    }

    if (answers[i] === supoza2[order2]) {
      matchCount[2] = ++matchCount[2] || 1;
    }

    if (answers[i] === supoza3[order3]) {
      matchCount[3] = ++matchCount[3] || 1;
    }
  }
  let result = whoIsBest(matchCount);
  return result;
}

function whoIsBest(matchCount) {
  let result = new Array();
  let max = Math.max(...Object.values(matchCount));
  for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }
  result.sort();
  return result;
}

수포자가 가진 배열 인덱스에 answers 배열 인덱스를 맞추기 위해 나머지 연산(%)을 사용하였습니다.

    let order1 = i % supoza1.length;
    let order2 = i % supoza2.length;
    let order3 = i % supoza3.length;

정답이라면 matchCount Object에 수포자에 해당되는 번호를 key로 하고

1을 더하거나 key가 없을 때는 1로 초기화합니다. 

    if (answers[i] === supoza1[order1]) {
      matchCount[1] = ++matchCount[1] || 1;
    }

whoIsBest 함수는 matchCount Object를 받아 결과값(ex [2,3])을 반환합니다.

function whoIsBest(matchCount) {
  let result = new Array();
  let max = Math.max(...Object.values(matchCount));
  for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }
  result.sort();
  return result;
}

Object 가 가진 value 들 중에 가장 큰 값을 max로 선정합니다.

let max = Math.max(...Object.values(matchCount));

Object.entries method를 사용해 key와 value를 얻어내어 

value가 max와 같다면 key를 Number로 바꾸어 result 배열에 추가합니다.

for (const [key, value] of Object.entries(matchCount)) {
    if (value === max) {
      result = result.concat(Number.parseInt(key));
    }
  }

Solution with using filter

배열 filter 함수를 사용한 방법

function solution2(answers) {
  let matchCount = new Object();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  matchCount[1] = answers.filter(
    (answer, index) => answer === supoza1[index % supoza1.length]
  ).length;
  matchCount[2] = answers.filter(
    (answer, index) => answer === supoza2[index % supoza2.length]
  ).length;

  matchCount[3] = answers.filter(
    (answer, index) => answer === supoza3[index % supoza3.length]
  ).length;
 
  let result = whoIsBest(matchCount);
  return result;
}

Solution not using Object and fuction whoIsBest

Object와 whoIsBest 메소드를 사용하지 않은 방법

function solution(answers) {
  let result = new Array();
  const supoza1 = [1, 2, 3, 4, 5];
  const supoza2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoza3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  const match1 = answers.filter(
    (answer, index) => answer === supoza1[index % supoza1.length]
  ).length;
  const match2 = answers.filter(
    (answer, index) => answer === supoza2[index % supoza2.length]
  ).length;
  const match3 = answers.filter(
    (answer, index) => answer === supoza3[index % supoza3.length]
  ).length;
  
  let max = Math.max(match1, match2, match3);
  
  [match1, match2, match3].forEach((match, index) => {
    if (match === max) {
      result = result.concat(index + 1);
    }
  });
  
  return result;
}

function charCount(input) {
  if (!input) {
    return {};
  }
  if (typeof input !== 'string') {
    throw new Error('Input is not String');
  }
  let result = new Object();
  //  문자열을 소문자로 바꾸고 문자 단위로 나눈 뒤
  // 소문자이고 숫자인지 정규식을 사용해 필터링하고 정렬합니다.
  let charArray = input
    .toLowerCase()
    .split('')
    .filter((c) => /[a-z0-9]/.test(c))
    .sort();
  for (let i = 0; i < charArray.length; i++) {
    let char = charArray[i];
    result[char] = result.hasOwnProperty(char) ? result[char]++ : 1;
  }
  return result;
}

출력 예시

console.log(charCount('abc'));
// { a: 1, b: 1, c: 1 }
console.log(charCount('c b a a a 1 2 3'));
// { '1': 1, '2': 1, '3': 1, a: 1, b: 1, c: 1 }
console.log(charCount(123));
// Error: Input is not String
console.log(charCount(''));
// {}
console.log(charCount());
// {}
console.log(charCount('Hi, my name is Jinsu!!'));
// { a: 1, e: 1, h: 1, i: 1, j: 1, m: 1, n: 1, s: 1, u: 1, y: 1 }

다른 방식

function charCount2(str) {
  let obj = new Object();
  for (const char of str) {
    char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      obj[char] = ++obj[char] || 1;
    }
  }
  return obj;
}

let names = ["Michael", "Bab", "Andrea"];
let num = [4, 5, 6, 9, 8, 7, 1, 2, 3, 0, 11, 12, 13, 10];
let values = [true, false, {}, [], 1, "a"];
// [ 'Andrea', 'Bab', 'Michael' ]
// [ [], 1, {}, 'a', false, true ]
// [0, 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(names.sort());
console.log(values.sort());
console.log(num.sort());

문자열은 알바벳 순으로 정렬됩니다.

배열, 숫자, 객체, 문자열, false, true 순으로 정렬이 됩니다.

숫자는 문자열의 유니코드 코드 포인트를 따르기 때문에

1 11 12 2 3 4 순서로 정렬됩니다. 

숫자 순서로 정렬하기 위해서는 sort() 안에 비교 함수를 넣습니다

console.log(num.sort((a, b) => a - b));

/*
오름차순
[
   0,  1, 2, 3,  4,  5,
   6,  7, 8, 9, 10, 11,
  12, 13
]
*/

console.log(num.sort((a, b) => b - a));

/*
내림차순
[
  13, 12, 11, 10, 9, 8,
   7,  6,  5,  4, 3, 2,
   1,  0
]
*/

Map을 이용한 정렬

let list = [
  'korea',
  'Ukraine',
  'Russia',
  'japan',
  'china',
  'America',
  'poland',
  'Rumania',
];

// 임시 배열은 위치 및 정렬 값이있는 객체를 보유합니다.
let mapped = list.map(function (element, index) {
  return { index: index, value: element.toLowerCase() };
});
console.log(mapped);
// 축소 치를 포함한 매핑 된 배열의 소트
mapped.sort(function (a, b) {
  return +(a.value > b.value) || +(a.value === b.value) - 1;
});
console.log(mapped);
// 결과 순서를 위한 컨테이너
let result = mapped.map(function (element) {
  return list[element.index];
});
console.log(result);​

/*
let mapped = list.map(function (element, index) {
  return { index: index, value: element.toLowerCase() };
});
[
  { index: 0, value: 'korea' },
  { index: 1, value: 'ukraine' },
  { index: 2, value: 'russia' },
  { index: 3, value: 'japan' },
  { index: 4, value: 'china' },
  { index: 5, value: 'america' },
  { index: 6, value: 'poland' },
  { index: 7, value: 'rumania' }
]
mapped.sort(function (a, b) {
  return +(a.value > b.value) || +(a.value === b.value) - 1;
});
[
  { index: 5, value: 'america' },
  { index: 4, value: 'china' },
  { index: 3, value: 'japan' },
  { index: 0, value: 'korea' },
  { index: 6, value: 'poland' },
  { index: 7, value: 'rumania' },
  { index: 2, value: 'russia' },
  { index: 1, value: 'ukraine' }
]
let result = mapped.map(function (element) {
  return list[element.index];
});
[
  'America', 'china',
  'japan',   'korea',
  'poland',  'Rumania',
  'Russia',  'Ukraine'
]
*/

[참조]

Array.prototype.sort()

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

수행시간 비교: 기본 for loop < forEach < for of < for in

기본 for loop가 가장 빠릅니다.

Example

기본 for loop 사용: 3.799ms
for in loop 사용: 359.135ms
forEach 사용: 21.931ms
for of 사용: 26.932ms

function Loop1(nList) {
  let total = 0;
  for (let i = 0; i < nList.length; i++) {
    total += nList[i];
  }
  return total;
}

function Loop2(nList) {
  let total = 0;
  for (const num in nList) {
    total += num;
  }
  return total;
}

function Loop3(nList) {
  let total = 0;
  nList.forEach((num) => {
    total += num;
  });
  return total;
}

function Loop4(nList) {
  let total = 0;
  for (const num of nList) {
    total += num;
  }
  return total;
}

let n = 1000000;
let nList = new Array();
for (let i = 1; i <= n; i++) {
  nList.push(i);
}

console.time("기본 for loop 사용");
Loop1(nList);
console.timeEnd("기본 for loop 사용");

console.time("for in loop 사용");
Loop2(nList);
console.timeEnd("for in loop 사용");

console.time("for Each 사용");
Loop3(nList);
console.timeEnd("for Each 사용");

console.time("for of 사용");
Loop4(nList);
console.timeEnd("for of 사용");

1. forEach 문은 배열에서만 사용이 가능합니다.

2. for in 문은 모든 객체에서 사용이 가능하지만 key에만 접근합니다. value는 key를 사용해 접근해야 합니다.

3. for of 문은 컬렉션 개체가 [Symbol.iterator] 속성]을 가져야 합니다.

let sample = [1, 2, 3, 4, 5];
sample.Case = "I'am in the Cafe";

for (const key in sample) {
  if (sample.hasOwnProperty(key)) {
    console.log(key, sample[key]);
  }
}

// 0 1
// 1 2
// 2 3
// 3 4
// 4 5
// Case I'am in the Cafe

for (const iterator of sample) {
  console.log(iterator);
}

// 1
// 2
// 3
// 4
// 5

Big O of Objects

1. 삽입 O(1)
2. 제거 O(1)
3. 탐색 O(n)
4. 접근 O(1)

Big O of Object mehtods

1. Object.keys() O(n)
2. Object.values() O(n)
3. Object.entries() O(n)
4. Object.hasOwnProperty("키 이름") O(1)

Big O of Arrays

1. 탐색 O(n)
2. 접근 O(1)

Big O of Array methods

1. push O(1)
2. pop O(1)
3. shift O(n)
4. unshift O(n)
5. concat O(n)
6. slice O(n)
7. splice O(n)
8. sort O(nlogn)
9. forEach/map/filter/reduce 등 O(n)

function solution(board, moves) {
  let answer = 0;
  let basket = new Array();
  for (let i = 0; i < moves.length; i++) {
    let pick = moves[i] - 1;
    let doll = 0;
    for (let j = 0; j < board.length; j++) {
      if (board[j][pick] > 0) {
        doll = board[j][pick];
        board[j].splice(pick, 1, 0);
        break;
      }
    }

    if (doll > 0) {
      basket.push(doll);
    }
    if (basket.length > 1) {
      let last = basket[basket.length - 1];
      let beforeLast = basket[basket.length - 2];
      if (last === beforeLast) {
        basket.splice(basket.length - 2, 2);
        answer += 2;
      }
    }
  }
  return answer;
}

let board = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];

let moves = [1, 5, 3, 5, 1, 2, 1, 4];

basket: 뽑은 인형을 담는 배열

pick: moves 배열 값으로 선택되는 세로축 번호

doll: 뽑은 인형 번호, 0은 빈 공간

for (let j = 0; j < board.length; j++) {
  if (board[j][pick] > 0) {
    doll = board[j][pick];
    board[j].splice(pick, 1, 0);
    break;
  }
}​

board.length는 인형뽑기 깊이를 의미합니다. 인형 번호가 1 이상이고 빈 공간이 0입니다.

board[j][pick]가 0보다 큰 경우는 인형이 있다는 것이고 doll에 인형 번호를 줍니다.

그리고 splice 함수를 이용해 인형이 있던 자리값을 0으로 바꾸어 줍니다.

인형을 뽑았기 때문에 반복문을 종료합니다.

 if (doll > 0) {
   basket.push(doll);
 }

board에서 인형을 뽑을 때 pick이 지정한 세로축에 인형이 없을 수도 있습니다!!

그러면 doll은 0인 상태인지 확인하고 basket에 인형을 담습니다.

    if (basket.length > 1) {
      let last = basket[basket.length - 1];
      let beforeLast = basket[basket.length - 2];
      if (last === beforeLast) {
        basket.splice(basket.length - 2, 2);
        answer += 2;
      }
    }

basket에 둘 이상이 있어야 뽑은 인형과 바로 전에 뽑은 인형을 비교할 수 있습니다.

방금 뽑은 인형과 이전에 뽑은 인형을 비교해 같다면

basket에서 이 둘을 splice를 이용해 제거합니다. 그리고 두 인형이 제거되었으므로 answer에 2를 더해줍니다.