Permutation

m개의 main dish 와 n개의 side dish 가 있다.
main dish 와 side dish 는 중복선택 불가하다고 할 때, main dish 와 side dish 로 가능한 모든 조합을 구해보자.

예를 들어, 2개의 main dish와 3개의 side dish가 있다면,
경우의 수는 3x2 = 6 이고, 모든 경우의 수는
{(m1, s1), (m2, s2)}
{(m1, s1), (m2, s3)}
{(m1, s2), (m2, s1)}
{(m1, s2), (m2, s3)}
{(m1, s3), (m2, s1)}
{(m1, s3), (m2, s2)}
for (int m1=s1; m1<=s3; m1++)
    for (int m2=s1; m2<=s3; m2++)
        if (m1==m2) continue;
        printf("(m1, %d), (m2, %d)", m1, m2)

3개의 main dish와 3개의 side dish가 있다면, 3x2x1 = 6가지 경우이며,
{(m1, s1), (m2, s2), (m3, s3)}
{(m1, s1), (m2, s3), (m3, s2)}
{(m1, s2), (m2, s1), (m3, s3)}
{(m1, s2), (m2, s3), (m3, s1)}
{(m1, s3), (m2, s1), (m3, s2)}
{(m1, s3), (m2, s2), (m3, s1)}
for (int m1=s1; m1<=s3; m1++)
    for (int m2=s1; m2<=s3; m2++)
        if (m1==m2) continue;
        for (int m3=s1; m3<=s3; m3++)
            if (m3==m1 || m3==m2) continue;
            printf("(m1, %d), (m2, %d), (m3, %d)", m1, m2, m3)

for loop 로 구현하면 m,n 값에 맞게 일일이 iterator 변수를 추가해주어야 하는 문제가 있음.
main dish2는 main dish1과 조합을 이루지 않은 side dish 중 한 개,
main dish3은 main dish1, main dish2와 조합을 이루지 않은 side dish 중 한 개 이므로
재귀로 구현해보면, 아래와 같음. (좀 더 간결하게 되려나)

#include <stdio.h>

void select(int id, int selected[3])
{
    if (id == 2) {
        int temp;
        for (int iter = 0; iter < 3; iter++) {
            if (selected[iter] == -1) {
                temp = iter;
                break;
            }
        }
        selected[temp] = id;
        for (int iter = 0; iter < 3; iter++) {
            printf("(%d %d) ", iter, selected[iter]);
        }
        printf("\n");
        selected[temp] = -1;
        return;
    }
    for (int iter = 0; iter < 3; iter++) {
        if (selected[iter] == -1) {
            selected[iter] = id;
            select(id+1, selected);
            selected[iter] = -1;
        }
    }
}

int main()
{
    int selected[3] = {-1, -1, -1};
    select(0, selected);
    return 0;
}

printf 부분 대신 다른 로직을 넣으면 permutation 경우의 수마다 특정 처리를 하는게 가능해보임. 예를 들면, main dish + side dish 조합 중 가장 가격이 싼 경우를 구할 때, printf 대신에 lowest_total_price 를 갱신하도록 하면 됨.

일단 코드를 좀 더 간결하게 하는 게 필요함.
또한 재귀 깊이가 어느 정도까지 가능한 지도 업데이트 할 것.

path register

# vi .bash_profile 하고 열어 보시면,

PATH=$PATH:$HOME/bin <-- 이런 부분이 보일겁니다.

# source .bash_profile

----------------------------------------------------------------
# vi /etc/profile

PATH=$PATH:/usr/local/sbin:/usr/local/tomcat/bin
export PATH

맨뒤에 위의 두줄을 추가 시켜 주시고

# source /etc/profile 해주시면 적용됩니다.
 

Getting a source and building of Kitkat

[Prepare the environment]

① Python and Make Utility 

  Python이나 Make 유틸리티 같은 경우에는 기본적으로 리눅스 패키지에 포함되어 있다.

혹시 설치 시에 누락되었을 경우 apt-get 설치 관리자를 통하여 쉽게 다음 명령어로 쉽게 설치 가능하다.

$ sudo apt-get install python   $ sudo apt-get install make

