[문제 링크]


DP문제이다. 정말 내 머리가 DP에서 틀에 박혔다는 생각이 든 문제였다. 원래는 DP[V] = DP[V] + DP[V-COIN[I]]와 같은 점화식으로 문제를 풀어나갔는데.


이 식의 문제점은 다른 순서지만, 같은 종류의 동전을 사용한 것도 모두 다른 값으로 취급해 카운트를 하는 것 같았다. 그래서 그냥 단순하게 위와 같은 방식으로 문제를 풀 경우 출력값이 엄청 크게 나왔다..


그래서 내가 원래 풀었던 것과 반복을 다른 방법으로 진행해야 하는데, 그것은 각 값 별로 방법의 수를 구하는 것이 아니라, 동전 별로 각 값에 대한 방법의 수를 구하는 것이다.



밑의 코드는 원래 방식대로, 값을 기준으로 재귀를 진행한 코드이다. 1,1,1,2와 2,1,1,1과 같은 같은 종류지만 다른 순서로 인것들도 모두 다른 경우로 취급해 엄청 큰 값이 나온다. 

각 동전의 경우에 따른 경우의 갯수를 cache의 2차원 배열로 추가하면 문제 해결이 가능하고, 실제로도 이렇게 답을 구했었지만 이 경우 문제의 메모리 제한 4mb를 초과해버린다.

#include <cstdio> #include <cstring> int n,coin[101],k,cache[10001]; //사용한 동전 갯수가 같으면 같은 경우이다. int dp(int value){ //기저사례 num == k일때 if(value==0) return 1; //기저사례 2, n을 넘어설때, 0 if(value<0) return 0; int& ret = cache[value]; if(ret!=-1) return ret; ret = 0; //점화식 for(int i=0;i<n;i++){ if(value-coin[i] >= 0) ret = ret + dp(value-coin[i]); } return ret; } int main(){ memset(cache,-1,sizeof(cache)); scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&coin[i]); } printf("%d",dp(k)); }


밑은 각 동전별로 경우의 수를 구한 코드이다.


#include <cstdio>
int n,coin[101],k,cache[10001]={0,};
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 1;
    
    //각 동전별로 값마다 경우의 수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i])
                cache[j] += cache[j-coin[i]];
        }
    }   
    printf("%d",cache[k]);
}

코드가 훨씬 간결하고 직관적이다. DP에 대한 학습은 아직 더 필요한거같다.

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26


기본적으로 프로그래밍 언어에서 스코프란, 어떤 변수에 대한 유효 범위를 뜻한다.

대표적으로 C언어에 함수 안에서 선언한 변수는, 함수 밖에서는 참조할 수 없는 것을 예로 들 수 있다.

보통 C,C++,JAVA에선 이 스코프에 대한 정보 흐름을 스택으로 표현한다. 프로그램이 시작하면 main함수에서 참조하는 정보들이 스택 영역에 push하고, 새로운 함수나 흐름이 시작하면 스택 영역의 가장 위에 push하여 정보를 저장한다. 그리고 변수를 사용할 때 스택의 top에 있는 정보를 사용한다. 

자바스크립트도 이러한 스코프를 구현하기 위해, 다른 언어의 스택 영역과 유사한 개념으로 실행 컨텍스트(Excution context)를 정의하였다.


실행 컨텍스트란, '실행 가능한 코드를 형상화하고 구분하는 추상적인 개념'으로 정의 된다고 한다, 쉽게 말하면 코드 블럭에 대한 정보들을 표현한 것이라고 할 수 있다.


이러한 실행 컨텍스트는 다른 언어의 main영역과 마찬가지로 global 컨텍스트가 존재한다, 이는 실행 컨텍스트가 생성되는 과정을 살펴본 후 알아보도록 하겠다.


function circle(r){
    var number = 3.14;
    function square(){
        return r*r;
    }
    return number * square();
}

circle(4);//50.24


위는 입력받은 반지름에 따른 원의 넓이를 구하는, 그냥 예제를 위한 함수이다. 위 함수를 실행함에 따라 실행컨텍스트가 어떻게 생성이 되는지 하나씩 정리하도록 해자.


