반응형

문제

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


다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1
2
3
4
5
6
7
8
9
10
11
int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

  • fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
  • fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
  • 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
  • fibonacci(0)은 0을 출력하고, 0을 리턴한다.
  • fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
  • 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
  • fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.


입력

3
0
1
3

출력

1 0
0 1
1 2


fibonacci(n) 이하 fi(n)은 피보나치 함수이다.

fi(0)과 fi(1)은 각각 0과 1을 반환하며 fi(2)는 fi(1)+fi(0)임을 알 수 있다.

이때 fi(1)은 1이 출력되는 횟수 fi(0)은 0이 출력되는 횟수로 접근하면 된다.


fi(2) = fi(1) + fi(0)

fi(3) = fi(2) + fi(1) = fi(1) + fi(0) + fi(1)

fi(4) = fi(3) + fi(2) =  fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) 

fi(5) = fi(4) + fi(3) = fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)

==> fi(1) + fi(0) + fi(1) + fi(1) + fi(0) + fi(1) + fi(0) + fi(1)


 

 0 횟수

1 횟수 

 fi(2)

1 

1 

 fi(3)

1 

2 

 fi(4)

2 

3 

 fi(5)

3

5 


표를 보면 더 쉽게 규칙을 찾을 수 있다

즉 fi(4) 에서 0과 1의 횟수는 fi(2)의 횟수 + fi(3)의 횟수 이며 

fi(5)도 fi(4)의 횟수 + fi(3)의 횟수이다.

따라서 fi(n) = fi(n-1) + fi(n-2) 라는 점화식을 뽑아낼 수 있다.


소스

//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 06. 28

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;


void fibo(int n);

void init();

int dp[2][41] = {0};

int main()

{

int T,n; // 0<=n<=40

cin>>T;

init();

while(T>0){

T--;

cin>>n;

fibo(n);

cout<<dp[0][n]<<" "<<dp[1][n]<<endl;

}

return 0;

}

void fibo(int n)

{

for(int i=2;i<=n;i++){

dp[0][i] = dp[0][i-1] + dp[0][i-2];

dp[1][i] = dp[1][i-1] + dp[1][i-2];

}

}

void init()

{

dp[0][0] = 1;

dp[0][1] = 0;

dp[1][0] = 0;

dp[1][1] = 1;

}


이와 같이 2차원 배열을 이용하여 쉽게 프로그램을 구현할 수 있다.

dp로 풀이하지 않아도 쉬운 문제이나 dp로 풀지 않은 소스와 dp로 푼 소스는 실행시간에 큰 차이를 보인다.

반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 9095] 1,2,3 더하기  (0) 2018.03.27
반응형

문제

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


문제 설명

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

예제 입력

3
4
7
10

예제 출력

7
44
274



1을 만드는 방법 =  1가지

(1)

2를 만드는 방법 = 2가지

(1+1) / (2)

3을 만드는 방법 = 4가지

(1+1+1) / (1+2) / (2+1) / (3)

4를 만드는 방법 = 7가지

(1+1+1+1) / (1+1+2) / (1+2+1) / (1+3) / (2+1+1) / (2+2) / (3+1)

5를 만드는 방법 = 12가지

.....


3을 만드는 방법에서 예를 들면

1+1+1 에서 가장 앞 부분인 1을 제외하면

2를 만드는 방법의 가지수를 구해주면 2가지 이다.


이후 가장 먼저 2를 더할 때는 3-2의 값인 1을 만드는 경우의 수

3을 가장 먼저 더할때는 3을 만들 수 있는 경우의 수를 구하는 방식이다.


즉

dp[3] = 4 인 것을 구했다면

dp[4] 를 유추해 보자


dp[4] = 1 + dp[3]

  + 2 + dp[2]

  + 3 + dp[1]

임을 알 수 있으며 이는 4 + 2 + 1 = 7가지의 방법으로 4를 만들 수 있다.


이 점화식을 일반화 시키면 dp[n] = dp[n-1]+ dp[n-2] + dp[n-3] 이므로 이후 소스 작성은 어렵지 않을 것이다.


