동전 문제

https://www.acmicpc.net/problem/9084

첫 번째 시도

동적 프로그래밍으로 풀고 싶었다.
동전의 개수 N = 2, 동전의 종류 C = [1,2], 만들어야 할 금액 M = 1000가 입력된다고 하고.

D[1]은 가능한 모든 동전을 사용해 1원을 만들 수 있는 경우의 수
D[2]은 가능한 모든 동전을 사용해 2원을 만들 수 있는 경우의 수
….
D[M]은 가능한 모든 동전을 사용해 M원을 만들 수 있는 경우의 수

여기서 D[M]을 구하는 일반화된 식을 만들어보려고 M=1인 경우부터 쭉 나열했다.

이런식으로 표를 작성했는데, 경우의 수가 중복해서 계산되는 문제가 있었다.

두 번째 시도

이상한 표만 계속 그리다가 결국 구글링..

http://blog.naver.com/occidere/220793012348 이 글이 가장 도움이 됐다. 코드는 안보고(!) 일반화하는 방법을 참고했다.

동전의 종류가 오름차순으로 주어지는 것에 가장 큰 힌트가 있었다.
동전 1, 2가 있다면

1. 동전 1원으로, 1원부터 M원까지 만드는 경우의 수를 구하고, 결과를 D[M]에 저장.
   

   

   
   

2. 동전 1원과 2원으로, 1원부터 M원을 만드는 경우의 수를 구한다. 앞 단계에서 구했던 D[M]을 재사용한다 !!
   

   

 한 마디로 앞 단계에서 사용 가능한 동전(1원)으로 M원을 만드는 경우의 수에, 현재 단계에서 새로 추가된 동전(2원)으로 M원을 만드는 경우의 수를 더한다.

최종 코드

T = int(input())

for _ in range(T):
    N = int(input())
    C = list(map(int, input().split()))
    M = int(input())

    d = [0 for _ in range(M + 1)]

    d[0] = 1

    for coin in C:
        for m in range(coin, M + 1):
            d[m] = d[m] + d[m - coin]

    print(d.pop())

자바스크립트 생성자 함수

자바스크립트는 ‘생성자 함수’에 인스턴스에 만들어질 속성과 메서드를 정의하고, ‘생성자 함수’를 이용해서 인스턴스를 생성할 수 있다.

function Person(name) [
    this.name = name;
}

Person은 생성자 함수이다. 자바스크립트의 함수는 반복되는 로직을 모아놓은 함수가 될 수도, 인스턴스의 모양(속성이나 메서드)이 정의된 생성자가 될 수도 있다. 다른 언어에서는 클래스와 생성자가 구분되지만, 자바스크립트에서는 생성자 함수가 클래스의 역할을 한다. 그리고 생성자 함수의 이름은 Person처럼 첫 글자를 대문자로 쓰는 것이 관례이다.

인스턴스를 만들 때는 new 연산자와 함께 생성자를 호출한다.

var tarzan = new Person('Tarzan');
tarzan.name; // 'Tarzan'

주의할 것은 new 연산자가 빠지면 안되는 점이다. 그냥 Person() 으로 호출하면 Person은 일반 함수로서 동작한다. 일반 함수의 this는 기본적으로 글로벌 객체를 참조하며 strict-mode에서는 undefined이 된다.

이어서 메서드의 정의는 생성자 안에서 할 수도 있다. 하지만 비효율적이다.

function Person(name) {
    this.name = name;
    this.describe = function() {
        return 'my name is ' + this.name;
    }
}

new 연산자는 생성자의 this가 새로운 인스턴스를 가르키게 한다. 그리고 this로 참조하는 인스턴스에 속성과 메서드를 추가할 것이다. 위의 예제에서도 Person으로 생성하는 모든 인스턴스에서 name 속성과 describe 메서드를 추가한다. 그런데 name 속성은 인스턴스마다 모두 달라서 인스턴스에 추가되는 것이 맞지만, describe 메서드는 모든 인스턴스에 추가될 필요가 없다. 한 공간에 메서드를 한번만 정의하고, 모든 인스턴스에서 그 공간을 참조할 수 있게 하는 방법이 더 효율적이다.