1. 함수가 실행되면, 실행 컨텍스트를 생성한다.


 실행 컨텍스트

 



2. 실행 컨텍스트가 생성된 후, 이 컨텍스트에서 실행에 필요한 정보들을 담을 객체인 활성 객체를 생성한다.


 실행 컨텍스트

 

 활성 객체

 


활성 객체에는 이 함수가 가지고 있는 파라미터나 변수, 객체 등에 대한 정보가 저장된다. 

또한 다른 스코프에서 이 실행 컨텍스트를 참조할 땐 저 활성 객체를 통해 참조하게 된다.



3. 활성 객체 내에, 매개변수의 정보를 저장하고 있는 arguments 객체가 생성되고, 함수의 arguments 객체를 참조한다.


 실행 컨텍스트

 

 활성 객체

 arguments ---> [ r ]



활성 객체에는 이 함수가 가지고 있는 파라미터나 변수, 객체 등에 대한 정보가 저장된다. 

또한 다른 스코프에서 이 실행 컨텍스트를 참조할 땐 저 활성 객체를 통해 참조하게 된다.


4. 활성 객체 내에, 이 실행 컨텍스트의 스코프 체인을 생성한다.


 실행 컨텍스트

 

 활성 객체

 arguments ---> [ r ]

 [[scope]] 


스코프 체인은 이 컨텍스트 생성의 대상이 되는 함수가 가지고있는 [[scope]]를 복사해오고, 거기에 이 실행 컨텍스트의 활성 객체를 추가한다.

[[scope]]는 list의 형태로 저장이 되며, 전역객체에서 함수를 선언했으므로, 이 예제에서 저장되어있는 스코프는 이 실행 컨텍스트와, 전역 컨텍스트 일 것이다.



5. 변수 객체가 생성 되고, 함수가 가지고있는 변수 및 객체 정보를 생성한다.


 실행 컨텍스트

 

 활성 객체 = 변수 객체

 arguments ---> [ r ]

 [[scope]] ---> [List]

 r : value

 number : undefined

 square ---> Function Object


변수 객체가 따로 명명 되었지만, 변수 객체가 활성 객체와 같다.

매개변수로 받은 변수들은 바로 그 값으로 초기화 되고, 

함수 내에 선언된 변수는 해당 코드가 실행 되기 전까지는 초기화 되지 않기 때문에,

먼저 undefined로 저장이 된다.



6. this에 대한 정보를 저장하며, 이 객체에 바인딩한다.


 실행 컨텍스트

 

 활성 객체 = 변수 객체

 arguments ---> [ r ]

 [[scope]] ---> [List]

 r : value

 number : undefined

 square() ---> square함수 객체를 참조

 this ---> 전역 객체에 바운딩


this 바운딩에 대해선 this 키워드 포스트를 참조하자. 여기선 전역에 선언되어있는 함수이기 때문에 전역 객체에 바인딩 될 것이다.



7. 코드가 실행된다.

코드가 실행되면서 number의 값이 초기화되고 함수가 실행되어 반환된다.



지금까지 circle 함수의 실행 컨텍스트의 생성 과정을 보았다. 그러면 global 컨텍스트는 어떻게 될까? 

global 객체도 자바스크립트 객체이기 때문에 이와 크게 다르지 않다. global에 선언되어있는 변수와 객체에 대한 정보를 변 수객체에 저장하게 될 것이다.


global 실행 컨텍스트

 

 활성 객체 = 변수 객체

 arguments ---> []

 [[scope]] ---> [List]

 circle() ---> circle 함수 객체를 참조

 this ---> 전역 객체에 바운딩



예제에서의 global 컨텍스트는 위와 같을 것이다. 이 컨텍스트의 [[scope]]는 그 이전의 전역 컨텍스트의 변수 객체만이 존재할 것이며, this도 전역 객체에 바운딩 될 것이다.

'Javascript' 카테고리의 다른 글

자바스크립트 - Prototype 기반의 객체지향  (0) 2016.02.25
자바스크립트 - 객체 생성  (0) 2016.02.21
자바스크립트 - this 키워드  (0) 2016.02.04

