23.05.18. Today I learned

컴공실
선형대수학

컴공실

tetris project third week

//DrawShadow함수와 동일하게 작성하되 모양만 'R'이 되도록 구현
void DrawRecommend(int y, int x, int blockID, int blockRotate) {
    DrawBlock(y, x, blockID, blockRotate, 'R');
}

//트리를 생성 및 구현하는 과정을 합쳤다
//전달받는 최초의 root는 빈 노드이다
int recommend(RecNode* root) {
    int max=0;
    int curID=nextBlock[root->lv];
    int idx=0;
    int i,j,k,l;
    RecNode* node;

        //lv 1==nextBlock[0],...,lv 3==nextBlock[2]
        //2번째 예상블록까지 확인했다면 최대점수를 확인하고 갱신한다
    if((root->lv)+1 >VISIBLE_BLOCKS){
                //maxNode설정이 안되있으면 기본값으로 설정
        if(maxNode==NULL) maxNode=root;
        else if(root->score>maxNode->score) maxNode=root;
                //기저조건
        return 0;
    }
    for(i=0;i<blockAbleRotate[curID];i++){//i=blockRotate, 블록이 회전함에 따라 똑같은 경우가 발생함으로 미리 제거
        for(j=-3;j<WIDTH;j++){//j=x, 블록이 4X4 필드 에서 오른쪽 끝에 있는 경우를 고려해 -3부터 시작
            if(CheckToMove(root->f,curID,i,0,j)){
                                //실행가능한 블록 초기화
                root->c[idx]=(RecNode*)malloc(sizeof(RecNode));
                node=root->c[idx];
                node->lv=(root->lv)+1;
                node->parent=root;
                for(k=0;k<HEIGHT;k++){
                    for(l=0;l<WIDTH;l++){
                        node->f[k][l]=root->f[k][l];
                    }
                }

                                //각 회전, 각 위치에서 배치되는 위치 찾기
                for(k=1;k<HEIGHT;k++){//k=h
                    if(!CheckToMove(node->f,curID,i,k,j)) break;
                }
                                //해당 위치의 값을 기록해둔다.
                node->blockID=curID;
                node->recommendX=j;
                node->recommendY=k-1;
                node->recommendR=i;

                                //score는 기존에 만들어둔 함수를 호출
                node->score=root->score+AddBlockToField(node->f,curID,i,k-1,j)+DeleteLine(node->f);
                                //재귀호출
                recommend(root->c[idx]);
                idx++;
            }
        }
    }
    return max;
}

혼자힘으로는 해결하기 버거워서 결국 족보를 참고했다. 생각할 수 있는 부분들인데 놓쳐서 아쉬웠다.
이번 실습에서 짠 코드는 두개의 블록만을 예측하기때문에, 여러개의 블록을 예측하는 코드에 비해 점수 기댓값이 낮다. 그래서 nextBlock을 여러개 만들어서 여러개의 블록을 예측하게 할 수도 있지만, 이는 저번에도 말했듯 시공간복잡도가 기하급수적으로 증가한다.
그래서 유전적 알고리즘을 짜보고 싶은데, 이에대한 반복학습을 어떻게 할 지 모르겠다. 가중치를 임의로 잡아두고 한다 치면.. 최적의 가중치를 내 힘으로 찾아낼 수 있을까? GA에 대해 조금 더 알아볼 필요가 있을 것 같다.

선형대수학

개념확립하기

Orthogonal

같은 공간에 있는 두 subspace에 대해, 두 subspace의 아무 벡터나 가져와 내적을해도 0이 된다면 두 공간은 Orthogonal하다.

Orthogonal Complement

V를 W의 subspace라 가정하자. V의 orthogonal complement는
$V^\perp=\{\vec{w}\in W:\vec{w}\cdot\vec{v}=0 for all \vec{v}\in V\}$
로 정의할 수 있다.

Orthonormal

$R^m$ 공간 내에있는 벡터들 중, 벡터들의 크기가 1이고 같은 벡터를 내적하면 1, 다른 벡터를 내적하면 0인 값을 갖는 벡터들에 대해 Orthonormal하다고 한다.

Gram-Schmit

n차원공간에서 n개의 벡터(basis)가 주어졌을때, orthonormal한 벡터n개를 찾을 수 있다.
기준 벡터를 설정하고, 두번째 벡터는 두번째 벡터에서 처음으로 찾은 기준벡터에 대한 정사영 값을 뺀 걸로 구한다.
세번째 벡터는 세번째 벡터에서 첫번째 벡터에 대한 정사영값을 빼고, 두번째 벡터에 대한 정사영 값을 뺀 것으로 구한다.
이를 반복하여 공간을 span하는 orthonormal한 basis들을 찾을 수 있다.

determinant

기본성질 3가지

$\det I_n=1$
두개의 row를 교환하면 부호가 바뀐다.
각각의 독립적인 row들에 대해 선형성을 갖는다. 이들을 응용해 여러가지 성질을 찾을 수 있다.
두개의 row가 같다면, $\det A=0$
${E_i}_j(a)$ 는 determinant값을 변경시키지 않는다.
zero row가 있다면, $\det A =0$ 이다.
triangular matrix라면, $\det A=\Pi {a_i}_i$ , 즉 diagonal 요소중 하나라도 0이면 0이다.
A가 invertible이면 $\det A \ne 0$
A가 invertible이 아니면 $\det A == 0$ 이다.
$det(AB)=det(A)det(B)$
$det A^T =det A$ 주의할점은 선형성은 각row에 독립적으로 있다는 것이다.

formula

계산하는 방법. 크게 두가지가 있다.

triangular matrix를 만들어 계산한다. 2번째 방법이 잘 안보이면 쓰기 좋은 방법
row의 선형성을 이용한다. 각 row, column에서 하나의 entry씩만 가져와 곱한다. 0이 많을수록 빠르게 계산할 수 있다.
이를 통해 cofactor formula로 일반화 시킨다.

23.05.18.

Today I learned

컴공실​

tetris project third week​

recommend 실습 구현 완성​

선형대수학​

개념확립하기​

Orthogonal​

Orthogonal Complement​

Orthonormal​

Gram-Schmit​

determinant​

formula​

컴공실