② JAVA JDK

  JDK를 설치하는 방법은 다음과 같이 안드로이드 사이트에 명시되어 있다.

sudo add-apt-repository ppa:webupd8team/java  sudo apt-get update  sudo apt-get install oracle-java6-installer

더 상세히 보면....

먼저, python-software-properties 패키지가 필요한데 보통은 기본적으로 깔려있다.
하지만 없는 경우도 있으니 다음 커맨드로 먼저 설치하여 준다.

$ sudo apt-get install python-software-properties

그리고 나서 다음 명령을 입력하여 준다. 

첫 번째 명령을 치면 계속하려면 Enter, 중지하려면 Ctrl + C 키를 입력하라고 나오는데
ENTER를 쳐주면 계속해서 다운로드 패키지를 등록한다.

$ sudo add-apt-repository ppa:ferramroberto/java   $ sudo apt-get update

그러면 sun-java6-jdk 패키지가 등록이 되고 설치가 된다. java6-jdk와 플러그인 설치를 위해
다음의 명령어로 설치 할 수 있다.

$ sudo apt-get install sun-java6-jdk sun-java6-plugin

  

그런데 위의 명령을 통해서 JDK를 설치 할 수 있으나 버젼이 java 6만이 가능하다.

따라서 java7, java8 등 상위버전을 설치하고 싶다면 다음 명령으로 설치 가능하다.

$ sudo add-apt-repository ppa:webupd8team/java   $ sudo apt-get update

그러면 Oracle Java Installer를 통해서 원하는 버전의 자바 JDK의 설치가 가능하다.

Java 6를 설치하려면,

$ sudo apt-get install oracle-java6-installer

Java 7을 설치하려면,

$ sudo apt-get install oracle-java7-installer

Java 8을 설치하려면,

$ sudo apt-get install oracle-java8-installer

설치 후 이미 중복 설치되어 있는 여러버전의 JDK를 관리해 줄 필요가 있을 수 있다.

그럴 때는 다음 명령어를 통해서 원하는 JDK를 선택하여 주면 된다.

$ sudo update-alternatives --config java

선택       경로                                    우선순  상태 ----------------------------------------------------------------------------------------------------- * 0            /usr/lib/jvm/java-8-oracle/jre/bin/java       1062      자동 모드    1            /usr/lib/jvm/java-6-openjdk/jre/bin/java    1061      수동 모드    2            /usr/lib/jvm/java-8-oracle/jre/bin/java       1062      수동 모드 기본 사항[*]을 사용하려면 엔터, 다른 것을 사용하려면 번호를 입력하십시오:

그럼 위와 같은 콘솔 화면이 나오는데 목록 중 원하는 JDK의 번호를 입력하여 선택해 주면 된다.

선택된 자바의 버전을 확인하기 위해서 다음 명령어를 통해 확인하여 본다.

$ java -version

③ GIT

  리눅스 커널은 git에 의해 버전이 관리되고 다운로드 할 수 있다.

따라서 git을 설치해주어야 한다. git 또한 apt-get을 이용하여 손쉽게 설치 가능하다.

$ sudo apt-get install git

 2. 필요한 라이브러리 패키지들

우분투의 버전마다 필요한 라이브러리가 살짝 다르긴 하다. 구글에서는 우분트 10.04 64비트를 권장하고 있다. 

  안드로이드 사이트에서는 우분투 버전 10.04 ~ 11.10에 해당하는 시스템들은 다음 명령어를 통하여 필요한 라이브러리를 설치하라고 명시되어 있다.

$ sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev libc6-dev lib32ncurses5-dev ia32-libs x11proto-core-dev libx11-dev lib32readline-gplv2-dev lib32z1-dev libgl1-mesa-dev g++-multilib mingw32 python-markdown libxml2-utils xsltproc

하지만, 이 또한 업데이트가 되지 않아 몇 가지 라이브러리가 오류가 발생한다.

오류가 발생하거나 대체된 것들을 수정한 다음 명령어를 실행하면 한번에 설치 가능하다.

 [ ubuntu 10.04에서 ] 

$ sudo sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev libc6-dev lib32ncurses5-dev ia32-libs x11proto-core-dev libx11-dev lib32readline5-dev lib32z1-dev libgl1-mesa-dev g++-multilib mingw32 python-markdown libxml2-utils xsltproc libpcsclite-dev

