반응형

1.1 문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라. 다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가?

//풀이(C++) 

bool isUnique(string* str){

if(str->length() > 256) 

return false;

bool check[256];

for(int i=0;i<str->length();i++){

int index=str->at(i);


if(check[index]==true)

return false;

else

check[index]=true;

}


return true;

}

sol) 문자열이 ASCII코드라고 가정할 때 문자는 총 256개이다. 즉 문자열의 길이가 256 이상이면 중복이 존재할 것이다. 이후 boolean형 배열을 정의해 문자열을 탐색하여 기존에 있던 문자면 false를 반환하도록 한다.


1.2 널 문자로 끝나는 문자열을 뒤집는 reverse(char* str)함수를 C나 C++로 구현하라.

//reverse함수 구현

//문자열 str포인터를 인자로 받아 역순으로 값을 바꿈

//풀이(C++)

void reverse(char *str)

{

char *end = str;

char temp;

if(str)

{

while(*end)

{

++end;

}

--end; //마지막 null값 제외

while(str<end)

{

temp=*str;

*str++ = *end;

*end-- = temp;

}

}

}

쉬운 문제이므로 pass!


1.3 문자열 두 개를 입력으로 받아 그중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라.

        //순열 = 문자열 종류와 길이는 같고 배열된 순서는 다를 수 있음

//풀이(JAVA)

/*

* 가장 먼저 문자열의 길이를 비교한다.

* 이후 정렬을 통해 문자열 종류를 비교한다.

*/

public boolean isCheck(String str1, String str2)

{

if(str1.length() != str2.length())

return false;

return sort(str1).equals(sort(str2));

}

public String sort(String str)

{

char[] result=str.toCharArray();

java.util.Arrays.sort(result);

return new String(result);

} 


1.4 주어진 문자열 내의 모든 공백을 '%20'으로 바꾸는 메소드를 작성하라. 문자열 끝에 추가로 필요한 문자들을 더할 수 있는 충분한 공간이 있다고 가정하라. 그리고 공백을 포함하는 문자열의 길이도 함 주어진다고 가정하라.

Ex) 입력 : "Mr John Smith"

     출력 : "Mr%20John%20Smith"

//풀이(C++)

void convert(char str[], int len)

{

int blank=0; //공백 개수

int strlen=len;

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

if(str[i]==' ')

++blank;

}

strlen+=(blank*2); //2자리 증가

str[strlen]='\0';


for(int i=len-1;i>=0;i--){

if(str[i]==' '){

str[strlen-1]='0';

str[strlen-2]='2';

str[strlen-3]='%';

strlen-=3;

}

else

{

str[strlen-1]=str[i];

strlen--;

}

}