요새 자바스크립트 하나만 잘 알아도, 웹사이트 전체를 만들 수 있는 풀스택 개발이 가능하다고 한다. 이러한 풀 스택 개발이 가능하게 된 기반은 node.js라는 자바스크립트 프레임워크의 존재 떄문이다. 


자바스크립트는 초기에 그저 브라우저 내 에서의 동적인 처리를 위한 스크립트 언어였고, 현재도 대부분이 jquery나 angular.js와 같은 프론드엔드 프레임워크를 많이 사용한다. 하지만 수많은 자바스크립트 프레임워크중에 특출나게 서버 사이드를 처리하는 프레임워크가 있으니, 그것이 바로 node.js다. 기존의 자바스크립트 프론트엔드 프레임워크와, node.js가 합쳐져, 그야말로 자바스크립트만 잘 알아도 사이트 하나는 뚝딱 만드는 것이다. 

그 뿐만 아니라 node.js는 기존의 서버와는 다르게 event-driven 기반, 싱글 쓰레드에 non-Blocking I/O 방식으로 작동한다고 한다.(데이터 입출력때마다 blocking되지 않는다.)

그리고 jsp나 php와 같이 웹서버나 WAS가 필요 없고, node.js 그 자체가 웹서버로서 동작한다.


node.js에 대한 관심은 항상 가지고 있었다. node.js는 매 업데이트마다 죄다 뒤집어져서 책이 의미가 없다고 하니, 구글링과 레퍼런스를 통해 독학으로 시작하려 한다.



node.js는 공식 사이트에서 받을 수 있는데, 검색해서 찾아가보니 메인화면만 유일하게 한글화가 되어있다..(..)


공식 사이트의 주소는 다음과 같다 - https://nodejs.org/en/




사이트에 들어가면 위와 같이 LTS 버젼과, Stable버젼이 있다. Stable 버젼이란 안정화된 최신 버전을 뜻하고

LTS란 보통 Long Term Support, 장기간 지원을 하는 버전을 뜻한다. 4.3.1 LTS버젼을 다운 받아보자.




다운 받으면 설치 파일을 실행, node.js에 흥미를 가지실 정도의 분이라면 설치에 대한 두려움을 가진 사람은 없으리라 생각한다.






설치 완료!


C:\nodejs폴더에 example.js 파일을 생성하고, 다음 예제코드를 입력해보자.

const http = require('http');

http.createServer( (request, response) => {
  response.writeHead(200, {'Content-Type': 'text/plain'});
  response.end('Hello World\n');
}).listen(8124);

console.log('Server running at http://127.0.0.1:8124/');


명령 프롬포트를 실행하고, 다음과 같이 입력해보자.




브라우저를 이용해 http://localhost:8124/ 접속해보면 서버가 정상적으로 작동하여 HelloWord가 출력 되었음을 확인 할 수 있다. 




서버를 종료하고 싶을 경우 명령 프롬포트를 종료하거나, 명령 프롬포트에서 Ctrl+C를 누르면 된다.

'Javascript > node.js' 카테고리의 다른 글

비동기 흐름 제어를 위한 모듈 - async  (0) 2016.09.18
node.js 모듈  (0) 2016.03.30


문제 링크



BFS 문제다. 값의 범위만 조심하면 어려울 것 없는 문제였다.

다만 지금까지 풀었던 BFS는 방문을 체크하는 변수와 현재 탐색 레벨의 변수를 따로 두고 풀었는데, 이번에는 이전 문제와는 다르게,방문을 체크하는 변수 안에 현재 탐색 레벨을 담았다. 다만 그 체크를 위해 맨 처음 값이 1로 시작해야 했기에, 마지막 결과 값에서 1을 빼서 반환했다.

밑은 내가 풀이한 코드이다. 



