05. 5차시 수업

01.cpp - 369게임

푸는 방법 : 미리 테이블을 만들어 놓습니다.

1) 3,6,9가 포함되는 수

자릿수	3,6,9가 포함되는 수 : A[i]	안포함되는 수 : B[i]
0	0	1 (=>이건 그냥 계산을 위한 수. 0자리수는 없음.)
1	3	7
2	10*A[1] + 3*B[1] = 51	B[1]*7 = 49
...
n	10*A[n-1] + 3*B[n-1]	B[n-1]*7

{3x

6x

9x} ->여기까지 3개는 x에 10개씩 들어갈 수 있습니다.

{x3

x6

x9}->여기까지 3개는 x에 3,6,9를 제외한 7개씩 들어갈 수 있습니다.

n번째 항에서는 이미 369가 포함되어있는 수에는 0~9까지의 총 10개의 숫자 중 아무거나 들어가도 상관 없습니다.

369가 포함 안되어있으면 3,6,9를 포함 시켜줘야겠지요. 3,6,9 3개의 숫자만 들어가야 합니다.

그래도 포함되지 않은 수는 바로 윗줄에서 포함시킨거 말고 다른거 모두를 세면 되겠죠. 3,6,9를 제외한 7개의 수가 들어갑니다.

! 잠깐 ! 자릿수 2이면 10부터 99까지 90개만 올 수 있는거 아닌가요? => 아닙니다. 여기선 01도 자릿수 2로 친답니다.

2) 3,6,9가 들어가지 않은 것 중 3,6,9의 배수

자릿수	(3으로 나눴을 때)나머지 0 : C[i]	나머지 1 : D[i]	나머지 2 : E[i]
1	1 = {0}	3 = {1, 4, 7}	3 = {2, 5, 8}
2	1*1 + 3*3 + 3*3 = 19	1*3 + 3*1 + 3*3 = 15	1*3 + 3*1 + 3*3 = 15
...
n	C[n-1]*C[1] + D[n-1]*E[1] + E[n-1]*D[1]	C[n-1]*D[1] + D[n-1]*C[1] + E[n-1]*E[1]	C[n-1]*E[1] + E[n-1]*C[1] + D[n-1]*D[1]

(자릿수 2에 있는 모든것을 합하면 1)에 자릿수 2에 있는 B[2]의 개수와 똑같습니다.)

경우의 수. = 각 두개를 결합(곱)한거.

(1)나머지 0인거

C[n-1], C[1] : 나머지가 0인거 + 나머지가 0인거 = 나머지가 0인거

D[n-1], E[1] : 나머지가 1인거 + 나머지가 2인거 = 나머지가 3인거 => 나머지가 0인거

E[n-1], D[1] : 나머지가 2인거 + 나머지가 1인거 = 나머지가 3인거 => 나머지가 0인거

(2)나머지 1인거

C[n-1], D[1] : 나머지가 0인거 + 나머지가 1인거 = 나머지가 1인거

D[n-1], C[1] : 나머지가 1인거 + 나머지가 0인거 = 나머지가 1인거

E[n-1], E[1] : 나머지가 2인거 + 나머지가 2인거 = 나머지가 4인거 => 나머지가 1인거

(3)나머지 2인거

C[n-1], E[1] : 나머지가 0인거 + 나머지가 2인거 = 나머지가 2인거

E[n-1], C[1] : 나머지가 2인거 + 나머지가 0인거 = 나머지가 2인거

D[n-1], D[1] : 나머지가 1인거 + 나머지가 1인거 = 나머지가 2인거

3)이제 세는법

1~12345을 구한다고 하면

0xxxx

10xxx

11xxx

12xxx

120xx

121xx

122xx =>여기까지 나눠서 각각의 경우마다 부분합과 남은 길이를 이용해서 계산한다. 왜냐구?

123xx => 여기부턴 안세도 다 나와 있찌. (12345-12300+1 : 전체 12345개 중 앞의 12300개 빼고 12300 하나 더해주면 그게 123xx에서의 박수 횟수.)

*코드는 제가 짠 코드가 아닙니다.

#include <stdio.h>
#include <string.h>
 
#define N 100002
#define R 20150523
 
int inc[N], not_inc[N], r0[N], r1[N], ten_r[N];
char first[N], second[N], temp[N];
 
