2023.04.18 TIL

토깽이연구소 수석연구원·2023년 4월 18일

TIL

목록 보기

12/37

오늘의 나는 무엇을 잘했을까?

알고리즘 문제를 해답을 바로 보지 않고 고민해 가면서 풀었다.

오늘의 나는 무엇을 배웠을까?

알고리즘 문제풀이

최대 연속 부분합 알고리즘

최대 연속 부분합은 어떤 배열에서 연속된 부분합의 최댓값을 구하는 문제이다. 다이나믹 프로그래밍으로 점화식을 만들어서 풀 수 있다.

$d[i]$ : i번째 인덱스를 마지막으로 포함하는 부분합 중 최대값

$d[i] = max(d[i-1], d[i-1]+arr[i])$

즉, 지금까지의 인덱스를 포함한 최대 부분합에서 다음 요소를 포함할 지 말 지 정하면 된다. 따지고 보면 다음에 음수가 나오는 경우는 포함을 안시키는 것이다.

이렇게 d 배열을 완성시킨 뒤, d 배열의 요소 중 가장 큰 요소를 골라 리턴하면 된다.

__sublist_cache = {}

def sublist_max(profits, start, end):
    global __sublist_cache

    # 캐시에 있으면 그냥 리턴
    if (start, end) in __sublist_cache.keys():
        return __sublist_cache[(start, end)]

    if start == end:
        __sublist_cache[(start, end)] = profits[start]
        return __sublist_cache[(start, end)]

    # 없다면 그냥 구한다
    sublist_profit = 0
    for i in range(start, end+1):
        sublist_profit += profits[i]
    ret = max(sublist_profit, sublist_max(profits, start + 1, end), sublist_max(profits, start, end - 1))
    __sublist_cache[(start, end)] = ret

    return ret

자바스크립트의 static 메서드

static 메서드는 클래스가 가진 고유의 메서드이다. 즉, 객체가 가진 것이 아닌 “클래스 객체“가 가진 프로퍼티이다. 자바스크립트에서는 클래스 또한 객체인데, 프로토타입이 Funtion.prototype이다. 클래스는 즉 함수 객체인 것. 객체가 자신의 메서드를 가질 수 있듯이 클래스도 자신의 메서드를 가질 수 있다. 클래스 내부에 static 키워드를 추가하여 함수를 정의하면 해당 함수는 static 메서드, 즉 클래스의 생성자가 만든 객체가 아닌 클래스 고유의 메서드가 된다. 따라서 호출하려면 클래스명을 객체 다루듯이 해야 한다.

아래와 같이 정적 메서드를 객체가 호출하려 하면 에러가 난다.
```
class Person {
    constructor(name){
        this.name = name;
    }

    static sayHi(){
        console.log('Hi!');
    }
}

const person = new Person('kenny');
person.sayHi();

// sayHi() 메서드는 클래스의 메서드이지, 클래스가 만든 객체의 메서드가 아니라서 에러 발생
// Uncaught TypeError: person.sayHi is not a function
//    at <anonymous>:12:8
```
정적 메서드는 아래와 같이 인스턴스 없이 바로 호출해야 한다.
```
class Person {
    constructor(name){
        this.name = name;
    }

    static sayHi(){
        console.log('Hi!');
    }
}

const person = new Person('kenny');
Person.sayHi();

// Hi!
```
많이 사용하는 정적 메서드의 예시로 Math.random(), Object.assign()등이 있다.