#include <cstdio> #include <queue> using namespace std; //기존에 풀었던 BFS문제와는 다르게, visited 배열에 현재 레벨도 저장하였다. int n, k, visited[100001]={0,}; queue<int> q; int bfs(){ //큐에 수빈의 위치를 넣고, 방문을 체크하는 배열에 1을 넣어준다. q.push(n); visited[n] = 1; //bfs 시작 while(!q.empty()){ //큐를 꺼내고, 수빈이가 동생의 위치에 도달했는지 확인한다. int p = q.front(); q.pop(); if(p==k) return visited[p]-1; //수빈이 현재 위치 -1이 0보다 크거나 같고, 방문한 적이 없을경우. 현재 값에서 레벨을 1증가시켜 큐에 넣어준다. if(p-1>=0&&visited[p-1]==0){ visited[p-1] = visited[p]+1; q.push(p-1); } //수빈이 현재 위치의 +1이 100,000보다 작거나 같고, 방문한 적이 없을경우. if(p+1<=100000&&visited[p+1]==0){ visited[p+1] = visited[p]+1; q.push(p+1); } //수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한 적이 없을경우. if(2*p<=100000&&visited[2*p]==0){ visited[2*p] = visited[p]+1; q.push(2*p); } } } int main(){ scanf("%d %d",&n,&k); printf("%d",bfs()); }



'Algorithm > Problems' 카테고리의 다른 글

백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25


문제 링크


나는 BFS로 푼 문제이다. 시작 점이 꼭 1번 건물이 아닐 수도 있으므로 모든 건물의 정보를 입력 받는 과정에, 그 이전 단계가 있는 건물들은 시작 건물이 아니라 단정하고 시작 건물들이 가능한 건물들은 처음에 큐에 미리 넣어주고 BFS를 진행하였다.

이 문제에 함정이 있는 게, 문제는 최소 시간을 구하라고 하는데 따지고 보면 그냥 그 단계까지 누적 최고 건설 시간들만 구해주면 된다. 왜냐하면 특정 단계 건물을 짓기 위해서는 선행 건물들을 모두 지어야 하는데, 선행 건물들 중에 건설 시간이 짧은 것을 아무리 먼저 지어도 건설 시간이 긴 건물이 지어지기 전까지는 그 특정 단계의 건물을 지을 수 없기 때문이다. 

이 로직 대로 코드를 짰는데, 처음에 문제를 풀 때 시간 초과가 났었다. 뭐가 문제인가 고민을 해봤더니, 초기에는 build배열에서 첫 번째 인덱스는 현재 건물, 두 번째 인덱스는 다른 건물을 인덱스로 두고, 그 배열 값이 참이면 경로가 존재한다고 하고 풀이를 진행했었다.

이 과정에서 매 루프마다 그때의 건물 배열을 1부터, n까지 전부 다 경로 검사를 진행해야 하니 시간 초과가 일어난 것이다. 그래서 일일이 해당 인덱스에 저장하는 방법을 버리고 해당 건물이 가진 경로의 개수를 path 배열 에다가 저장하고, 배열의 1 인덱스부터 다음 경로들을 저장하는 방법을 택하니 시간 초과에서 벗어났다. 


밑은 위의 과정대로 작성한 코드이다.


#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; //각 건물의 인덱스 0번에 건설 시간을 저장한다. int t,build[1001][1001],isFirst[1001]={0,},value[1001],path[1001]; int x,y,n,k,w; queue<int> q; int bfs(){ int ret = 0; //시작점이 가능한 것들을 전부 큐에 넣는다. for(int i=1;i<=n;i++){ if(isFirst[i]==0){ q.push(i); //초기 빌드의 누적 비용을 건설 비용으로 초기화한다. value[i] = build[i][0]; } } //BFS를 진행한다. while(!q.empty()){ //큐에서 인덱스를 하나씩 꺼내서, 다음 경로에서 가능한 것을 찾는다. int p = q.front(); q.pop(); //원하는 건물에 도달하면, 최대 값을 넣어준다. if(p==w) ret = max(ret,value[p]); else{ for(int i=1;i<=path[p];i++){ if(build[p][i]>=1){ int a = build[p][i]; // 다음 빌드를 짓는 데에 드는 최대 비용을 구한다. 최대 비용이 안되면 enqueue 하지 않는다. if(value[a] < value[p]+build[a][0]){ value[a] =value[p] + build[a][0]; q.push(a); } } } } } return ret; } int main(){ scanf("%d",&t); while(t--){ //초기화// for(int i=0; i<q.size();i++) q.pop(); memset(build,0,sizeof(build)); memset(value,0,sizeof(value)); memset(isFirst,0,sizeof(isFirst)); memset(length,0,sizeof(length)); //건물의 갯수와 건설 규칙 순서 scanf("%d %d",&n,&k); //각 건물 0번 인덱스에 건물의 건설 시간을 저장한다. for(int i=1;i<=n;i++) scanf("%d",&build[i][0]); //각 건물의 경로 초기화 for(int i=0;i<k;i++){ scanf("%d %d",&x,&y); int a = ++path[x]; //해당 경로가 있음을 표시하기위해 1을 저장한다. build[x][a] = y; //또한 해당 경로가 시작점이 가능한지 아닌지도 체크를 해야된다. isFirst[y] = 1; } //목표 건물 scanf("%d",&w); printf("%d\n",bfs()); } }