void including_369_array(int *inc, int *not_inc, const unsigned int len){
    //parameters
    //int *inc: 369가 포함된 숫자의 갯수들을 저장하는 배열
    //int *not_inc: 369가 포함되지 않은 숫자의 갯수들을 저장하는 배열
 
    unsigned int i;
 
    not_inc[0] = 1;
    inc[0] = 0;
 
    for(i = 1; i <= len; ++i){
        not_inc[i] = (not_inc[i-1] * 7) % R;
        inc[i] = ((inc[i-1] * 10) + (not_inc[i-1] * 3)) % R;
    }
}
 
void remainder_array(int *r0, int *r1, const unsigned int len){
    //parameters
    //int *r0: 3으로 나눈 나머지가 0인 숫자의 갯수 배열
    //int *r1: 3으로 나눈 나머지가 1또는 2인 숫자의 갯수 배열
    
    unsigned int i;
 
    r0[0] = 1;
    for(i = 1; i <= len; ++i){
        r0[i] = (r0[i-1] + r1[i-1] * 6) % R;
        r1[i] = ((r0[i-1] * 3) + (r1[i-1] * 4)) % R;
    }
}
 
void tens_remainder(int *ten_r, const unsigned int len){
    //parameters
    //int *ten_r: 10의 제곱수들을 R로 나눈 나머지들의 배열
 
    unsigned int i;
 
    ten_r[0] = 1;
 
    for(i = 1; i <= len; ++i){
        ten_r[i] = (ten_r[i-1] * 10) % R;
    }
}
 
int has_369(char ch){
    return (ch == '3' || ch == '6' || ch == '9');
}
 
int calc_claps(const unsigned int sum, const unsigned int len){
  if(sum == 0)
      return inc[len] + r0[len] - 1;
  else if(sum % 3 == 0)
      return inc[len] + r0[len];
  else
      return inc[len] + r1[len]; 
}
 
int claps(char *num, const unsigned int len){
    unsigned int i, j, k;
    int to = len - 1;
    int sum = 0; //경우의 수 마다 부분합을 저장
    int temp = 0;
    int ret = 0; //최종 결과 값
 
    //최초로 3,6,9가 나오는 위치를 구함
    for(i = 0; i < len; ++i){
        if(has_369(num[i])){
            to = i;
            break;
        }
    }
 
    //각각의 경우마다 부분합과 남은 길이를 이용해 횟수 계산 후 누적
    for(i = 0; i <= to; ++i){
        for(j = 0; j < num[i]-'0'; j++){
              if(len - i - 1 > 0)
                  ret = (ret + calc_claps(sum, len - i - 1) % R) % R;
              else
                  ret = (has_369(j + '0') || (sum % 3 == 0 && sum != 0)) ? ((ret + 1) % R) : ret;
            ++sum;
        }
    }
 
    //3, 6, 9가 맨 끝에 있거나 합이 3의 배수면 자기 자신에 대한 박수 회수 를 더함
    if(len - i == 0)
        ret = (has_369(j + '0') || (sum % 3 == 0 && sum != 0)) ? ((ret + 1) % R) : ret;
 
 
    //마지막으로 남은 박수 횟수를 계산
    for(i = len-1; i > to; --i){
      temp += ((num[i]-'0') * ten_r[len - 1 - i]) % R;
      temp %= R;
    }
 
    if(to != len - 1)
      ++temp;
 
    return ((ret % R) + (temp % R)) % R;
}
 
int main(){
    unsigned int first_len, second_len;
    unsigned int first_ans, second_ans;
 
    scanf("%s", first);
    first_len = strlen(first);
    first[first_len-1]--; //자기자신을 포함하기 위해
 
    scanf("%s", second);
    second_len = strlen(second);
 
    including_369_array(inc, not_inc, second_len);
    remainder_array(r0, r1, second_len);
    tens_remainder(ten_r, second_len);
 
    first_ans = claps(first, first_len);
    second_ans = claps(second, second_len);
 
    printf("%d", (second_ans - first_ans + R) % R);
}

02.cpp - KMP알고리즘 마무리

전체 문자열에서 주어진 부분 문자열(pattern)을 한칸씩 앞으로 간다고 생각한다.

Pi를 이용해서 반복된 부분을 찾고 찾던 문자가 일치하거나 패턴의 맨 앞으로 돌아올 때까지 반복.

패턴의 인덱스가 끝까지 갔을 때 끝.

Pi : 맨처음 0으로 초기화. j가 0이면서 일치하지 않으면 j대입. j가 0이 아니면서 일치하지 않으면 j=pi[j-1]일치하면  +1해서 대입.

Pi에 대해선 04. 4차시 수업을 보면 아주아주 자세히 설명 되어있어요~

*코드는 제가 짠 코드가 아닙니다.

#include <stdio.h>
#include <string.h>
 