cout<<str;

}


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2167] 2차원배열의 합 구하기  (0) 2018.09.07
[BOJ 11048] 다리놓기  (0) 2018.09.07
깊이 우선 탐색(DFS, Depth First Search)  (0) 2018.08.08
[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
반응형

 깊이 우선 탐색이라는 알고리즘에 대해 알아보려고 합니다. 일반적으로 DFS 알고리즘을 구현할때는 스택을 이용하고, 트리 혹은 그래프 같은 자료구조에서 데이터를 탐색할 때 사용하는 알고리즘 입니다. 나중에 알아볼 너비 우선 탐색이라는 비슷한 알고리즘이 있는데, 다음 게시물에서 다루도록 하겠습니다.

 깊이 우선 탐색 알고리즘은 한마디로 더 나아갈 길이 보이지 않을 만큼 깊게 들어가는 특징을 지니고 있으며, 더 깊게 들어갈 경로가 존재하지 않으면 이전의 위치로 돌아온 뒤 다른 경로를 선택해서 움직입니다.


(그래프를 첨부하고 싶은데 어떻게 첨부하는지 모르겠네요 ㅠㅠ)


연습장 꺼내신 후 직접 그려보시면 이해가 더 빠르실거에요...ㅎㅎㅎ


그래프를 간략하게 노드들만 나타내보도록 하겠습니다 각 노드간은 연결되어 있는 상태라고 가정할게요. 즉 각 Vertex들을 잇는 Edge는 모두 연결되어 있는 상태입니다!


 

 

 1

 

 

 

 2

 

 

3 

 

 4

 

5 

6 

 

7 

 

 

 8

 

 


 시작 Vertex(노드)는 1에서 부터 시작하겠습니다. 앞에서 언급했듯이 계속 탐색한 후 길이 없으면 되돌아 간 후 다른 경로를 선택하는 알고리즘 입니다.

 방문 순서는 1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7 로 진행되겠죠. 그렇다면 여기서 이론은 끝! DFS 알고리즘을 직접 구현해보도록 하겠습니다. 먼저 코드로 구현하기 전에 Vertex간 관계를 나타내기 위해 인접행렬을 사용하겠습니다. 인접행렬은 그래프에서 각 정점의 인접관계를 나타내는 행렬입니다. (간단한 내용이니 궁금하시면 검색해보세요!)


※ 인접행렬


0 

1

1 

0 

0 

 0

0 

0 

1

0 

0 

1 

1 

0 

0 

0 

1

0 

0 

0 

0 

1 

1 

0 

0

1 

0 

0 

0 

0 

0 

1 

0

1 

0 

0 

0 

0 

0 

1 

0

0 

1 

0 

0 

0 

0 

1 

0

0 

1 

0 

0 

0 

0 

1 

0

0 

0 

1 

1 

1 

1 

0 



C++로 구현한 단순 DFS 알고리즘 입니다.

#include <iostream>


int vertex; //정점 갯수

int map[30][30], visit[30]; // map - 상호간 연결을 나타냄 

// visit - 방문 여부

void DFS(int t_vertex);

using namespace std;


int main()

{

int sVertex; // Start Vertex

int v1, v2;


cin>>vertex>>sVertex;


while(true)

{

cin>>v1>>v2;

if(v1 == -1 && v2 == -1) //무한루프 방지

break;

map[v1][v2] = map[v2][v1] = 1; // vertex 상호간 연결

}

DFS(sVertex);


return 0;

}


void DFS(int t_vertex)

{

visit[t_vertex] = 1; // visit vertex

for(int i=1; i<=vertex; i++){

if(map[t_vertex][i] == 1 && !visit[i])

{

cout<<t_vertex<<"에서 "<<i<<"로 이동합니다"<<endl;

DFS(i);

}

}

} 

















반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 11048] 다리놓기  (0) 2018.09.07
코딩인터뷰  (0) 2018.08.10
[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
반응형

문제

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


문제

꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 koong(n)이라고 할 때,

n < 2 :                         1
n = 2 :                         2
n = 3 :                         4
n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)

이다.

여러분도 꿍 피보나치를 구해보아라.

 

입력

입력의 첫번째 줄을 테스트케이스의 개수 t (0 < t < 69)가 주어진다. 다음 t줄에는 몇번째 피보나치를 구해야하는지를 나타내는 n(0 ≤ n ≤ 67)이 주어진다.

출력

각 테스트케이스에 대해, 각 줄에 꿍 피보나치값을 출력하라.

예제 입력 1 

8
0
1
2
3
4
5
30
67

예제 출력 1 

1
1
2
4
8
15
201061985
7057305768232953720



















이 문제를 틀렸다면 이유는 알고리즘적 문제가 아니라 자료형 선언일 것이다. 아마 int형으로 선언하지 않았을까 한다. DP문제로 메모리제이션 기법을 사용하여 풀이 하였다.

문제 난이도가 쉬우므로 자세한 설명은 생략하기로 한다. 피보나치 형식대로 함수를 구현해 주면 된다.


소스코드

//

//  main.cpp

//  DP

//

//  Created by seungwoo on 2018. 06. 28

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

//


#include <iostream>

#include <algorithm>


using namespace std;


long long fibo(int n);


int main()

{

int T,n;

cin>>T;

while(T>0)

{

T--;

cin>>n;

cout<<fibo(n)<<endl;

}

return 0;

}

long long fibo(int n)