변수가 쓸대 없이 많아진 것 같아 나중에 시간을 내서 리팩토링을 해야겠단 생각이 든다.


정답률이 15%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.

'Algorithm > Problems' 카테고리의 다른 글

백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
더블릿 - 댐  (0) 2016.02.26
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25
알고스팟 - MORSE, DICT  (0) 2016.02.25


문제 링크

BFS의 정말 정석적인 문제인 것 같다. 미로 찾기 문제와 탐색 방법은 거의 같은데 다른 점은 원하는 만큼 확장한 다음에, 그 갯수를 구한다는 것이다. 
너비우선탐색을 진행해가며 해당 좌표가 맵을 벗어나는지 아닌지, 길인지 아닌지, 그리고 범람했는지 아닌지를 검사한다. 
위 조건을 충족하면 해당 위치의 카운트를 증가시키고 큐에 넣어서 탐색을 계속 이어가고, 카운트가 만약 댐 건설 시간과 일치하면 해당 위치에 댐을 지어야 하므로 댐의 갯수인 ret 변수를 증가시킨다. 
만약 배열 탐색을 끝까지 했음에도 ret변수가 0이면, 댐으로 막지 못했다는 뜻이므로 "OH, MY GOD" 문자열을 출력하고, 0이 아닐 경우엔 막는 데 성공했다는 것이므로 ret의 값을 출력한다. 먼저 STL의 큐를 이용해서 구현했었는데, 라이브러리에 의존적이지 않도록 배열을 이용한 큐를 또 따로 작성해서 구현도 해보았다. 

밑은 이를 구현한 코드이다.


STL을 이용한 BFS