[ ubuntu 11.10에서 ] 

$ sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev libc6-dev lib32ncurses5-dev ia32-libs x11proto-core-dev libx11-dev lib32readline-gplv2-dev lib32z1-dev libgl1-mesa-dev g++-multilib mingw32 python-markdown libxml2-utils xsltproclibpcsclite-dev

우분투 10.10 인 경우에는 다음 명령을 통하여 링크하나를 생성해 준다.

$ sudo ln -s /usr/lib32/mesa/libGL.so.1 /usr/lib32/mesa/libGL.so

우분투 11.10은 추가적으로 패키지 하나를 추가로 설치하여 준다.

$ sudo apt-get install libx11-dev:i386

우분투 12.04 버전인 경우 다음 명령을 통하여 설치해 준다.  

$ sudo apt-get install git-core gnupg flex bison gperf build-essential \   zip curl libc6-dev libncurses5-dev:i386 x11proto-core-dev \   libx11-dev:i386 libreadline6-dev:i386 libgl1-mesa-glx:i386 \   libgl1-mesa-dev g++-multilib mingw32 openjdk-6-jdk tofrodos \   python-markdown libxml2-utils xsltproc zlib1g-dev:i386

 하지만 libgl1-mesa-glx:i386 패키지가 libglapi-mesa:i386 의존성으로 인해 설치가 안 되므로
 libglapi-mesa:i386패키지를 추가하여  설치하여 준다. 또한 "make menuconfig"를 수행하기 위하여

필요한 lib32ncurses5-dev 도 미리 설치하여 준다.

$ sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl libc6-dev libncurses5-dev:i386 x11proto-core-dev libx11-dev:i386 libreadline6-dev:i386 libglapi-mesa:i386 libgl1-mesa-glx:i386 libgl1-mesa-dev g++-multilib mingw32 openjdk-6-jdk tofrodos python-markdown libxml2-utils xsltproc zlib1g-dev:i386 lib32ncurses5-dev

혹시 다음과 같은 에러가 발생한다면,  

다음 패키지의 의존성이 맞지 않습니다:  lib32ncurses5-dev : 의존: libncurses5-dev (= 5.9-4) 하지만 %s 패키지를 설치하지 않을 것입니다 E: 문제를 바로잡을 수 없습니다. 망가진 고정 패키지가 있습니다.

위의 패키지에서 libncurses5-dev만 빼고 설치 후

$ sudo apt-get install lib32ncurses5-dev 명령으로 libncurses5-dev만 따로 설치해 준다.

다음 명령을 통하여 링크 파일도 생성하여 준다. 

$ sudo ln -s /usr/lib/i386-linux-gnu/mesa/libGL.so.1 /usr/lib/i386-linux-gnu/libGL.so

Install the repo:

Code:

$ mkdir ~/bin
$ PATH=~/bin:$PATH
$ curl http://commondatastorage.googleapis.com/git-repo-downloads/repo > ~/bin/repo
$ chmod a+x ~/bin/repo

6) Initialize the repo:

Code:

$ mkdir WORKING_DIRECTORY
$ cd WORKING_DIRECTORY

6a) For AOSP:

Code:

$ repo init -u https://android.googlesource.com/platform/manifest -b android-4.4_r1

6.1) For people who have already done a repo init:

Code:

$ cd WORKING_DIRECTORY

AOSP:

Code:

$ repo init -b android-4.4_r1
$ repo sync

7) When prompted, enter your real name and email address.

8) Gather the files:

Code:

$ repo sync

 7) Navigate back to your home directory for building:

Code:

$ cd ~/WORKING_DIRECTORY

8) Prepare To Compile:

Code:

$ source build/envsetup.sh

Or:

Code:

$ . build/envsetup.sh

9) Get your list of devices:

Code:

$ lunch

10) Pick your poison.

11) Now compile ('#' being the number of cores in your processor +1):

Code:

$ make -j#

Or for a flashable zip:

Code:

$ make -j# otapackage

Emulate an Android Device

The emulator is added to your path automatically by the build process. To run the emulator, type

$ emulator

