가전제품 이것저것 이야기

1. Bottom-up 방식

www.acmicpc.net/problem/9461

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...

여기서 규칙이 보이나요?

규칙은 전전 값과 전전전 값을 더한 것입니다.

이를 bottom-up 방식으로 구현해보면 아래와 같습니다.

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int total, N;
vector<long long int> v;

int main(void) {
    
    cin >> total;
    
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(1);
    
    
    for(int k=0; k<total; k++){
        cin >> N;
        
        for(int i=(int)v.size(); i<=N; i++){
            v.push_back(v[i-2] + v[i-3]);
        }
        
        printf("%lld\n", v[N]);
    }
    
    return 0;
}

CASE 1) 순서 O, 중복 X

www.acmicpc.net/problem/15649

#include <stdio.h>
#include <iostream>
using namespace std;

int N, M;
int arr[9];
int ch[9];

void dfs(int depth){
    if(depth == M){
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    } else {
        for(int i=1; i<=N; i++){
            if(ch[i] == 0){
                ch[i] = 1;
                arr[depth] = i;
                dfs(depth + 1);
                ch[i] = 0;
            }
        }
    }
}

int main(void) {
    
    cin >> N >> M;
    
    dfs(0);
    
    return 0;
}

- check 배열과 arr 배열, 그리고 depth 를 사용하여 구현하였다.

CASE 2) 순서 X,  중복 X

www.acmicpc.net/problem/15650

#include <stdio.h>
#include <iostream>
using namespace std;

int N, M;
int ch[9];
int arr[9];

void dfs(int s, int depth){
    if(depth == M){
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    } else {
        for(int i=s; i<=N; i++){
            if(ch[i] == 0){
                ch[i] = 1;
                arr[depth] = i;
                dfs(i, depth+1);
                ch[i] = 0;
            }
        }
    }
}

int main(void) {
    
    cin >> N >> M;
    
    dfs(1, 0);
    
    return 0;
}

CASE 3) 순서 O, 중복 O

www.acmicpc.net/problem/15651 

#include <stdio.h>
#include <iostream>
using namespace std;

int N, M;
int arr[10];

void dfs(int depth){
    if(depth == M){
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    } else {
        for(int i=1; i<=N; i++){
            arr[depth] = i;
            dfs(depth+1);
        }
    }
}

int main(void) {
    
    cin >> N >> M;
    
    dfs(0);
    
    return 0;
}

CASE 4) 순서 X, 중복 O

www.acmicpc.net/problem/15652

#include <stdio.h>
#include <iostream>
using namespace std;

int N, M;
int arr[10];


void dfs(int s, int depth){
    if(depth == M){
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    } else {
        for(int i=s; i<=N; i++){
            arr[depth] = i;
            dfs(i, depth+1);
        }
    }
}

int main(void) {
    
    cin >> N >> M;
    
    dfs(1, 0);
    
    return 0;
}

< 결론 >

순서 X - 0부터 시작

순서 O - s 부터 시작

중복 X - ch 배열 안씀

중복 O - ch 배열 씀

1. 핵심 개념

값이 총 3개일 때, 트리 모양으로 가정합니다. D(1), D(2), D(3), D(4)가 있습니다. D() 안의 숫자는 level을 뜻합니다. D(1)은 0 0 0이고, D(2)는 첫째 값, D(3)는 둘째 값, D(4)는 셋째 값입니다. 루트부터 전위 순회를 하면서 왼쪽은 ch[level] = 1; 오른쪽은 ch[level] = 0; 입니다. level 1은 0 0 0입니다. level이 4일 때 부분집합을 출력합니다. 

void dfs(int level){
    
    if(level == N){
        if(!isEmpty()){
            for(int i=0; i<N; i++){
                if(ch[i] == 1)
                    sum += v[i];
            }
            if(sum == S)
                cnt++;
            sum = 0;
        }
        return;
    }
    
    ch[level] = 1;
    dfs(level+1);
    ch[level] = 0;
    dfs(level+1);
    
}

2. 백준 1182

