알고리즘은 감자를 상하게 한다

-박감자-

알고리즘 풀이

새로 배운 로직 혹은 메소드를 정리하면서 문제를 푸는 습관을 들여야할 것 같다. 가끔 푼 문제더라도 "이거 어떻게 했더라" 싶은게 있어서...

약수 구하기

자주 사용하던 약수 구하는 로직은 아래와 같다. n의 약수를 구하는 로직

function findDivisor(n) {
  let divisors = [];
  for (let i = 1; i <= n; i++) {
  	if (n % i === 0) {
    	divisors.push(i);
    }
  }
  return divisors;
}

보다시피 1부터 n까지의 모든 숫자를 돌며 n을 나누었을 때 나머지가 0인지 일일이 확인하는 방법이다. 혹시나 다른 방법이 없나 찾아보다가 약수가 n의 반이 되는 숫자들과 n 자신으로만 이루어진다는 글을 보게 되었다.

예시를 보자면

[1, 2, 3, 4, 6, 12] -> 12의 약수
[1, 13] -> 13의 약수
[1, 2, 4, 5, 10, 20, 25, 50, 100] -> 100의 약수

소수인 경우 패턴을 찾기는 힘들지만 그래도 n/2 아래의 약수가 되는 수들과 n으로만 이루어진 것을 확인 할 수는 있었다. 따라서 100의 약수를 찾는다면 1부터 100까지 도는게 아니라, 1부터 50까지만 돌고 100만 추가하면 100번 돌아야 되는 함수를 50번을 줄일 수 있다. 아래는 이 패턴을 적용한 로직

function findDivisor(n) {
  let divisors = [];
  for (let i = 1; i <= n/2; i++) {
    if (n % i === 0) divisors.push(i);  
  }
  // n만 추가해주기
  divisors.push(n);
  
  return divisors;
}

사실 time complexity를 따졌을 때 새로운 방법이나 이전 방법이나 똑같이 O(n)이기 때문에 유의미한 건 아니지만 어쨌든 새로운 방법을 찾아봤다는 수확에 의미를 두면 좋을 것 같다.

약수의 개수와 덧셈

접근한 방법은

1. left에서 right까지만 도는 반복문이 필요
2. 그 안에서 각 숫자의 약수의 개수를 찾는 로직이 필요
3. 찾은 후 개수가 짝수면 +, 홀수면 -를 붙여서 합산

그래서 틀을 짜게 되면

function solution(left, right) {
  // 합산한 값을 저장하는 변수
  let answer = 0;
  // left -> right 도는 반복문
  for (let i = left; i <= right; i++) {
    // 각 i의 약수 개수 구하기
    let divisors = 0;
    // (약수 개수 구하는 로직)
    
    // 약수의 개수 짝/홀 판별
    answer += (divisors % 2 === 0) ? i : -i;
  }
  return answer;
}

짝/홀 판별은 쓰다보니 삼항연산자가 편할것 같아서 사용했다. 짝수면 i를 더하고 아니면 -i를 더하는 식으로

알고리즘을 완성시키면

function solution(left, right) {
  // 합산한 값을 저장하는 변수
  let answer = 0;
  // left -> right 도는 반복문
  for (let i = left; i <= right; i++) {
    // 각 i의 약수 개수 구하기
    let divisors = 0;
    for (let j = 1; j <= i/2 j++) {
      if (i % j === 0) divisors += 1;
    }
    divisors += 1;
    
    // 약수의 개수 짝/홀 판별
    answer += (divisors % 2 === 0) ? i : -i;
  }
  return answer;
}

완성!

분수의 덧셈 문제

다음은 공약수가 필요한 문제로 생각보다 조금 오래 걸렸다.

왜냐하면 문제를 처음 봤을때 그냥 자연스럽게 최소공배수를 찾아서 분모만 통일하면 되는 거 아닌가 했다가 약분을 잊어먹었다.

그래서 바꾼 로직이

1. 분모을 모두 곱해 공통 분모를 만든다
2. 분자를 분자1 * 분모2 + 분자2 * 분모1로 지정
3. 최대공약수로 나눈다

처음부터 최소공배수는 구할 필요없이 일단 계산을 한 뒤에 최대공약수로 나누는 것이 가장 빨라 보였다.

위에서 한 약수 찾기를 조금 변형하여서 아래와 같은 코드가 나온다.

function solution(numer1, denom1, numer2, denom2) {
    let numer = numer1 * denom2 + numer2 * denom1;
    let denom = denom1 * denom2;
    
    let gcd = 1;
    // 최대 공약수찾기
    for (let i = 2; i <= Math.min(denom, numer); i++) {
        if (denom % i === 0 && numer % i === 0) {
            gcd = i;
        }
    }
    
    return [numer / gcd, denom / gcd];
}