[출처] 우분투에서 안드로이드 소스 컴파일 환경 구축|작성자 또갈이

[Reference]
http://blog.naver.com/PostView.nhn?blogId=ysjin1212&logNo=110166566875
http://forum.xda-developers.com/showthread.php?t=2506695
http://source.android.com/source/building-running.html

Freeze in Ubuntu logo in boot

[Reason]
lightdm (light gdm) has some bugs. It is still in develop. So, suggest gdm instead of it.

[Solution]
1. Press Ctrl+Alt+F1 to get to a text-based virtual console
2. Uninstall lightdm and install gdm instead.

sudo apt-get remove lightdm
sudo apt-get update
sudo apt-get install gdm
sudo start gdm

3. When you fail to log-in,

sudo apt-get update

sudo apt-get install ubuntu-desktop

sudo apt-get install -f install

sudo dpkg-reconfigure ubuntu-desktop

sudo reboot

[Reference]

http://askubuntu.com/questions/175481/ubuntu-12-gdm-install-remove-problem

http://askubuntu.com/questions/205872/failed-to-load-session-ubuntu

ClockSync

Initial think

#include <stdio.h>

int c;
int clkTime[16];
int clkOfSW[10][5] = {
    {0,1,2,-1,-1},//0
    {3,7,9,11,-1},
    {4,10,14,15,-1},
    {0,4,5,6,7},
    {6,7,8,10,12},
    {0,2,14,15,-1},//5
    {3,14,15,-1,-1},
    {4,5,7,14,15},
    {1,2,3,4,5},
    {3,4,5,9,13}//9
};
int swSize2[10] = {3,4,4,5,5,4,3,5,5,5};

int swOfClk[16][4] = {
    {0,3,5,-1},
    {0,8,-1,-1},
    {0,5,8,-1},
    {1,6,8,9},
    {2,3,5,8},
    {3,7,8,9},//5
    {3,4,-1,-1},
    {1,3,4,7},
    {4,-1,-1,-1},
    {1,9,-1,-1},
    {2,4,-1,-1},//10
    {1,-1,-1,-1},
    {4,-1,-1,-1},
    {9,-1,-1,-1},
    {2,5,6,7},
    {2,5,6,7}//15
};
int swSize[16]= {3,2,3,4,4,4,2,4,1,2,2,1,1,1,4,4};
int curMin,cnt;
void sub();

FILE* fin;
FILE* fout;
int press[20000];
int pressCnt;

void main()
{
    fin = fopen("in.txt","r");
    fout = fopen("out.txt","w");

    //scanf("%d", &c);
    fscanf(fin,"%d",&c);
    for (int i=0; i<c; i++)
    {
        for (int j=0; j<16; j++)
            //scanf("%d",&(clkTime[j]));
            fscanf(fin,"%d",&(clkTime[j]));

        curMin = 65535;
        cnt= 0;
        pressCnt=0;
        sub();
        //printf("%d\n",curMin);
        fprintf(fout,"%d\n",curMin);
    }

    fclose(fin);
    fclose(fout);
}

void sub()
{
    int clk = 0;
    while (clk<15)
    {
        if (clkTime[clk] != 12) {
            break;
        }
        clk++;
    }

    if (clk == 15)
    {
        if(curMin > cnt)
        {
            curMin = cnt;
            fprintf(fout,"clk=15. cnrMin=%d\n\n",curMin);
        }
        return;
    }

    for(int sw=0; sw<swSize[clk]; sw++)
    {
        for (int cc=0; cc<swSize2[sw]; cc++)
        {
            clkTime[clkOfSW[sw][cc]] += 3;
            if(clkTime[clkOfSW[sw][cc]] > 12) clkTime[clkOfSW[sw][cc]] -= 12;
        }
        cnt++;
        press[pressCnt++] = sw;
        fprintf(fout, "%d press. cnt=%d\n", sw, cnt);
        for(int jj=0; jj<pressCnt; jj++)    fprintf(fout,"%d ", press[jj]);     fprintf(fout,"\ntime: ");
        for(int jj=0; jj<16; jj++)          fprintf(fout,"%d ", clkTime[jj]);   fprintf(fout,"\n");

        sub();

        for (int cc=0; cc<swSize2[sw]; cc++)
        {
            clkTime[clkOfSW[sw][cc]] -= 3;
            if(clkTime[clkOfSW[sw][cc]] == 0) clkTime[clkOfSW[sw][cc]] = 12;
        }
        cnt--;
        pressCnt--;
        fprintf(fout, "%d unpress. cnt=%d\n", sw, cnt);
        for(int jj=0; jj<pressCnt; jj++)    fprintf(fout,"%d ", press[jj]);     fprintf(fout,"\ntime: ");
        for(int jj=0; jj<16; jj++)          fprintf(fout,"%d ", clkTime[jj]);   fprintf(fout,"\n");
    }
}