function Person(name) {
    this.name = name;
}

Person.prototype.describe = function() {
     return 'my name is ' + this.name;
}

var tarzan = new Person('tarzan');
var jane = new Person('jane');

tarzan.describe(); // 'my name is tarzan'
jane.describeS(); // 'my name is jane' 

Person.prototype  객체에 메서드를 추가하면 모든 인스턴스에서 메서드를 공유할 수 있다. 

프로토타입

자바스크립트의 원시 값을 제외한 모든 객체는 코드 상에서 접근할 수 없는 내부 속성인 [[Prototype]] 속성을 가진다. [[Prototype]] 속성은 자신의 프로토타입 객체를 가르킨다. 프로토타입 객체란 자신의 부모 객체를 말한다. 그리고 [[Prototype]] 속성으로 연결된 두 객체의 관계를 프로토타입 관계(혹은 상속 관계)라고 부르며, 하나 이상의 프로토타입 관계는 프로토타입 체인을 형성한다. 그리고 자식 객체에서 동일한 프로토타입 체인에 있는 부모 객체의 속성이나 메서드에 접근할 수 있다.

Person의 인스턴스인 tarzan과 jane에도 역시 [[Prototype]]속성이 있다. 그리고 생성자가 new 연산자와 함께 실행될 때, 새로운 인스턴스인 tarzan과 jane의 [[Prototype]]속성은  Person.prototype 객체를 참조하게 된다. 즉, 인스턴스와 Person.prototype 객체는 프로토타입 관계에 있다. 인스턴스에는 describe 메서드가 직접 선언되어 있지 않지만, 프로토타입 체인을 통해 Person.prototype의 describe 메서드에 접근할 수 있다.

Person.prototype은 이름만 봤을 때 Person의 프로토타입 객체로 착각하기 쉽다. Person의 프로토타입 객체는 생성자 함수이기 이전에 일반 함수이기 때문에 자바스크립트 내장 객체인 Function이며, Person.prototype은 Person 인스턴스들의 프로토타입 객체(인스턴스 프로토타입)이다.

참고

• 악셀 라우슈마이어의 자바스크립트를 말하다
• MDN - 객체 지향 자바스크립트 소개
• 생활코딩 - 생성자와 new

자바스크립트 배열 연결하기.

 JavaScript의 Array 객체는 두 개의 배열을 연결할 수 있는 concat 메서드를 제공한다.

var arr1 = [1, 2, 3];
var arr2 = ['a', 'b', 'c'];

var new_arr = arr.concat(arr2);
// arr1 뒤에 arr2를 이은 새로운 배열을 반환한다.

// arr1 : [1, 2, 3];
// arr2 : ['a', 'b', 'c'];
// new_arr : [1, 2, 3, 'a', 'b', 'c'];

 정확히 말하면 두 배열의 모든 요소를 복사한 새로운 배열을 만들고, 기존 배열의 내용은 바뀌지 않는다. 그리고 concat은 세 개 이상의 배열을 연결한 새로운 배열을 만들 수도 있다.

 하지만 굳이 원래 배열들의 형태를 유지할 필요가 없고, 새로운 배열이 선언되는 낭비를 줄이고 싶다면 push와 apply를 이용해서 배열을 연결할 수 있다.

arr1.push.apply(arr1, arr2);

// arr1 : [1, 2, 3, 'a', 'b', 'c'];
// arr2 : ['a', 'b', 'c'];

 push 메서드는 두 개 이상의 인자를 넘겨 배열의 맨 뒤에 붙일 수 있다.

arr1.push(4, 5);

// arr1 : [1, 2, 3, 4, 5];

 apply 메서드는 수신자 함수에서 참조하게 될 this값을 첫 번째 인자로 넘기고, 수신자 함수로 넘어갈 인자들을 배열 형태로 넘길 수 있다.

arr1.push.apply(arr1, arr2)

// 아래와 동일한 방법이다.
arr1.push('a', 'b', 'c');