알고리즘 기초 Big-O

Big-O

• 빅오 표기법은 불필요한 연산을 제거하여 알고리즘분석을 쉽게 할 목적으로 사용함.

• 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타냄.

• 공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양을 나타냄. 요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아짐.

시간 복잡도

K번째 수를 구하는 방법

function solution(array, commands) {
    const answer = [];
    
    commands.forEach(comd => {
        const begin = comd[0] - 1;
        const end = comd[1];
        const k = comd[2] - 1;
        const cropped = array.slice(begin, end);
        const sorted = cropped.sort((n1,n2)=>n1-n2);
        answer.push(sorted[k]);
    });
    
    return answer;
}

풀이

1. slice를 이용하여 a번째부터 b번째의 숫자를 가진 배열을 만든다.

2. 만든 배열을 정렬한다.

3. 정렬된 배열의 k번째 숫자를 answer 배열에 push 한다.

사용된 속성

• slice() - 어떤 배열의 시작부터 끝까지(끝은 포함하지 않음) 복사본을 새로운 배열 객체로 반환함. 원본 배열은 바뀌지 않음.

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

• sort() - 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환함. 복사본이 아닌 원 배열이 정렬됨. 비교 속성을 넣지 않으면 문자열을 반환하고 유니 코드 순서로 비교, 정렬함.

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]

• push() - 배열의 끝에 요소를 추가하고, 배열의 새로운 길이를 반환함.

const animals = ['pigs', 'goats', 'sheep'];

const count = animals.push('cows');
console.log(count);
// expected output: 4
console.log(animals);
// expected output: Array ["pigs", "goats", "sheep", "cows"]

음양 더하기

//내 풀이
function solution(absolutes, signs) {
    for(let i =0; i<signs.length; i++){
        if(signs[i] === true ){
            continue;
        }
        else{
            absolutes[i] = -absolutes[i];
        }
    }
    const answer = absolutes.reduce((a,b) => a+b);
 
    return answer;
}

//참고 풀이
function solution(absolutes, signs) {
    let answer = 0;
    absolutes.forEach((v, i) => {
        if (signs[i]) {
            answer += v;
        } else {
            answer -= v;
        }
    })
    return answer;
}

풀이

1. 불린값의 성질을 사용해 if else문으로 answer에 값을 가감한다.

2. 모든 배열을 반복한다.

사용된 속성

• reduce - 배열의 각 요소에 대해 주어진 리듀서(reducer) 함수를 실행하고, 하나의 결과값을 반환함.

var sum = [1, 2, 3].reduce((a, b) => a + b);

가운데 글자 가져오기

//내 풀이
function solution(s) {
    function returnCenterCha(){
        
        const splits = s.split('');
        const divided = parseInt(splits.length/2);
        let spliced
        if(splits.length%2 === 0){
            spliced = splits.splice(divided-1,2);
        }
        else {
            spliced = splits.splice(divided,1);
        }
        const convertToString = spliced.toString().replace(",","");
        return convertToString
        }
   return returnCenterCha();
}

//참고 풀이
function solution(s) {
    const mid = Math.floor(s.length/2);
    return s.length % 2 === 1 ? s[mid] : s[mid-1]+s[mid];
}

풀이

1. 중간에 있는 수를 구한다.

2. 문자열 길이를 2로 나누었을 때 나머지가 1이면 가운데 수를, 그렇지 않으면 가운데 -1과 가운데 수를 반환한다.

사용된 속성

• Math.floor() - 소수점을 버리고 반환함.

console.log(Math.floor(5.95));
// expected output: 5

console.log(Math.floor(-5.05));
// expected output: -6

• parseInt() - 정수를 반환함.

var result = parseInt(13 / 5); // 값은 2
var remainder = 13 % 5; // 값은 3

• JS에서 콤마 없애는 방법

const numberStr = "123,456,789";

// 콤마 제거
const number = numberStr.replace(",", ""); 

• toString() - 배열에서 문자열을 반환.

const array1 = [1, 2, 'a', '1a'];

console.log(array1.toString());
// expected output: "1,2,a,1a"

핸드폰 번호 가리기

function solution(phone_number) {
      
    const sliced = phone_number.slice(-4);
    return "*".repeat(phone_number.length-4)+sliced
}

풀이

1. 전화번호 뒷 4자리를 추출한다.

2. 추출한 개수를 제외한 전화번호 수만큼 *를 반복한다.

3. 반복한 개수에 추출한 전화번호 뒷 4자리를 더한다.

