항해 99 5기 TIL_30

▶ Today I Learned

 

<알고리즘 스터디>

 

[그리디 알고리즘]

 

탐욕법이라고도 칭함,

매 순간 가장 좋아보이는 선택을 하며 나중에 끼칠 영향에 대해서는 고려하지 않음.

그래서 단순 무식하게, 탐욕적으로 푸는 방법이라고 하나보다.

모든 문제에 통하는 방식은 아니며 동적 프로그래밍을 보완해주기위한 느낌으로 쓰이는 듯 하다.

 

해당 알고리즘으로 매 순간 가장 좋아보이는 선택을 하기에 보통 가장 큰 단위부터 풀어나가는 경우가 많아보이나,

사용자가 정답을 찾을 때 세운 조건에 가장 가까운 값을 선택하는 것이 해당 알고리즘에 더 맞는 설명이라고 본다.

그것이 항상 큰 단위일 수 없는게 만약 사용자가 정답을 구하기 위해 '배열 내 값 중 최솟값을 구해야 해!' 라고 생각했다면

가장 작은 단위가 기준이 되어 작은 수부터 찾아나가는 알고리즘을 짤 수도 있기 때문이다.

 

그리디 알고리즘에 대해서는 아래 링크를 참조해보자.

https://jeleedev.tistory.com/69

 

 

cf) 동적 프로그래밍: 문제를 작은 것부터 풀어나가는 방식,

필요조건

1) 작은 문제의 반복

2) 같은 문제는 구할 때 마다 정답이 같다.

 

이로인해 한번 계산한 문제는 저장해놓고 사용 -> 이를 Memorization 이라고 함

아래 링크 참조

https://galid1.tistory.com/507

 

<TDD>

 

[클래스 상속]

 

출처: 자바스크립트 공식문서

https://ko.javascript.info/class-inheritance

 

[생성자 오버라이딩]

 

공식문서에 따르면 자식 클래스에 생성자가 없을 때는 문제가 없다고 한다.