{

static long long dp[68]={0};

if(dp[n]!=0) return dp[n];

if(n==0 || n==1) return 1;

else if(n==2) return 2;

else if(n==3) return 4;

return dp[n]=fibo(n-1) + fibo(n-2) + fibo(n-3) + fibo(n-4);

} 



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

코딩인터뷰  (0) 2018.08.10
깊이 우선 탐색(DFS, Depth First Search)  (0) 2018.08.08
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
반응형

TABLE = BOOK

BOOK_NO 

NAME 

EDITION 

 100

JAVA 

1 

 100

JAVA 

2 

 101

C++ 

3 


이와 같은 데이터가 있다고 가정할 경우 책번호와 책이름을 조회하되 같은 책이 있을 경우 EDITION이 높은 것을 조회하고자 한다.


많은 방법이 있겠지만 한가지 방법을 소개한다.


SELECT BOOK_NO, NAME, EDITION

FROM BOOK

WHERE 1=1

AND (BOOK_NO, NAME, EDITION) IN (SELECT BOOK_NO, NAME, MAX(EDITION) AS EDITION FROM BOOK GROUP BY BOOK_NO, NAME)


이와 같은 방법으로 WHERE 조건에 괄호와 IN 그리고 서브쿼리를 사용하여 조건을 부여할 수 있다.

반응형
저작자표시

'Database' 카테고리의 다른 글

[SQL 튜닝] 2. 옵티마이저(Optimizer)  (0) 2019.04.22
[SQL 튜닝] 1. 실행계획(Execution plan)  (2) 2019.04.22
무결성 (Integrity)  (0) 2018.01.12
JOIN (조인)  (0) 2018.01.12
오라클 SQL Developer 2018.01.09  (0) 2018.01.09
반응형

문제

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



문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생들이 구금되어있다.

그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. 같은 방식으로 n번의 라운드를 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5≤n≤100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

예제 입력 1 

2
5
100

예제 출력 1 

2
10







   



문제 풀이

테스트 케이스는 5이상 100이하이다.

즉 방이 최소 5개 존재한다는 것이다. 처음에 문제를 이해할 때는 짝수 번째는 2의 배수 홀수 번째는 3의 배수로 풀이하다가 잘못된 것을 알고

2번째는 2의 배수, 3번째는 3의 배수 4번째는 4의 배수, n번째는 n의 배수임을 깨닫게 되었다.


n = 5인 경우 (1 = open / 0 = close)


  1 

1 

1 

1 

1 

 1

0 

1 

0 

1 

 1

0 

0 

0

1 

 1

0 

0 

1 

1 

 1

0 

0 

1 

0


위 표를 보면 규칙이 각 라운드 마다 열거나 닫는 방 번호는 라운드의 배수임을 알 수 있다. 

즉, 방번호 % 라운드 == 0 인 경우 열린 문은 닫고, 닫힌 문은 열면 되는 간단한 문제이다.

if문을 사용해서 방번호 %라운드 ==0 조건을 사용해도 되지만 조건을 조금 더 간단하게 하는 방법이 있다.

해당 라운드의 배수인 방이 열려있으면 닫고 닫혀있으면 여는 방법이다.

충분히 생각해보고 소스코드를 참고하자


소스코드

//

//  main.cpp

//  Algorithm

//

//  Created by sw on 2018. 6. 25..

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

//


#include <iostream>

#include <algorithm>


using namespace std;

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

    // insert code here...

    int testcase, room;

    cin>>testcase;

    while(testcase>0){

        testcase--;

        cin>>room;

        int dp[101] = {0};  //dp 저장 변수(테스트케이스마다 초기화를 위해 while문 안에 선언)

        for(int i=1;i<=room;i++){

            for(int j=1; i*j<=room; j++){

                if(dp[i*j]==1) dp[i*j]=0;

                else dp[i*j]=1;

            }

        }

        for(int i=1; i<=room; i++){

            dp[0] += dp[i]; //dp[0]를 count로 사용

                            //for문을 사용하고 싶지 않다면 위쪽 if문에서 dp[0]값을 더하거나 빼주면 됨.

        }

        cout<<dp[0]<<endl;  //문이 열린 갯수 출력

    }

    return 0;

} 



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