#include <cstdio>
#include <queue>
using namespace std;
//맵의 크기 t, 맵 변수 a, 댐 시간 변수 k, 홍수 넘침 여부 변수 flood 
int t,a[101][101],k,flood[101][101]={0,},x,y;
//해당 좌표 정보를 저장하는 구조체 
typedef struct{
    int x,y,count;  
}Point;
//bfs를 위한 큐 
queue<Point> q;
//해당 위치의 상대 좌표. 물의 확산 비교를 위해 
int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}};
int bfs(){
    int ret=0;
    // 초기 좌표의 정보 값을 저장한 구조체를 만들고, 큐에 넣는다. 
    Point p = {x,y,0}; flood[y][x] = 1;
    q.push(p);  
    // bfs 시작 
    while(!q.empty()){
        p = q.front(); q.pop();
        for(int i=0; i<4;i++){
            int px = p.x + relPos[i][0];
            int py = p.y + relPos[i][1];
            //보드판의 범위 안에 있고, 방문한 적이 없고, 건물이 아니어야 한다. 
            if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){
                //해당 거리에 홍수가 났음을 체크 
                flood[py][px] = 1;
                Point np = {px,py,p.count+1};
                //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. 
                if(p.count+1==k) ret++;
                q.push(np);
            }
        }
    }   
    return ret;
}
int main(){
    scanf("%d",&t);
    // 맵 초기화 
    for(int i =1; i<=t;i++){
        for(int j=1;j<=t;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d",&x,&y);
    scanf("%d",&k);
    int ret = bfs();
    printf(ret==0?"OH, MY GOD":"%d",ret);
}



배열을 이용해 큐를 구현해 푼 BFS

#include <cstdio> //맵의 크기 t, 맵변수 a, 댐 시간 변수 k, 홍수 넘침여부 변수 flood int t,a[101][101],k,flood[101][101]={0,},x,y; //해당 좌표 정보를 저장하는 구조체 typedef struct{ int x,y,count; }Point; //bfs를 위한 큐 Point q[10000]; int front=0,rear=0; void enqueue(Point p){ q[rear++] = p; } Point dequeue(){ return q[front++]; } bool isEmpty(){ return front==rear; } //해당 위치의 상대좌표. 물의 확산 비교를 위해 int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}}; int bfs(){ int ret=0; // 초기 좌표의 정보값을 저장한 구조체를 만들고, 큐에 넣는다. Point p = {x,y,0}; flood[y][x] = 1; enqueue(p); // bfs 시작 while(!isEmpty()){ p = dequeue(); for(int i=0; i<4;i++){ int px = p.x + relPos[i][0]; int py = p.y + relPos[i][1]; //보드판의 범위안에 있고, 방문한적이 없고, 건물이 아니어야한다. if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){ //해당 거리에 홍수가 났음을 체크 flood[py][px] = 1; Point np = {px,py,p.count+1}; //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. if(p.count+1==k) ret++; enqueue(np); } } } return ret; } int main(){ scanf("%d",&t); // 맵 초기화 for(int i =1; i<=t;i++){ for(int j=1;j<=t;j++){ scanf("%d",&a[i][j]); } } scanf("%d %d",&x,&y); scanf("%d",&k); int ret = bfs(); printf(ret==0?"OH, MY GOD":"%d",ret); }




'Algorithm > Problems' 카테고리의 다른 글

백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25
알고스팟 - MORSE, DICT  (0) 2016.02.25
백준 - 1963 소수경로  (0) 2016.02.24

자바스크립트는 기본적으로 Java와 C++과 같은 클래스 객체의 상속이란 개념을 사용하지 않고 prototype 모델의 상속을 지원한다. prototype은 객체를 생성하기 위해 사용되는 객체의 원형을 뜻하며 생성자 객체를 통해 객체가 생성 될 때, 생성자의 prototype 프로퍼티에 링크되어있는 프로토타입 객체들이 생성된 객체에 연결된다. prototype 프로퍼티는 함수 함수들이 가지고있는 속성으로서 생성자를 처음 정의할때엔 기본적으로 empty Object를 가르킨다.

(cf: prototype 프로퍼티는 1급 객체인 함수 객체만 가지고 있는 프로퍼티이므로 일반 객체에서 접근하려고하면 syntax error가 발생한다.)


prototype을 정리하기에 앞서 비교를 위해 생성자 함수를 이용한 객체 생성을 먼저 보면,

var Parent = function(){ this.f = function(){ console.log("HI"); } } Parent.f = function(){ console.log("HELLO"); } var A = new Parent; var B = new Parent; A.f(); B.f();

위 코드의 결과는 다음과 같다.
HI
HI

위에서 this.f는 프로토타입이 아닌 생성자 Parent의 프로퍼티이다. 즉 이 생성자를 통해 새로운 객체를 생성하면 this가 A,B객체에 바인딩이 되어 A,B객체의 프로퍼티가 되기 때문에, 아무리 생성자인 Parent의 f를 수정하더라도 생성된 객체인 A와 B의 f 프로퍼티는 변하지 않는다.(객체 생성 부분은 객체 생성 포스트를 참조하자)


다음은 프로토타입을 이용한 객체 생성이다.

var Parent = function(){ Parent.prototype.f = function(){ console.log("HELLO"); }; } var A = new Parent; var B = new Parent; A.f(); B.f(); Parent.prototype.f = function(){ console.log("HI"); }; A.f(); B.f();

위 코드의 결과값은 다음과 같다.

HELLO
HELLO

HI
HI

즉 생성자의 prototype 프로퍼티를 이용해 프로토타입 객체에 생성된 프로퍼티는, 그 생성자 객체에 의해 생성된 모든 객체가 그 프로퍼티를 공유한다. 생성자가 가지고 있는 프로토타입 객체의 프로퍼티가 변하면 그 생성자에 의해 생성된 모든 객체들의 함수도 같이 변한다. 이는 prototype의 값은 생성자가 가지고있는 f의 값을 객체 자신만의 프로퍼티로 가지고 있는 것이 아니라, 프로토타입 객체에 링크되어 직접 찾아가 사용하기 때문이다.

이를 이해하기 위해선, 생성자 함수 객체가 가지고있는 prototype 프로퍼티 말고도, 객체들이 가지고있는 [[Prototype]]프로퍼티의 존재를 알아야한다. 이는 개발자 도구에서 객체를 열어보면 __proto__프로퍼티로 표시되는 프로퍼티이다. 이 __proto__프로퍼티가 자신이 상속 받은 부모 객체의 prototype을 가르키는 프로퍼티이며, 객체는 자기 자신이 가지고있는 프로퍼티 말고도, __proto__의 링크의 연결되어있는 부모 함수객체의 prototype에 정의해놓은 객체나 변수들을 객체 자신의 것인 양 사용하는 것이다.

(객체들은 모두 가지고있는 [[Prototype]]프로퍼티(__proto__)와 함수(생성자) 객체만 가지고있는 prototype 프로퍼티 두개를 헷갈리지 않도록 조심하자, 가르키는 대상은 같지만 가지고 있는 객체는 다르다. ECMAScript에서 [[Prototype]]프로퍼티라고 명세 했지만 대부분의 브라우져에선 __proto__로 표시하고있다.)

여담으로 함수 객체는 상속을 위한 porototype 프로퍼티가 자신의 prototype 객체를 가리키는데, 반대로 prototype에서는 자기 자신을 포함하는 생성자 함수 객체를 가르키는 constructor를 가지고 있다. 밑에 사진에서 보면 그 관계를 자세히 알 수 있다.

크롬의 개발자 도구에서 확인한 객체의 프로퍼티이다.

__proto__프로퍼티(=[[Prototype]] 프로퍼티)가 자기를 생성한 Member 생성자 객체의 prototype을 가르키고 있다. 그리고 그 prototype이 가지고있는 프로퍼티중 constructor 프로퍼티는, 생성자 함수를 가르키는것을 확인할 수 있다.




위 사진처럼 prototype를 통해 상속되어 연속되어 이어진 형태를 프로토타입 체인(prototype chain)이라고 한다.
객체 에서 어떤 프로퍼티를 사용하려고 할때, __proto__를 따라 상속받은 프로토타입을 찾아가며 프로퍼티를 찾아나간다.
원하는 프로퍼티를 찾고자 하는 과정은 위 그림 순서대로 찾아간다.
객체 자신이 해당 프로퍼티를 가지고있지 않으면 __proto__를 따라 올라가 상위 프로토타입 객체에서 찾고, 없으면 또 __proto__를 따라 올라가 프로퍼티를 찾아나간다.
끝까지 탐색을 해나갔음에도 불구하고(Object.prototype까지 탐색) 원하는 프로퍼티를 찾지 못했을 경우에는 undefined를 반환한다.
이와 같이 찾아 체인을 따라 프로퍼티를 찾는 과정이 프로토타입 체이닝이다.


해당 프로퍼티가 객체 자신의 프로퍼티인지, prototype으로 상속받은 프로퍼티인지는 hasOwnProperty 메소드를 이용해 알 수 있다.
hasOwnProperty메소드는 모든 객체들의 조상인 Object.prototype에 정의 되어 있으며, 이 또한 프로토타입 체이닝을 통해 모든 객체가 사용 가능하다.


그외 Object.prototype(네이티브 프로토타입)도 프로퍼티를 추가해서 모든 객체들의 기능을 확장할 수 있는데(Object.prototype은 모든 객체의 조상이니 말이다) 이는 권장되는 방법은 아니다.



정리하자면 함수 객체는 자식에게 상속할 프로퍼티를 포함하는 prototype를 가지고 있다. prototype 프로퍼티는 객체의 원형을 담는 자신의 프로토타입 객체에 링크되고, 또한 객체를 생성할 때 객체의 [[Prototype]] 프로퍼티(__proto__)에 링크된다. (객체 생성 포스트를 참조하자, new 키워드를 이용해 생성될 때 연결된다.). 객체는 이 __proto__에 연결된 프로토타입 객체를 따라가 프로토타입에 정의된 프로퍼티를 객체 자신의 것처럼 사용할 수 있다. 부모 프로토타입에도 없을 경우, 부모가 상속받은 프로토타입을 찾아가며(__proto__프로퍼티를 통해 프로토타입 체인을 따라 올라가며) 해당 프로퍼티를 찾는다.

이렇게 따로 생성한 객체 말고도, Array나 Function 등의 객체들도 프로토타입의 상속을 기반으로 한다. Array나 Function이 내부적으로 가지고있는 메소드들은 바로 이 상속을 기반으로 가능한 것이다.

객체의 생성은 함수 객체(생성자 객체)에 의해 일어나지만, 상속에 관련된 모든 역할은 생성자 객체에 연결되어있는 프로토타입 객체에 의해 일어난다는 것을 기억하자. 

'Javascript' 카테고리의 다른 글

자바스크립트 - 실행 컨텍스트  (1) 2016.03.03
자바스크립트 - 객체 생성  (0) 2016.02.21
자바스크립트 - this 키워드  (0) 2016.02.04


문제 링크 : 알고스팟 NQUEEN

문제 링크 : 백준 N-QUEEN


N-Queen문제, 즉 여왕말 문제는 백트래킹 관련으로 정말 유명한 문제이다. 백트래킹이란 그냥 다음 탐색을 진행하는데, 그 탐색이 유망하지 않으면 무시하고 돌아가서다시 탐색한다는 것(백트래킹,되추적) 이다.

출처 위키피디아

여왕말에서 유망한 탐색인지 아닌지를 검사하는 조건은 정말 간단하다. 그냥 지금까지 고른 말의 위치 중에서 같은 열에 속하는 게 있는지, 혹은 대각선에 위치하는 게 있는지 검사하고 있으면 이 탐색을 무시하고(가지치기하고) 되돌아가 다음 탐색을 진행(백트래킹)한다.

끝까지 도달하였으면, 가능한 경우를 찾은 것이므로 카운트를 증가 시키고 반환하여 다른 경우를 찾는다.

밑은 이 풀이에 해당하는 코드이다.


#include <cstdio> #include <cmath> int n, t, a[13], count=0; //이 위치에 여왕 말을 놓을 수 있는지, 즉 유망한지 체크한다. bool check(int cur) { //0부터 이 행까지 모두 조사한다. for (int i = 0; i<cur; i++) { //열이 같은 것이 있거나, 대각선 범위 내에 있으면 불가능한 경우므로 false을 리턴 if(a[i]==a[cur] || cur-i==std::abs(a[cur]-a[i])){ return false; } } return true; } void nqueen(int cur) { //기저사례 : 끝에 도달하였으면 카운터를 증가 시키고 반환한다. if(cur==n-1) { count++; return; } //아직 끝에 도달하지 않았으면 다음 위치를 찾는다. for(int i=0;i<n;i++){ a[cur+1] = i; //이 위치가 유망한지 검사, check이 참이면 다음 여왕 말을 찾고, 못 찾으면 백트래킹한다. if(check(cur+1)){ nqueen(cur+1); } } } int main() { scanf("%d",&t); while(t--){ count = 0; scanf("%d", &n); nqueen(-1); printf("\n%d\n",count); } }


근데 이렇게 가지치며 나가는 것보다 더 빠른 방법이 있는 것 같다. 좀 더 공부가 필요한듯하다..

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26
알고스팟 - MORSE, DICT  (0) 2016.02.25
백준 - 1963 소수경로  (0) 2016.02.24
백준 - 2960 에라토스테네스의 체  (1) 2016.02.24

+ Recent posts