void generate_pi(char *p, int *pi){
    int m = strlen(p);
    int i, j = 0;
    pi[0] = 0;
 
    for(i = 1; i < m; ++i){
        while(j > 0 && p[i] != p[j])
            j = pi[j-1];
        if(p[i] == p[j])
            ++j;
        pi[i] = j;
    }
}
 
int kmp(char *text, char *pattern, int *pi){
    int n = strlen(text);
    int m = strlen(pattern);
    int i, j = 0;
 
    for(int i = 0; i < n; ++i){
        while(j > 0 && text[i] != pattern[j])
            j = pi[j - 1];
        if(text[i] == pattern[j]){
            if(j == m - 1)
                return (i - m + 1);
            else
                j++;
        }
    }
}
 
int main(){
    char text[] = "ABCXABCDABXABCDABCDABCY";
    char pattern[] = "ABCDABCY";
    int pi[100];
    int i;
 
    generate_pi(pattern, pi);
 
    for(i = 0; i < strlen(pattern); ++i){
        printf("%d", pi[i]);
    }
 
    printf("\n%d", kmp(text, pattern, pi));
}

03.cpp - 바이러스

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

바이러스 문제입니다. 

*코드 출처 : http://yukari-ko.blogspot.kr/2014/07/7575.html*

#include <stdio.h>
 
int program[101][1001],length[1001];
int match[1001],reverse[1001],reverse_match[1001];
int N,K,L;
void pi(int *q,int *p){
    int i=1,j=0;
    for(;i<=K;){
        if(!j||p[i]==p[j]){
            j++;i++;q[i]=j;
        }
        else j=q[j];
    }
}
int kmp(int *q,int *a,int *p,int len){
    int i,j;
    for(i=j=1;i<=len;){
        if(!j||a[i]==p[j]){
            i++;j++;
        }
        else j=q[j];
        if(j==K+1) return 1;
    }
    return 0;
}
int main(){
    int i,j,k,t,q,s;
  
    scanf("%d%d",&N,&K);
    for(i=0;i<N;i++){
        scanf("%d",&length[i]);
        for(j=1;j<=length[i];scanf("%d",&program[i][j++]));
    }
    for(i=1;program[0][i+K];i++){
        pi(match,&program[0][i-1]);
        for(j=1;j<=K;j++){
            reverse[j]=program[0][i+K-j];
        }
        pi(reverse_match,reverse);
        for(s=j=1;j<N;j++){
            if(kmp(match,program[j],&program[0][i-1],length[j])) s++;
            else if(kmp(reverse_match,program[j],reverse,length[j])) s++;
            else break;
        }
        if(s==N){
            puts("YES");
            return 0;
        }
    }
    puts("NO");
}

04.cpp - Stack

push, pop, peek가 있는 간단한 stack구현입니다. 

설명은 >> http://sunrinnote.tistory.com/37

//stack
#include <stdio.h>
int arr[1000];
int N;
int idx=-1;
 
void push(int a){
    if(a>=1000){
        printf("memory over. return.\n");
        return;
    }
    arr[++idx]=a;
    return;
}
 
int pop(){
    if(idx==-1){
        printf("underflow. return -1.\n");
        return -1;
    }
    return arr[idx--];
}
 
int peek(){
    if(idx==-1){
        printf("no data. return -1.\n");
        return -1;
    }
    return arr[idx];
}
 
int main(){
    while(1){
        int a;
        printf("1push 2pop 3peek 4exit >> ");
        scanf("%d", &a);
        switch(a){
            case 1: scanf("%d", &a); push(a); break;
            case 2: printf("pop:%d\n",pop()); break;
            case 3: printf("peek:%d\n",peek()); break;
            case 4: return 0;
            default: return 0;
        }
    }
}

05.cpp - 쇠막대기

/* https://www.acmicpc.net/problem/10799 */
#include <stdio.h>
#include <string.h>
char arr[100001];
int cnt=0;
int idx=-1;
int len;
int main(){
    scanf("%s", arr);
    len=strlen(arr);
    for(int i=0; i<len; ++i){
        if(arr[i]=='('){
            ++idx;
        }
        else{
            if(arr[i-1]==')'){
                --idx;
                cnt+=1;
            }
            else{
                cnt+=idx--;
            }
        }
    }
    printf("%d", cnt);
    return 0;
}

*idx는 현재 쇠막대기가 (겹쳐진 개수-1)이라고 생각하시면 됩니다.

'('를 차곡차곡 쌓다가 ')'를 만나면 두가지 경우로 나눕니다.