그러나 자식 클래스에도 생성자를 만들고 실행할 경우 에러가 발생한다. (상세 내용은 공식문서 '생성자 오버라이딩 부분 참조)

이에 대해서는 다음과 같은 말이 적혀있었다.

'그런데 왜 super(...)를 호출해야 하는 걸까요?

당연히 이유가 있습니다. 상속 클래스의 생성자가 호출될 때 어떤 일이 일어나는지 알아보며 이유를 찾아봅시다.

자바스크립트는 '상속 클래스의 생성자 함수(derived constructor)'와 그렇지 않은 생성자 함수를 구분합니다. 상속 클래스의 생성자 함수엔 특수 내부 프로퍼티인 [[ConstructorKind]]:"derived"가 이름표처럼 붙습니다.

일반 클래스의 생성자 함수와 상속 클래스의 생성자 함수 간 차이는 new와 함께 드러납니다.

• 일반 클래스가 new와 함께 실행되면, 빈 객체가 만들어지고 this에 이 객체를 할당합니다.
• 반면, 상속 클래스의 생성자 함수가 실행되면, 일반 클래스에서 일어난 일이 일어나지 않습니다. 상속 클래스의 생성자 함수는 빈 객체를 만들고 this에 이 객체를 할당하는 일을 부모 클래스의 생성자가 처리해주길 기대합니다.

이런 차이 때문에 상속 클래스의 생성자에선 super를 호출해 부모 생성자를 실행해 주어야 합니다. 그렇지 않으면 this가 될 객체가 만들어지지 않아 에러가 발생합니다.

아래 예시와 같이 this를 사용하기 전에 super()를 호출하면 자식클래스(상속클래스)의 생성자가 제대로 동작합니다.'

class Board extends Site{
    
    constructor(name) {
        if(name === '' || name === null) {
            throw Error
        } else{
            this.name = name; // Board {name: '공지사항'}
        // this.siteId = -1
        this.isDupName = true; // 사용가능 게시판 기준
        this.articles = []; // 왜 만들까? 이렇게되면 Site { boards: [ Board { name: '공지사항', articles: [] } ] } 이런느낌이려나?

        }
        
    }
    // function을 쓰면 에러가 뜬다. 왜지?
    publish(article) {
        if (!super.boards.length === 0) {
            this.articles.push(article);
        } else {
            throw Error
        }
        
    } 

}

extends로 관계 설정 후 자식클래스에서 super클래스의 생성자를 먼저 불러주지 않으면 다음과 같은 에러가 뜬다?

 ReferenceError: Must call super constructor in derived class before accessing 'this' or returning from derived constructor

 

실제 이미지는 하단 참조

 

 

'오버라이드'란 무엇인가?

공식문서의 예제를 통해 살펴보겠다.

class Animal {
  name = 'animal'

  constructor() {
    alert(this.name); // (*)
  }
}

class Rabbit extends Animal {
  name = 'rabbit';
}

new Animal(); // animal
new Rabbit(); // animal

이처럼 되어있을 경우 자식 클래스에 생성자는 없기 때문에 자식클래스인 래빗으로 객체를 만든다면

해당 객체인 new Rabiit() 을 호출할 때 rabbit이 아닌 animal이 alert된다.

 

여기서 부모 클래스의 클래스 필드인 name이라는 변수에 자식클래스에서 선언한 rabbit을 입히는 걸 '오버라이딩'이라고 한다.

override는 중단하다, 무시하다, 을 보다 우선순위로 하다라는 뜻이며, 여기선 부모에서 대입하는 값을 무시해버리고

자식 클래스에서 새로 값을 대입하다, 자식클래스의 값을 우선순위로 하다는 뜻으로 보인다.

애초에 단어가 over(무언가의 위에서) ride (타다, 달리다) 니까 그렇게 이해된다.

위 경우엔 부모생성자가 자식클래스에서 오버라이딩한 값이 아닌 부모클래스 안의 필드 값 animal을 쓰고 있는 것이다.

 

 

[테스트 코드 문제 해결 - 클래스 간 상속 없이 연결하기]

 

여러 문제를 풀었지만 그 중 가장 어렵게 다가온 문제는 이것이었다.

아래의 테스트 코드에 대해 그 아래의 index 파일 코드로 문제를 해결하는 것이다.

즉, 사이트 내 추가된 보드에 대해서만 Article을 추가하도록 하고 아닌 경우 Article을 추가해주지 않도록 하는 것.

test('Site 에 추가된 Board만 사용 가능한 것으로 간주하며 사용 불가능한 Board에는 Article을 추가할 수 없다.', () => {
        const addedBoard = new Board('사이트에 추가된 게시판');
        const notAddedBoard = new Board('사이트에 추가되지 않은 게시판');

        mySite.addBoard(addedBoard);

        expect(() => {
            const article = new Article({
                subject: '글 제목',
                content: '내용',
                author: '작성자',
            });
            addedBoard.publish(article);
        }).not.toThrow();

        expect(() => {
            const article = new Article({
                subject: '글 제목2',
                content: '내용',
                author: '작성자',
            });
            notAddedBoard.publish(article);
        }).toThrow();
    });

 

class Site {
    constructor() {
        this.boards = [];
        // this.id = Math.random().floor()
    }

    addBoard(board) {

        if (this.boards.length === 0) {
            this.boards.push(board); // Site { boards: [ Board { name: '공지사항' } ] }
            this.boards[0].names.push(board.name);
        } else {
            for (let i = 0; i < this.boards.length; i++) {
                if (this.boards[i].name === board.name) {
                    // this.boards.filter(x => x.name === board.name) 도 있음
                    // this.boards.map(x => x.name).includes(board.name) 도 있음
                    throw this.addBoard(board);
                } else {
                    return (
                        this.boards.push(board), //  여기서 만약 return이 없으면 무한루프가 발생한다.
                        this.boards[i].names.push(board.name)
                    );
                }
            }
        }
    }

    findBoardByName(name) {
        if (this.boards.filter((x) => x.name === name)) {
            // this.boards라는 배열 내부의 객체 값 중 name키의 값이 에서 외부에서 받아온 name 값과 같은 경우의 객체만 새로운 배열로 반환해준다.

            return this.boards.filter((x) => x.name === name)[0];
            // 위의 결과물이 Expected: {"articles": [], "name": "공지사항", "names": ["공지사항"]}
            //Received: [{"articles": [], "name": "공지사항", "names": ["공지사항"]}]이므로 여기서 [0]를 사용해 []를 한번 벗겨준다.
        }
    }
}

class Board {
    constructor(name) {
        // super(); // 부모 생성자, 이것을 만들어주어야 자식 생성자 this도 만들 수 있다.
        if (name === '' || name === null) {
            throw Error;
        } else {
            this.name = name; // Board {name: '공지사항'}
            this.names = [];
            this.articles = []; // 왜 만들까? 이렇게되면 Site { boards: [ Board { name: '공지사항', articles: [] } ] } 이런느낌이려나?
            // this.siteId = -1
        }
    }
    publish(article) {
        if (this.names.includes(this.name)) {
            this.articles.push(article);
            article.id = this.name + '-' + Math.random() * (10000000000).toString(10).substr(0, 10); // 랜덤 id 생성
            article.createdDate = new Date().toISOString(); // ISO 8601 양식
        } else {
            throw Error;
        }
    }
    getAllArticles() {
        return this.articles;
    }
}

 

문제 해결을 위해 수 많은 방법을 시도했지만 끝에 고른 것은 클래스 Site에 추가된 Board의 이름을 배열로 따로 빼낸 후

그 배열 내 특정 이름이 있는지 없는지 비교하는 방법이었다. 이론은 이해했지만 상속이라는 개념을 쓰지않고 어떻게

Board에서도 쓸 수 있는 배열을 만들어낼지 고심했다.

그 끝에 위와 같은 코드들을 완성할 수 있었다. Board()에 미리 이름을 담을 배열을 객체로 선언하여 둔다.

여기선 this.names = [] 이다. 이렇게 되면 테스트 코드 부분에서 Board 인스턴스 생성 시 articles이라는 객체명이 Site쪽에도 추가된다. 이후 addBoard() 함수에서 push로 값을 넣어줄 때 해당 값의 이름 값만을 가져와 따로 names에 넣어준다.

이후 Board내 보드 추가 함수인 publish() 에서 해당 값이 있는 지 없는 지를 비교하여 없는 경우 Throw 해주는 것이다.

이렇게 문제를 해결했다 :)

 