BoardCover

Correct answer


#include <stdio.h>
#include <assert.h>

int testNum, row, col;
int Board[20][20];
int whiteCnt;
int ans;
void sub();


FILE *fin, *fout;
void printBoard(FILE *fp)
{    
    for (int r=0; r<row; r++)
    {        
        for(int c=0; c<col; c++)
            fprintf(fp, "%d ", Board[r][c]);
        fprintf(fp, "\n");
    }
}

int main()
{
    //fin = fopen("in.txt", "r");
    //fout = fopen("out.txt", "w");
    //fscanf(fin, "%d",&testNum);
    scanf("%d",&testNum);
    for (int ii=0; ii<testNum; ii++)
    {
        for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
                Board[r][c] = -1;
        whiteCnt = 0;
        ans = 0;
        //fscanf(fin, "%d%d",&row,&col);
        scanf("%d%d",&row,&col);
        char newline;
        //fscanf(fin, "%c", &newline);
        scanf("%c", &newline);
        for (int r=0; r<row; r++)
        {
            char buffer[20] = {0, };
            fgets(buffer, 20, stdin);
            for (int c=0; c<col; c++)
            {
                if(buffer[c]=='#')
                    Board[r][c] = 0;
                else if(buffer[c]=='.')
                {
                    Board[r][c] = 1;
                    whiteCnt++;
                }
                else assert(0);
            }
        }
        // do my work
        //printBoard(fout);
        sub();
        //fprintf(fout, "\nans = %d\n", ans);
        printf("%d\n", ans);
    }
    //fclose(fin);
    //fclose(fout);
    return 0;
}

void sub()
{
    //fprintf(fout, "--------------------\n");
    //fprintf(fout, "row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printf("row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printBoard(fout);
    if (whiteCnt == 0)
    {
        ans++;
        //fprintf(fout, "ok! return. ans=%d\n", ans);
        //printf("ok! return.\n");
        return;
    }
    if (whiteCnt < 3)
    {
        //fprintf(fout, "no room. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("no room. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }
    if (whiteCnt % 3 != 0)
    {
        //fprintf(fout, "not multiple of 3. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("not multiple of 3. stop here. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }
    bool find=false;
    int r=0, c=0;
    for (r=0; r<row; r++)
    {
        for (c=0; c<col; c++)
        {
            if (Board[r][c]==1)
            {
                find=true;
                break;
            }
        }
        if(find==true)  break;
    }

    if (find == false)
    {
        //printf("no white.\n");
        ans++;
        return;
    }

    //fprintf(fout, "(%d %d) ", r, c);
    // shape1
    // 1 1
    // x 1
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c+1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 1 matched\n", r, c);
        Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c+1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 1 roleback\n", r,c );
        whiteCnt+=3;
        Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c+1]=1;
        //printBoard(fout); 
    }
    // shape2
    // x 1
    // 1 1
    if (r+1<row && c-1>=0 && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c-1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 2 matched\n", r, c);
        Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c-1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 2 roleback\n", r, c);
        whiteCnt+=3;
        Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c-1]=1;
    }
    // shape3
    // 1 x
    // 1 1
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c+1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 3 matched\n", r, c);
        Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c+1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 3 roleback\n", r, c);
        whiteCnt+=3;
        Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c+1]=1;
        //printBoard(fout);
    }
    // shape4
    // 1 1
    // 1 x
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 4 matched\n", r, c);
        Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 4 roleback\n", r, c);
        whiteCnt+=3; 
        Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c]=1; 
        //printBoard(fout);
    }
    //fprintf(fout, "no. return\n");
}