소스


//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 3. 27..

//  Copyright © 2018년 seungwoo. All rights reserved.

//


#include <iostream>

#include <algorithm>


using namespace std;


int main(int argc, const char * argv[]) {

    

    int testcase,n;

    int dp[11]; //N<11

    cin>>testcase;

    

    // f(n) = f(n-1) + f(n-2) + f(n-3)

    dp[1] = 1;

    dp[2] = 2;

    dp[3] = 4;

    for(int i = 0; i<testcase; i++){

        cin>>n; //정수 n

        for(int j=4;j<=n;j++){

            dp[j] = dp[j-1] + dp[j-2] + dp[j-3];

        }

        cout<<dp[n]<<endl;

    }

    return 0;

} 





반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28
반응형

○ 정규화란

/*

한 마디로 DB서버의 메모리 낭비를 낭비하지 않도록 하기 위해서

어떤 테이블을 식별자를 가지는 여러 개의 테이블로 나누는 과정

막 나누는 것이 아니라 다시 JOIN할 수 있도록 식별자를 가져야 한다!


정규화는 순차적으로 진행되어야 한다



EX) 개발자로써의 진로를 포기한 김선규 사원이

    정승우 사원의 유혹에 넘어가 옥장판 영업사원으로 취업을 하게 되었다.

    이 때 『거래처직원』정보를 데이터베이스화 하려고 한다.

    

    테이블명 : 거래처직원

       10byte     10byte      10byte        10byte      10byte      10byte        10byte    

-----------------------------------------------------------------------------------------------

    거래처회사명  회사주소   회사전화     거래처직원명  직급       이메일          핸드폰

-----------------------------------------------------------------------------------------------

        농심    여의대방로  02-345-6789    명소희       대리    SO@NAVER.COM    010-1111-1111

        농심    여의대방로  02-345-6789    임미영       대리    MI@NAVER.COM    010-2222-2222

        농심    여의대방로  02-345-6789    조태희       부장    TE@DAUM.COM    010-3333-3333

        삼양    서울소공동  02-555-8888    박기범       주임    KI@NAVER.COM    010-5555-5555

        농심    강원원주로  033-99-9999    서운성       차장    UN@GMAIL.COM    010-4444-4444

                                            :

                                            :

                                     (100만 이상)  

                                          

 (농심 본사만 100만명)

 TABLE에서 이상한 점을 찾아보자!!

 =>아마 99.9%사람들 모두 이상이 없다고 할 것이다.

 

 가정) 여의대방로 농심 이라는 회사에 근무하는 거래처 직원 명단이

       본사 직원만 100만 명이라고 가정한다. (한 행은 10byte 이다)

       

       어느날 여의대방로에 위치한 농심 본사가 경기 분당으로 사옥을 이전하였다.

       

       --UPDATE를 수행해야 할 상황이 발생하게 되었다.(이 때 구성해야 하는 쿼리문)

       UPDATE 거래처직원

       SET 회사주소='경기 분당', 회사전화='031-345-6789'

       WHERE 거래처회사명='농심'

         AND 회사주소='여의대방로';

       

       --그러면 100만명의 회사 주소와 회사 전화 정보를 변경해야 하며 

         100만 개 행을 하드디스크상에서 읽어다가 메모리에 로드시켜 주어야 한다.

         즉, 100만 * 70byte 를 모두 하드디스크상에서 읽어다가 메모리에 로드시켜 주어야 한다는 말이다.

         

       --이는, 테이블의 설계가 잘못되었으므로 DB서버는 조만간 메모리 고갈로 인해 DOWN될 것이다.

         (물론 H/W사양이 좋아져서 너무 과장되었다고 생각할 수 있지만 많은 사람들이 이용하는 서버라는 것을 생각하자)

       

       --==>> 그러므로 정규화 작업에 들어간다!

       

 ■ 제 1 정규화

    어떤 테이블에 반복되는 컬럼값들이 존재하면

    값들이 반복되어 나오는 컬럼을 분리하여

    새로운 테이블은 만들어준다.

    

    거래처직원 → 회사 + 직원

    

    테이블명 : 회사


    테이블명 : 직원

  

  핵심은 반복되는 컬럼을 찾는 것과 식별자를 추가OR지정해 주는 것이다!  

  1정규화를 진행하면 100%(예외X) 부모테이블과 자식테이블로 나뉘게 된다. (1 : 다 관계)

  부모 - 참조받는 컬럼(PRIMARY KEY)

  자식 - 참조하는 컬럼(FOREIGN KEY)

  

  부모테이블의 PK는 반드시 자식테이블의 FK로 전이된다.

  

 ■ 제 2 정규화

    복합 PRIMARY KEY를 가지고 있는 테이블이 대상이다. 그리고 무조건 2정규화를 진행해야 한다.

    만약 1정규화를 진행했지만 단일 PRIMARY KEY만이 존재한다면 2정규화를 하지 않아도 된다.

    

    ※ 수행에 대한 전제 조건

       대상 테이블이 단일 PRIMARY KEY로 구성되어 있을 경우 2 정규화는 수행하지 않는다.

       단, 복합 PRIMARY KEY로 구성되어 있을 경우 반드시 2 정규화를 수행해야 한다.

       

    테이블명 : 주문

    ----------------------------------------------------------------------

       고객ID    제품코드    주문일자    주문수량

        PK          PK          PK         

    ----------------------------------------------------------------------

        어떤 테이블에 PRIMARY KEY 제약조건은 최대 1개까지 설정할 수 있다.

        단, 여러 컬럼을 묶어서 설정할 수 있다. → 복합 프라이머리 키

        

    ----------------------------------------------------------------------

    테이블명 : 과목 → 부모 테이블

    ----------------------------------------------------------------------

    과목번호   과목명      교수번호  교수명   강의실코드     강의실설명

      PK                          PK

    1정규화를 진행하면 부모테이블의 PK가 자식테이블의 FK로 전이된다.

    ----------------------------------------------------------------------

    DB0101   오라클기초      21      에디슨     G309       전산실습관 3층 50석

    DB0101   오라클기초      22      장영실     H402       인문과학관 4층 100석

    DB0102   오라클고급      22      장영실     H402       인문과학관 4층 100석

    JV0103   자바심화        25      우장춘     H402       인문과학관 4층 100석

                                  :

    

    ----------------------------------------------------------------------

    테이블명 : 점수 → 자식 테이블

    학번은 PK가 될 수 없다! 다른 과목을 들을 수 있기 때문

    ----------------------------------------------------------------------

    과목번호  교수번호    학번      학생명   점수

      FK            FK

      PK                         PK

    ----------------------------------------------------------------------

    DB0101      21      1817110     오승우    98

    DB0101      21      1817116     최진규    89

                            :

 

    다중 PK일때 원래는 식별자 전체에 의존적이여야 하지만 

    다른 하나PK에 의존적이지 않은 컬럼이 존재하다면 

    따르지 않은 컬럼과 다른 하나PK를 따로 테이블을 생성한다.

    

    과목테이블에서 과목번호 / 교수번호가 과목명을 식별하는 것이 아니라

    오직 과목명은 과목번호에만 의존적이므로 따로 테이블을 생성한다.

    

    즉, 식별자가 아닌 컬럼은 식별자에게 의존적이여야 한다!

    -> 이를 해결해주는 것이 2정규화

    

    식별자가 아닌 컬럼은 식별자 전체 컬럼에 대해 의존적이여야 하는데

    식별자 전체 컬럼에 대해 의존적이지 않고 식별자 일부에만 의존적이라면 

    이를 분리하여 새로운 테이블을 생성한다.

    

 ■ 제 3 정규화

    식별자가 아닌 컬럼에 포커싱

    식별자가 아닌 컬럼이 식별자가 아닌 컬럼에 의존적이라면 이를 분리하여

    새로운 테이블을 생성한다.

    

    -----------------------------------------------------------------------

    테이블명 : 과목 → 부모 테이블

    ----------------------------------------------------------------------

    과목번호   과목명      교수번호  교수명   강의실코드     강의실설명

      PK                           PK

    1정규화를 진행하면 부모테이블의 PK가 자식테이블의 FK로 전이된다.

    ----------------------------------------------------------------------

    DB0101   오라클기초      21      에디슨     G309       전산실습관 3층 50석

    DB0101   오라클기초      22      장영실     H402       인문과학관 4층 100석

    DB0102   오라클고급      22      장영실     H402       인문과학관 4층 100석

    JV0103   자바심화        25      우장춘     H402       인문과학관 4층 100석

                                  :

                                  

    강의실설명은 강의실코드에 의존적이다. 하지만 강의실코드와 강의실설명 모두 

    식별자가 아닌 컬럼이므로 제 3정규화를 통해 『강의실』이라는 테이블을 새로 생성한다.

    

 ■ 제 4 정규화

    ※관계의 종류

    1 : 1   = 

    1 : 다  = 가장 바람직한 관계 (1정규화를 마친 상태)

    다 : 다 = 논리적으로는 존재하지만 물리적으로는 불가능/존재하지 않는 관계

    

    다:다 관계를 1:다의 관계로 깨뜨리는 것이 바로 4정규화이다.

    학생 - 수강신청 - 강의

    고객 - 주    문 - 제품

    과 같은 관계를 생성하는 것이 4정규화


 ■ 역 정규화(비 정규화)

    다시 합치는 행위 

    쪼개놓고 보니까 나중에 보니 합치는게 

    더 메모리 소모가 적을 것이라는 확신이 있을때 진행한다.

    

    ⓐ 경우

    

    부서 테이블(300BYTE)        사원 테이블(60*1,000,000BYTE)

    --------------------       ---------------------------------------------------------  + -----------

    부서번호 부서명 주소       사원번호 사원명  직급    급여   입사일 부서번호     부서명

      PK                                  PK                                               FK 

    -----------------------------------------------------------------------------------   + -----------

    10byte  10byte  10byte      10byte  10byte  10byte  10byte 10byte  10byte

    

          10개 행                             1,000,000개 행

          

    >> 조회 결과물

    -------------------------------------

    부서명   사원명     직급     급여

    -------------------------------------

    

    

    부서 테이블과 사원테이블을 JOIN했을 때 크기

    

    SELECT A.부서명,B.사원명,B.직급,B.급여

    FROM 부서 A JOIN 사원 B

    ON A.부서번호 = B.부서번호;

    => 60,000,300BYTE

    

    역정규화를 한 부서별 사원 테이블만 읽어올 경우

    (즉, 사원테이블에 부서명 컬럼을 추가한 경우)

    =>70,000,000BYTE

    

    

    ⓑ 경우 → 역정규화를 수행하는 것이 바람직한 상황

    

    부서 테이블(30*500,000)BYTE   사원 테이블(60*1,000,000)BYTE

      --------------------       ---------------------------------------------------------  + -----------

    부서번호 부서명 주소       사원번호 사원명  직급    급여   입사일 부서번호     부서명

      PK                                  PK                                               FK 

    -----------------------------------------------------------------------------------   + -----------

    10byte  10byte  10byte      10byte  10byte  10byte  10byte 10byte  10byte

    

          500,000개 행                             1,000,000개 행

          

    >> 조회 결과물

    -------------------------------------

    부서명   사원명     직급     급여

    -------------------------------------

    

    

    부서 테이블과 사원테이블을 JOIN했을 때 크기

    

    SELECT A.부서명,B.사원명,B.직급,B.급여

    FROM 부서 A JOIN 사원 B

    ON A.부서번호 = B.부서번호;

    => 75,000,000BYTE

    

    역정규화를 한 부서별 사원 테이블만 읽어올 경우

    (즉, 사원테이블에 부서명 컬럼을 추가한 경우)

    =>70,000,000BYTE

    

    부모테이블과 자식테이블 크기가 비슷할 때 사용될 가능성이 높다.

반응형

+ Recent posts

티스토리툴바