사용된 속성

• repeat - 문자열을 주어진 횟수만큼 반복해 붙인 새로운 문자열을 반환함.

'abc'.repeat(2);    // 'abcabc'
'abc'.repeat(3.5);  // 'abcabcabc'

폰켓몬

//내 풀이
function solution(nums) {
    const max = parseInt(nums.length/2);
    const set = new Set(nums);
    const setSize = set.size;

    return max < setSize ? max : setSize
}

//참고 풀이
function solution(nums) {
    const max = parseInt(nums.length/2);

    return Math.min(max, new Set(nums).size);
}

풀이

1. 최대로 가져갈 수 있는 개수를 구한다.

2. Set 객체로 중복없는 배열을 구한다.

3. 이 둘을 비교하여 최대로 가져갈 수 있는 폰켓몬 수를 반환한다.

사용된 속성

• Set - 중복을 허용하지 않는 값을 모아놓은 Collection 객체.

var mySet = new Set();

mySet.add(1); // Set { 1 }
mySet.has(1); // true

const arr = ['a', 'b', 'c', 'b'];
const set = new Set(arr);

set.size; // 3

완주하지 못한 선수

function solution(participant, completion) {
    participant.sort()
    completion.sort()
    
    for(let i = 0; i<participant.length; i++){
        if(participant[i] !== completion[i]){
            return participant[i]
        }
    }
}

풀이

1. 각 파라미터를 문자순으로 정렬한다.

2. 정렬된 배열 중 일치하지 않는 원소가 있을 경우 participant의 원소를 반환한다.

예산

function solution(d, budget) {
    const arr = d.sort(function(a, b)  {
      return a - b;
    });
    
    let cnt = 0;
    let sum = 0;
    
    for(let i=0; i<arr.length; i++) {
        sum += arr[i]
        if(budget >= sum){
            cnt++
        }
    }
    return cnt;
}

풀이

1. sort 메소드로 부서별 금액을 정렬함.

2. 반복문으로 예산이 금액을 넘지 않을 때까지의 합과 지원 수를 구한다.

추가 info

• call by value (값에 의한 호출) - 함수 안에서 인자의 값이 변경되어도, 외부의 변수의 값은 변경되지 않음. call by reference (참조에 의한 호출) - 함수 안에서 인자의 값이 변경되면, 아규먼트로 전달된 객체의 값도 함께 변경.

모의고사

function solution(answers) {
    var answer = [];
    
    const sut1 = [1,2,3,4,5];
    const sut2 = [2,1,2,3,2,4,2,5];
    const sut3 = [3,3,1,1,2,2,4,4,5,5];
    
    let point = [0,0,0];
    
    for(let i = 0; i<answers.length; i++){
  		if(sut1[i % 5] === answers[i]){
            point[0] += 1;
        }
        if(sut2[i % 8] === answers[i]){
            point[1] += 1;
        }
        if(sut3[i % 10] === answers[i]){
            point[2] += 1;
        }
    }

    let maxCnt = Math.max(...point);

    for(let j=0; j<3; j++){
        if(point[j] === maxCnt){
            answer.push(j+1);
        }
    }
    
    return answer;
}

풀이

1. 수포자의 답을 const에 담는다.

2. 문제의 길이만큼 반복하여 각 배열의 숫자와 answers의 숫자가 일치하는지 확인하고, 일치하면 point를 1씩 올린다.

3. max 메소드를 사용하여 최대값을 알아낸후 최대값과 point가 일치하면 해당 숫자를 answer에 push한다.

사용된 속성

• 나머지 연산자(%) - 나누어진 후, 그 나머지를 반환함.

console.log(12 % 5);
// expected output: 2

• three dots(...) - 배열이라면 나머지 원소들을 배열로 만들어 리턴하고, 오브젝트라면 열거할수 있는 나머지 프로퍼티들을 묶어 오브젝트로 반환함.

const a = [1,2,3];
const aa = [...a, ...a];
console.log(aa) // [1, 2, 3, 1, 2, 3]

• max() - 입력값으로 받은 0개 이상의 숫자 중 가장 큰 숫자를 반환함.

Math.max(10, 20);   //  20

크거나 작은 수 구하는 알고리즘

function max(arr) {
    let largest;
    if(arr.length>0) {
		    largest=arr[0];}
    else { 
		    largest = 0;}

    for(let i=0;i<arr.length;i++) {
      if(arr[i]>largest)
      largest = arr[i];
    }
    return largest;
 }