반복문에서 i의 제한을 최종 분모와 분자 중 작은 수로 제한해놓았다. 그리고 1은 모두의 약수이므로 시작을 2부터하는 방향으로 횟수를 조금 줄였다고 생각했는데

저렇게 시간이 평소의 10배 이상이 걸리는 케이스들이 있었다. 찾아보니 반복문을 이용한 최대공약수 찾기는 효율적이지 못하다고 한다.

유클리디언 알고리즘 (Euclidean algorithm)

Greatest Common Divisor (GCD) 최대공약수를 찾아내는 방법으로 유명한 알고리즘

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

예시를 사용해서 설명해보자면
180과 192의 최대공약수를 구하고자 할때
a = 180, b = 192로 두고 계산하면

1번째 while 반복문
a,b 중 큰 수를 a로, 작은수를 b로 재조정해 줌
[a, b] = [192, 180 % 192 = 180]

2번째 
[a, b] = [180, 192 % 180 = 12]

3번째
[a, b] = [12, 180 % 12 = 0]
// b가 0이 되었으므로 4가 최대공약수!

이렇게 3번만에 최대공약수를 찾아냈다. 일반 for-loop에서 사용했을 때는 최소 179번은 돌아야 했는데...

새로운 방식을 적용해서 작성한 답안은 아래와 같으며

function solution(numer1, denom1, numer2, denom2) {
    let numer = numer1 * denom2 + numer2 * denom1;
    let denom = denom1 * denom2;
    
    const findGCD = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a
    }
    
    const gcd = findGCD(numer, denom);
    
    return [numer / gcd, denom / gcd];
}

사진처럼 시간을 한참 줄여볼 수 있었다.

TMI1) 아니 레밸 0 문제라면서 왜 실행시간으로 나를 힘들게 해!!

TMI2) 다른 문제를 풀다가 문자열 숫자 체크하는 방법도 다양하다는 것을 아래 링크를 통해 알았다.
https://coreui.io/blog/how-to-check-if-string-is-number-in-javascript/
하지만 주로 사용하는 것은 Number(s)에 s를 확인하고 싶은 문자열로 둔 뒤 저기서 NaN 값이 나온다면 문자열이 숫자로만 이루어져있지 않다는 것을 알 수 있다.

달리기반

어려웠던 thisbinding과 스코프, 그리고 클라스 객체에 대한 이론 강의

This

어떠한 특정 객체를 가르키는 것. JS의 기본/암묵적 바인딩 방식이 있는데 아래와 같다.

• 기본 바인딩: 함수 호출에서는 전역객체를 의미한다
• 암묵적 바인딩: 호출을 한 객체를 의미한다.

function showThis() {
  console.log(this);
}

// 기본으로 전역 바인딩
showThis(); // 브라우저 환경에서는 window 객체 출력
// strict 모드에서는 undefined

// 암묵적 바인딩
const obj1 = {
  name: 'obj1',
  sayName() {
    console.log(this.name);
  },
};

const obj2 = {
  name: 'obj2',
  sayName: obj1.sayName,
}

obj2.sayName();	// obj2가 출력된다!

• 명시적 바인딩: 말 그대로 명시적으로 this를 특정 무언가로 지정하고 싶다에 특정 객체를 넘겨서 this를 새로 바인딩하는 방식

명시적으로 바인딩 하는 방법은 call, apply, 그리고 bind가 있다.

// call
const name = "John";

function greet() {
  console.log(`Hello, my name is ${this.name}`);
}

const user1 = {
  name: 'Bob'
};

greet.call(user);	// Hello, my name is Bob ("John"아님)
// apply: call에 매개변수까지 받을 수 있음
function greetV2(greeting, punctuation) {
  console.log(`${greeting}, my name is ${this.name}${punctuation}`);
}

const user2 = {
  name: 'Alice'
};

greetV2.apply(user2, ['Hi', '!']); // 출력: Hi, my name is Alice! 

// bind: 앞선 두 방법은 호출까지 한 번에 하지만
// bind는 this만 지정해주고 호출은 따로 해야함
const user3 = {
  name: 'Charlie'
};

const boundGreet = greet.bind(user3);
boundGreet();	// Hello, my name is Charlie

• New Binding: new를 통해 생성자 함수를 호출할 때, 생성자 함수 내부의 this는 새로 생성되는 객체를 가르킨다.

// 생성자 함수 정의
function Car(maker, model) {
    // new 바인딩에 의해 this는 새로운 객체(이 경우 인스턴스)를 가리킴
    this.maker = maker;
    this.model = model;
}

// new 연산자를 사용해 객체 생성
const myCar = new Car('Toyota', 'Camry');

// 생성된 객체의 프로퍼티 접근
console.log(myCar.maker);	// Toyota
console.log(myCar.model);	// Camry