www.acmicpc.net/problem/1182

#include <stdio.h>
#include <iostream>
#include <vector>
#define MAX_NUM 25
using namespace std;

int N, S;
int num;
int cnt = 0;
int ch[MAX_NUM];
vector<int> v;
int sum;

int isEmpty(){
    for(int i=0; i<N; i++){
        if(ch[i] == 1)
            return 0;
    }
    return 1;
}

void dfs(int level){
    
    if(level == N){
        if(!isEmpty()){
            for(int i=0; i<N; i++){
                if(ch[i] == 1)
                    sum += v[i];
            }
            if(sum == S)
                cnt++;
            sum = 0;
        }
        return;
    }
    
    ch[level] = 1;
    dfs(level+1);
    ch[level] = 0;
    dfs(level+1);
    
}

int main(void) {
    
    cin >> N >> S;
    
    for(int i=0; i<N; i++){
        cin >> num;
        v.push_back(num);
    }
    
    dfs(0);
    
    cout << cnt << endl;
    
    return 0;
}

1. Stack

- 선언

stack <char> s1;

- push

s1.push('c');

- pop

s1.pop();

- 스택 가장 위의 값

s1.top();

- 예제

#include<string>
#include <iostream>
#include <stack>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    stack <char> s1;
    
    for(int i=0; i<s.length(); i++){
        if(s[i] == '('){
            s1.push(s[i]);
        } else if(s[i] == ')'){
            if(s1.empty() || s1.top() == ')'){
                answer = false;
                break;
            }
            s1.pop();
        }
    }
    
    if(!s1.empty()){
        answer = false;
    }
    
    
    return answer;
}

2. Queue

- 선언

Queue<int> q;

- push

q.push(1);

- pop

q.pop();

- 큐 맨 앞의 값

q.front();

- 큐 맨 뒤의 값

q.back();

- 비었는지 체크

q.empty();

- 큐에 몇 개의 값이 들었는지

q.size();

aonee.tistory.com/16

Event

브라우저에는 많은 이벤트가 발생합니다.

브라우저 화면의 크기를 마우스로 조절할 때도, 스크롤을 할 때도, 마우스로 이동하거나 무언가를 선택할 때도 
이벤트가 발생합니다.

이벤트를 브라우저가 발생시켜주니, 우리는 그때 어떤 일을 하라고 할 일을 등록할 수가 있습니다.

다시 말해, HTML엘리먼트별로 어떤 이벤트(주로 키보드나 마우스 관련)가 발생했을 때 특정 행위를(어떤 일) 하고 싶다면, 대상엘리먼트를 찾고 어떤 일을 등록하면 된다.

그것을 자바스크립트로 구현할 수 있습니다.

이벤트 등록

이벤트 등록 표준방법입니다.

addEventListener 함수를 사용할 수 있습니다.

var el = document.querySelector(".outside");

el.addEventListener("click", function(){
	//do something..
}, false);

addEventListener 함수의 두 번째 인자는 함수입니다.

이 함수는 나중에 이벤트가 발생할 때 실행되는 함수로 이벤트핸들러(Event Handler) 또는 이벤트리스너(Event Listener)라고 합니다.

콜백함수는 이벤트가 발생할 때 실행됩니다. 

이벤트 객체

브라우저는 이벤트 리스너를 호출할 때, 사용자로부터 어떤 이벤트가 발생했는지에 대한 정보를 담은 이벤트 객체를 생성해서 리스너 함수에 전달합니다.

따라서 이벤트리스너 안에서는 이벤트객체를 활용해서 추가적인 작업을 할 수 있게 됩니다. 

var el = document.getElementById("outside");

el.addEventListener("click", function(evt){
	 console.log(evt.target);
	 console.log(evt.target.nodeName);
}, false);

가장 많이 쓰이는 건 event.target입니다.

event.target은 이벤트가 발생한 element를 가리킵니다. 

element도 객체이므로 안에 nodeName이나 classname과 같이 element가 가진 속성을 사용할 수 있습니다.