깊이 우선 탐색(DFS, Depth First Search)  (0) 2018.08.08
[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28
반응형

문제

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


        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 숫자는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1줄까지 숫자 삼각형이 주어진다.

출력

첫째 줄에는 최대가 되는 합을 출력한다.

입력

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


출력

30


먼저 N을 입력받고 이차원배열에 숫자삼각형을 입력한다.

그리고 나서 윗층과 누적할 이차원배열이 필요하다. 크기는 숫자삼각형 입력받은 것과 동일하며 

두 번째줄부터 윗줄과 더하고 그 누적값을 가지고 있어야한다.

맨 왼쪽일 경우, 맨 오른쪽일 경우, 중간에 있을 경우가 있다.

여기서 맨 왼쪽, 오른쪽은 상관없지만 중간에 있을 경우 가장 큰 것을 찾아야 한다.

그러면 중간 값은 자기보다 위 줄의 좌, 우에서 큰 값을 찾아야한다.

즉 자신의 위치에서 대각선 , 우의 최대값을 가져오면 되는 문제이다.


소스

//

//  main.cpp

//  DP

//

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

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

//


#include <iostream>

#include <algorithm>

using namespace std;


int dp[502][502];

int a[502][502];

int main()

{

    int n;

    

    cin>>n;

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=i; j++)

            cin>>a[i][j];

    }

    

    for(int i=1; i<=n; i++)

    {

        for(int j=1; j<=i; j++)

            dp[i][j] = a[i][j] +  max(dp[i-1][j],dp[i-1][j-1]);

    }

    int res = 0;

    for (int i = 1; i <= n; i++)

        res = max(res, dp[n][i]);

    cout<<res;

    return 0;

}


 




반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1149] RGB거리  (0) 2018.03.29
[백준 1003] 피보나치 함수  (0) 2018.03.28
[백준 9095] 1,2,3 더하기  (0) 2018.03.27
반응형

문제

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



RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.


예제 입력

3
26 40 83
49 60 57
13 89 99


예제 출력

96


사실 알고리즘적 요소보다 문제 이해가 어려웠다.

문제 이해만 빠르고 확실하게 한다면 어려움없이 풀 수 있는 문제다.


만약 빨간집으로 시작했다면 2번째 집은 초록 or 파랑 이여만 한다.

즉 dp[0][1] (빨간색으로 칠했을때) = min(dp[1][i-1], dp[2][i-1])(전 집에서 초록색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + r_cost (현재 i를 빨간색으로 칠했을때의 비용)

dp[1][1] (초록색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + g_cost (현재 i를 초록색으로 칠했을때의 비용)

dp[2][1] (파란색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 초록색으로 칠했을 떄의 최소비용 중 최소값) + b_cost (현재 i를 파란색으로 칠했을때의 비용)


와 같은 식으로 진행되는 것을 알 수 있다.


이와 같은 식으로 모든 비용을 구한 이후 최소값을 출력해주는 알고리즘이다.



소스


//

//  main.cpp

//  DP

//

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

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

//


#include <iostream>

#include <algorithm>


using namespace std;


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

    int house;

    int result;

    int cost[3][1001]={0};

    cin>>house;

    for(int i=1; i<=house; i++){

        int r_cost, g_cost, b_cost;

        cin>>r_cost>>g_cost>>b_cost;

        cost[0][i] = min(cost[1][i-1] , cost[2][i-1]) + r_cost;

        cost[1][i] = min(cost[0][i-1] , cost[2][i-1]) + g_cost;

        cost[2][i] = min(cost[0][i-1] , cost[1][i-1]) + b_cost;

    }

    result = min(cost[0][house], min(cost[1][house],cost[2][house]));

    cout<<result;

    return 0;

} 


반응형

'Algorithm' 카테고리의 다른 글

[백준 9507] Generations of Tribbles  (0) 2018.06.26
[백준 6359] 만취한 상범  (0) 2018.06.25
[백준 1932] 숫자삼각형  (0) 2018.03.30
[백준 1003] 피보나치 함수  (0) 2018.03.28
[백준 9095] 1,2,3 더하기  (0) 2018.03.27
반응형

문제

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

티스토리툴바