▶ 느낀 점

 

클래스 상속에 대해 열심히 공부하였지만 정작  테스트 코드를 짤 때 상속을 사용하지 않아도 되었다.

시간을 꽤 소모했지만 그덕에 한동안 잊고 지냈던 상속, 오버라이딩 등에 대해서 다시 한 번 정리해볼 수 있었다.

그 외에도 테스트 코드 문제를 풀며 많은 개념을 익히고 많은 시간을 쏟아 해결해 나갔다.

알고리즘도 시간을 좀 쏟기도 했고.. 그래서 바쁘지만 알찬 하루였다! 히히

내일도 화이팅팅! ;)

 

 

▶ 공부 시 참고 링크들

 

https://jeleedev.tistory.com/69

[이것이 코딩테스트다] 그리디(탐욕법)

https://velog.io/@mygomi/TIL-69

TIL 72 | JS 두 배열을 비교하기

 

https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182#:~:text=%ED%81%B0%20%EB%AC%B8%EC%A0%9C%EB%A5%BC%20%ED%95%9C%20%EB%B2%88,%EA%B8%B0%EB%B2%95%EC%9D%B4%20%EB%8F%99%EC%A0%81%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%9E%85%EB%8B%88%EB%8B%A4.

(Algorithm) 동적 프로그래밍(Dynamic programming) - 배낭 문제, LCS 문제, 막대기 문제

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random

Math.random() - JavaScript | MDN

https://gist.github.com/bynaki/fcd46c09e0315d4dd839

JavaScript :: 유일한 ID 만들기.