첫번째, 바로 전에 있는 문자가 ')'일 경우 : 쇠막대기가 끝나는 부분. idx--를 해주고 cnt+=1을 해줍니다. (쇠막대기를 2번 자르면 3개로 쪼개지죠.)

두번째, 바로 전에 있는 문자가 '('일 경우 : 레이저. 겹쳐진 개수를 더해주고 쌓은 '('가 쇠막대기가 아니기 때문에 idx--를 해줍니다.

마지막엔 cnt를 출력해줍니다.

06.cpp - 후위표기법 (0~9까지만 계산됨)

원래는 중위표기법이죠.

2 + 3 = 5

이 중위표기법에는 치명적인 단점이 있는데, 바로 연산자의 우선순위를 생각해야한다는 것입니다.

2 + 3 * 5 = (앞에서부터하면)25 / (우선순위를 생각하면)17. 다른답이 나옵니다.

이를 방지하기 위해서 후위표기법이 나옵니다. 컴퓨터도 이 후위표기법을 사용한다고 하네요.

후위표기법은 앞에 두 숫자를 놓고 그 뒤에 연산자를 놓으면 된답니다.

2 3 +  (답은 5) 처럼요.

그러면 아까 2 + 3 * 5 를 후위표기법으로 나타내볼까요?

첫번째 방법 -> 2 (3 5 *) +

두번째 방법 -> 3 5 * 2 +

구현하는 방법은 스택을 사용합니다.

숫자가 들어오면 스택에 넣어주고

연산자가 들어오면 앞에 있는 두 숫자에 그 연산자를 적용해서 나온 값을 다시 스택에 넣어줍니다. (pop 2번 => 연산해서 => push 1번)

#include <stdio.h>
#include <string.h>
char arr[100000];
int stack[100000];
int idx=-1;
 
void push(int value){
    stack[++idx] = value;
}
int pop(){
    return stack[idx--];
}
 
int main(){
    scanf("%s", arr);
    int len=strlen(arr);
    int first, second;//순서가 있어야 하는 뺄셈과 나눗셈에 사용
    for(int i=0; i<len; ++i){
        if(arr[i]-48>=0){//숫자면
            push(arr[i]-48);
            
        }
        else{
            if(arr[i]=='+'){
                push(pop()+pop());
            }
            else if(arr[i]=='-'){
                second=pop();
                first=pop();
                push(first-second);
            }
            else if(arr[i]=='*'){
                push(pop()*pop());
            }
            else{
                second=pop();
                first=pop();
                push(first/second);
            }
        }
    }
    printf("%d", pop());
}

07.cpp - 후위표기법 - (두자리수, 세자리수, 네자리수,... 상관 없이 모든 int형 범위 내의 수에 대한 계산.)

띄어쓰기로 숫자와 숫자, 숫자와 연산자 사이를 구분합니다.

06.cpp와 달라진 부분은 코드 14줄~20줄과 23,24줄입니다.

특히 16번째 코드는 숫자가 연달아 나올 때 앞서 push했던 수를 다시 pop해서 10을 곱하고 새로운 수를 더해주는 내용입니다.

calc에서 리턴하는 값 : 26번째줄에서 for문을 돌 때 이미 계산한 부분은 건너 뛰어야해서 건너 뛰어야 할 i를 리턴해줍니다.

더 많은 수를 계산하고 싶다면 long long int로 바꾸면 되겠죠?

#include <stdio.h>
#include <string.h>
char arr[100000];
int stack[100000];
int idx=-1;
 
void push(int value){
    stack[++idx] = value;
}
int pop(){
    return stack[idx--];
}
 
int calc(int a){
    if(arr[a+1]!=' '){
        push(pop()*10+arr[a+1]-'0');
        return 1+calc(a+1);
    }
    else return 0;
}
 
int main(){
    fgets(arr, 100000, stdin);
    int len=strlen(arr)-1;//개행문자도 입력으로 치기 때문에 -1.
    int first, second;//순서가 있어야 하는 뺄셈과 나눗셈에 사용
    for(int i=0; i<len; ++i){
        if(arr[i]==' ') continue;
        if(arr[i]-'0'>=0){//숫자면
            push(arr[i]-'0');
            i+=calc(i);
        }
        else{
            if(arr[i]=='+'){
                push(pop()+pop());
            }
            else if(arr[i]=='-'){
                second=pop();
                first=pop();
                push(first-second);
            }
            else if(arr[i]=='*'){
                push(pop()*pop());
            }
            else{
                second=pop();
                first=pop();
                push(first/second);
            }
        }
    }
    printf("%d\n", pop());
}