추가로) 화살표 함수에서의 this
상위스코프의 this를 물려받는다

// 객체 생성
const person = {
    name: 'John',
    // 일반 함수에서의 this
    greetRegular: function() {
        console.log('Regular function this:', this);
    },
    // 화살표 함수에서의 this
    greetArrow: () => {
        console.log('Arrow function this:', this);
    }
};

// 객체 메서드 호출
person.greetRegular();	// {name: 'John', greetRegular: f, greetArrow: f}
person.greetArrow();	// window

greetArrow()는 상위(함수) 스코프를 찾으려고 하기 때문에 person를 뚫고 더 위의 스코프를 찾아 window가 된다.

Class

Class란 객체를 생성하기 위한 탬플릿

// (1) 이 부분이
function Car (brand, model) { 
		this.brand = brand;
		this.model = model;
}

class Car {
  // (2) 여기로 대체됨
  constructor(brand, model) {
    this.brand = brand;
    this.model = model;
  }

  // 인스턴스에 의존해서 실행
  displayInfo() {
    console.log(`${this.brand} ${this.model}`);
  }
}
const myCar = new Car("Toyota", "Camry");

myCar.displayInfo();	// Toyota Camry

위에서 displayInfo()가 클라스 메소드가 됩니다.

인스턴스 없이 클라스 메소드를 사용하는 방법은 정적으로 바꾸면된다

class Car {
  // 인스턴스와 무관하게 실행가능
  static displayInfo() {
    console.log(`${this.brand} ${this.model}`);
  }
}
// 정적으로 실행하기
Car.displayInfo("KIA", "K3");	// KIA K3	

주의사항) 클라스 안에서의 메소드는 화살표 함수로 하지 말 것, 안 그러면 디스가 자연스럽게 window가 될 수 있음

상속

class Animal {
  constructor(name) {
    this.name = name;
  }

  speak() {
    console.log(`${this.name} makes a noise.`);
  }
}

class Dog extends Animal {
  constructor(name, breed) {
    super(name);
    this.breed = breed;
  }

  // overriding
  speak() {
    console.log(`${this.name} barks.`);
  }
}

const dog = new Dog('Rex', 'Labrador');
dog.speak(); // 출력: Rex barks.

Scope

강의 들으면서 노트 했는데 저장이 안됐다... (망할)

스코프는 변수와 함수가 유효한 범위

• 함수 스코프: 함수 내에서 선언된 변수는 함수 내에서만 유효
• 블록 스코프: ES6에서 도입된 let과 const 키워드는 블록 스코프를 지원. 블록 스코프는 중괄호{}로 감싸진 코드 블록 내에서만 변수가 유효 (var는 예외)

두 가지를 모두 아래 예시 코드에서 보자면

// 함수 스코프
function foo() {
  var x = 'local';
  console.log(x); // 출력: local
}

foo();	// foo내의 x는 잘 정의 되어있음
console.log(x); // ReferenceError: x is not defined

// 블록 스코프
{
  var z = "var: not blocked";
  let y = 'block scoped';
  console.log(y); // block scoped
}

console.log(z);	// 출력 - var: not blocked
console.log(y); // ReferenceError: y is not defined

• 스코프 체인: 스코프 체인은 변수를 찾을 때 현재 스코프에서 찾고, 없으면 상위 스코프로 이동하여 변수를 찾는 방식

let a = 'global';

function outer() {
  let b = 'outer';
  if (true) {
	  let d = 10;
  }
  function inner() {
    let c = 'inner';
    console.log(a); // 출력: global
    console.log(b); // 출력: outer
    console.log(c); // 출력: inner
    console.log("d:",d);	// reference error!
  }

  inner();
}

outer();

outer에서 inner 호출:
a: inner에 없음 -> outer에 없음 -> 전역에 존재 = 'global'
b: inner에 없음 -> outer에 존재 = 'outer'
c: inner에 존재 = 'inner'
d: inner에 없음 -> outer에 없음! (블록 안에 있음) -> 전역에 없음 -> reference error

• 렉시컬 스코프: 함수가 선언된 시점에서 상위 스코프를 결정하는 방식. 실행되는 위치가 아닌, 함수가 선언된 위치에 따라 상위 스코프가 결정

// 아래 코드의 출력 결과는?
const y = 5;

function first() {
  const y = 20;
  second();
}

function second() {
  console.log(y);
}

first(); // 5
second(); // 5

첫번째로 second가 first 안에서 호출 되기는 하지만 선언 시점이 전역에서 했기 때문에 마침 전역에 있는 y값인 5가 출력된다.
두번째로 second가 호출 되었을때도 마찬가지

마치며...

렉시컬 스코프는 아직 헷갈려요