8/12 자료형의 복잡도, sort()

30

문자 pineapple에는 apple이라는 문자가 숨어 있습니다. 원범이는 이렇듯 문자열 속에 숨어있는 문자를 찾아보려고 합니다.

첫번째 입력에서는 문자열이 입력되고, 두번째에는 찾을 문자가 입력되어야 합니다.
그 문자가 시작하는 index를 반환하는 프로그램을 만들어 주세요

**입력**
pineapple is yummy
apple

**출력**
4
let sen = prompt('문장 입력')
let sen2 = prompt('단어 입력')

for(let i = 0; i<sen.length;i++) {
    if(sen[i] == sen2[0]) {
    console.log(i)
    }
    
}const data = prompt('문자열을 입력하세요');
const word = prompt('찾을 단어를 입력하세요');

console.log(data.indexOf(word)); 
/* indexOf() 메서드는 호출한 스트링 객체나 배열에서 
 * 주어진 값과 일치하는 값 혹은 요소의 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환합니다.
*/





31

자바스크립트 자료형의 복잡도

다음 배열 내장함수의 시간 복잡도가 O(1)이 아닌 것을 모두 고르시오.

1) arr[i]
2) arr.push(5)
3) arr.slice()
4) arr.pop()
5) arr.includes(5)

빅오란?
무언가를 실행하는데 필요한 단계수를 나타냄.
컴퓨터가 성능이 아주 빨라져서 예전과는 비교할 수 없지만
필요한 단계수가 1이라면 아주 빠르게 진행될 것을 알 수 있다.
하지만 필요한 단계수가 100이라면 컴퓨터의 성능을 제외하면 단계수가 1인 것보다 느리게 진행된다는 것을 알 수 있다.
즉 빅오는 알고리즘에 필요한 단계 수를 나타내는 것이다.

O(1)과 O(n)의 의미

O(1)은 “빅 오 1”이라고 읽는다. O(n)은 “빅 오 엔”이라고 읽는다.
뜻을 설명하자면 1은 단계수를 나타낸다. 즉 한단계가 걸린다는 것이다. 그렇다면 n은 무엇을까? 바로 자료구조의 길이만큼 만큼 걸린다는 뜻이다.

const arr = [1, 2, 3, 4, 5];

위와 같이 arr같은 배열이 있다. 이 배열에 숫자 3이 들어 있는지 확인하는 방법은 순서대로 값을 하나씩 비교하는 것이다. 인덱스 0번을 보고 3인지 확인하고 아니면 인덱스 1을 본다. 이와 같이 실행하다가 만약 3이 없으면 없다고 반환한다. 지금은 중간에 있지만 마지막에 3이 있었다면 모든 값을 다 확인하게 된다.
이게 O(n)이라고 할 수 있다.

배열에서 읽기는 O(1)이다. 컴퓨터는 인덱스를 통해서 바로 값을 읽을 수 있기 때문이다. 배열의 마지막 값을 삭제하거나, 배열의 마지막에 값을 넣는 것 또한 O(1)이다. 그래서 정답은 그 이외의 것인 3번과 5번이다.
중간에 넣거나 빼는 것은 왜 O(1)이 아닐까?
넣기 위해 값을 미뤄야하거나, 삭제하고 난 뒤에 중간에 값을 땡겨와야 하는 과정이 있기 때문이다.
slice의 경우 배열을 복사한다. 복사하기 위해서는 빈 값을 만들고 원래 값을 돌면서 push작업을 해준다. 또한 includes는 처음 값부터 하나하나씩 다 찾으면서 값이 들어있는 지 확인하기 때문에 O(n)이다.

출처 : https://minhanpark.github.io/today-i-learned/javascript-big-o/





34
키가 입력되면 순서대로 제대로 섰는지 확인하는 프로그램을 작성해보자.
(키는 공백으로 구분하여 입력됩니다.)

**입출력**

입력 : 176 156 155 165 166 169
출력 : NO

입력 : 155 156 165 166 169 176
출력 : YES
let unsorted = prompt('키를 입력하세요');
let sorted = "";

sorted = unsorted
  .split(" ")
  .sort(function(a, b) {
    return a - b;
  })
  .join(" ");

if (unsorted === sorted) {
  console.log("Yes");
} else {
  console.log("No");
}

sort()

arr.sort([compareFunction])
배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다.
기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다.
기존 배열이 정렬되는 것에 유의. 복사본이 만들어지는 것이 아닙니다.

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]
// 알파벳순
const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]
// 맨앞 1이라서 1다음 100000가 온다.

// 문자열로 비교한다고 보면된다.

var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
  return a - b;
});
console.log(numbers);

// [1, 2, 3, 4, 5]

compareFunction(a, b)이 0보다 작은 경우 a를 b보다 낮은 색인으로 정렬합니다. 즉, a가 먼저옵니다.

compareFunction(a, b)이 0을 반환하면 a와 b를 서로에 대해 변경하지 않고 모든 다른 요소에 대해 정렬합니다. 참고 : ECMAscript 표준은 이러한 동작을 보장하지 않으므로 모든 브라우저(예 : Mozilla 버전은 적어도 2003 년 이후 버전 임)가 이를 존중하지는 않습니다.

compareFunction(a, b)이 0보다 큰 경우, b를 a보다 낮은 인덱스로 소트합니다.

compareFunction(a, b)은 요소 a와 b의 특정 쌍이 두 개의 인수로 주어질 때 항상 동일한 값을 반환해야합니다. 일치하지 않는 결과가 반환되면 정렬 순서는 정의되지 않습니다.

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




2제곱, 3제곱, 4제곱을 할 수 있는 Factory 함수를 만들려고 합니다.

<pass>에 코드를 작성하여 two함수를 완성하세요.

function one(n){
    function two(){
        //pass
    }
    return two;
}

const a = one(2);
const b = one(3);
const c = one(4);

console.log(a(10));
console.log(b(10));
console.log(c(10));

답안

function one(n) {
  function two(value) {
    const sq = Math.pow(value, n); // value ** n 도 가능.
    return sq;
  }
  return two;
}

const a = one(2);
const b = one(3);
const c = one(4);

console.log(a(10));
console.log(b(10));
console.log(c(10));

변수 a에서 함수 one(2)을 실행한다. value는 undefined인 상태로 one 함수 안에 있는 two를 리턴한다. 즉 변수 a는 이제 two(value)를 가진 상태. 그리고 콘솔 값으로 a(10)을 실행하면, a가 two(value)를 가진 상태였기 때문에 two(10)을 실행합니다. Math.pow(value, n)에서 10의 2 제곱을 하는 형태로 값이 출력되고, 출력 값으로 100이 나오게 됩니다.

좋은 웹페이지 즐겨찾기