How We Coding

180301 튜터링 - 큐(Queue)

Tutoring/17-2 Data Structure (Winter)2018. 3. 1. 23:21

< 180301 >




- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조


- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐), 

            스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)



- (선형)큐 구현하기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int data[MAX];
    int front;
    int rear;
} Queue;
 
void init(Queue * q) {
    q->front = 0;
    q->rear = 0;
}
 
int isEmpty(Queue * q) {
    return (q->front == q->rear);
}
 
void enqueue(Queue * q, int data) {
    q->data[(q->rear)++] = data;
}
 
int peek(Queue * q) {
    if (isEmpty(q)) {
        printf("(peek)큐가 비어있습니다. : ");
        return -11111;
    }
    return q->data[q->front];
}
 
void dequeue(Queue * q) {
    if (!isEmpty(q)) {
        (q->front)++;
    }
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
}
 
cs


>> 이런식으로 구현할 수 있다.

>> 하지만 이렇게 될 경우, 배열의 앞 공간에 낭비가 발생한다.



- 원형 큐 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
   int data[MAX];
   int front;
   int rear;
} Queue;
 
void init(Queue * q) {
   q->front = 0;
   q->rear = 0;
}
 
int isEmpty(Queue * q) {
   return (q->front == q->rear);
}
 
int isFull(Queue * q) {
   return (q->rear+1)%MAX == q->front;
}
 
void enqueue(Queue * q, int data) {
   if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
   else {
      q->rear = (q->rear + 1) % MAX;
      q->data[q->rear] = data;
   }
}
 
int peek(Queue * q) {
   if (isEmpty(q)) {
      printf("(peek)큐가 비어있습니다. : ");
      return -11111;
   }
   return q->data[(q->front+1) % MAX];
}
 
void dequeue(Queue * q) {
   if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
   else {
      q->front = (q->front + 1) % MAX;
   }
}
 
int main()
{
   Queue q;
   init(&q);
 
   enqueue(&q, 1);
   enqueue(&q, 9);
   enqueue(&q, 9);
   enqueue(&q, 8);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
   
   printf("%d\n", peek(&q));
 

}
cs


>> 사용한 공간의 낭비를 막을 수 있다.

>> 빈 상태와 포화상태를 구분하기 위해 한 칸을 비워둔다. 

>> 21-23 :  포화상태에 대한 코드이다. 모듈러 연산을 통해 마지막 인덱스 다음 인덱스를 0으로 만들 수 있다.



### 연결리스트를 이용한 큐를 만들어보자. 

>> head 포인터를 front 로, tail 포인터를 rear 로 두고 만들면 된다.



### 덱

>> 앞으로도 넣고 뒤로더 넣을 수 있으며, 앞에서도 꺼내고 뒤에서도 꺼낼 수 있다.

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 트리(Tree)  (0) 2018.03.02
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

180301 튜터링 - 스택의 응용 (수정:180514)

Tutoring/17-2 Data Structure (Winter)2018. 3. 1. 00:35

< 숙제 Review >


1. 올바른 괄호 문자열인지 판단하는 함수 ("(", "{", "[" 로 구성)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#define MAX 100
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s);
int isEmpty(Stack *s);
int isFull(Stack *s);
void push(Stack *s, char data);
char peek(Stack *s);
void pop(Stack *s);
 
int isRightBraket(char *bk)
{
    int idx;
    Stack s;
    init(&s);
 
    for(idx=0; bk[idx]; idx++) {
        char ch = bk[idx];
        if(ch == '{' || ch == '(' || ch == '[') push(&s, ch);
        else {
            char tmp;
            if(isEmpty(&s)) return 0;
            tmp = peek(&s); pop(&s);
            if((tmp == '{' && ch != '}') || (tmp == '[' && ch != ']') || (tmp == '(' && ch != ')'))
                return 0;
        }
    }
    return isEmpty(&s);
}
 
int main()
{
    char str[]="[(){}[(){}]]";
    isRightBraket(str) ? puts("True") : puts("False");
    return 0;
}
cs


>> 28-29 : 여는 괄호에 대한 짝이 안맞으면 0을 리턴.

>> 30 : 검사가 끝나면 스택은 비워있어야 하므로..!!


>> 26번 라인잉 추가되었다. 이 코드가 없으면 닫는 괄호로 먼저 시작하는 코드들에 대해 에러가 발생한다. (수정:180514)



2. 중위식을 후위식으로 만드는 함수 (http://boj.kr/1918)


- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.


- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 push.

>> 스택의 맨 위 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력

>> ( 가중치에 상관없이 스택에 쌓는다. 

>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#define MAX 100
 
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
void infixToPostfix(char *t)
{
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('A' <= ch && ch <= 'Z') printf("%c", ch);
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        pop(&s);
    }
}
 
int main()
{
    char s[100];
    scanf("%s", s);
    infixToPostfix(s);
    puts("");
    return 0;
}
 
cs


>> 이전 튜터링(스택) 때 서술한 알고리즘을 그대로 구현한 코드다

>> A+(B*C)*D*E+F   —>    ABC*D*E*+F+  이렇게 결과가 나온다.



3. 중위식을 후위식으로 만든 후 그 후위식을 계산하는 함수


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
 
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
char* infixToPostfix(char *t)
{
    char *res = (char*)malloc(sizeof(char)*100);
    int idx=0;
 
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('0' <= ch && ch <= '9') { res[idx++]=ch; printf("%c", ch); }
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    res[idx++]=op;
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    res[idx++] = peek(&s);
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        res[idx++] = peek(&s);
        pop(&s);
    }
    res[idx] = 0;
    return res;
}
 
int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = peek(&s); pop(&s);
            int op1 = peek(&s); pop(&s);
            switch(eq[i]) {
                case '+': push(&s, op1+op2); break;
                case '-': push(&s, op1-op2); break;
                case '*': push(&s, op1*op2); break;
                case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    char s[100], *t;
    scanf("%s", s);
    printf("%s = ", s);
    t=infixToPostfix(s);
    printf(" = %d\n", exp(t));
    free(t);
 
    return 0;
}
 
cs


>> input : 8/2-3+3*2

>> output : 8/2-3+3*2 = 82/3-32*+ = 7


>> infixToPostfix() 에서 출력을 할 때마다 해당 문자를 배열에 저장하고,

     이전에 구현해놓은 exp() 를 그대로 사용하면 된다..

     여기서 후위식을 저장할 배열을 왜 동적할당을 했는지 생각해보자..!! (지역변수 관련)



4. 미로탐색

...

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 트리(Tree)  (0) 2018.03.02
180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

[14889] 스타트와 링크

BOJ/SWEA2018. 2. 28. 14:14


- [14889] 스타트와 링크 (http://boj.kr/14889)


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
 
int n, ans=1e9;
int g[21][21];
int start[11], link[11];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int abs(int k)
{
    return k > 0 ? k : -k;
}
 
void go(int k, int ti, int ki)
{
    if(ti == n/2 || ki == n/2) {
        int S=0, L=0;
        if(ti == n/2) {
            while(k)
                link[ki++] = k--;
        }
        if(ki == n/2) {
            while(k)
                start[ti++] = k--;
        }
        
        for(int i=0; i<ki; i++) {
            for(int j=i+1; j<ki; j++) {
                S += (g[start[i]][start[j]] + g[start[j]][start[i]]);
                L += (g[link[i]][link[j]] + g[link[j]][link[i]]);
            }
        }
        ans = min(ans, abs(S-L));
        return ;
    }
 
    start[ti] = k;
    go(k-1, ti+1, ki);
 
    link[ki] = k;
    go(k-1, ti, ki+1);
}
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    go(n, 0, 0); 
    printf("%d\n", ans);
    return 0;
}
 
cs


>> 한명씩 스타트에 넣고, 링크에 넣다가 둘중에 한 팀이 절반이 차면 나며지를 다른 팀에 마저 채운다. 그리고 계산!!

'BOJ > SWEA' 카테고리의 다른 글

[14890] 경사로  (0) 2018.03.06
[14888] 연산자 끼워넣기  (0) 2018.02.27

배열에서 배열의 크기 이상의 인덱스를 사용하게 되면...

Language/C2018. 2. 27. 23:42

< 예제코드 >


- 7라인에서 n 에 20을 대입한다면...?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
   int i, n;
   scanf("%d", &n);
   int *arr;
   arr = (int *)malloc(sizeof(int) * n);
 
   printf("%d\n", sizeof(arr));
   arr[1] = 1;
   arr[198] = 2;
   printf("(%d, %d)\n", arr[1], arr[198]);
 
   for(i=0; i<200; i++)
       printf("%d: %d\n", i, arr[i]);
 
   free(arr);
 
   return 0;
}
cs


>> 7 라인에서 n에 20을 입력한다.

>> 하지만 놀랍게도(?) 14 라인의 실행결과는 (1, 2) 이다. segmentation fault 가 안뜬다.

>> 그래서 16-17의 실행결과를 확인해보니.. 값을 할당하지 않은 곳은 0으로 초기화가 되어 있고, 인덱스가 1인 곳에는 1, 인덱스가 198인 곳에는 2가 저장되어있다.

     그래서 검색을 해봤다.


- 배열의 크기를 넘어서 사용하게 되면...

>> 아래 블로그에서 원하는 답변을 얻을 수 있었다.


- http://blog.naver.com/PostView.nhn?blogId=tipsware&logNo=221054714926



>> 결론만 몇가지 말하면, 문법상 오류는 아니며, 예외처리는 개발자가 알아서 해야한다고 한다.

>> 또한, 이렇게 코딩을 해도 문제가 없다고 넘어가면, 돌아오는 것은 버그 라고 한다..



- 이 의문은 같이 스터디를 하는 동생의 질문에서 시작되었다.

- 블로그에서 관련내용을 다시 잘 정리한 것 같다.


- http://www.crocus.co.kr/1171?category=278489 

'Language > C' 카테고리의 다른 글

비트 연산을 이용한 정수의 산술연산 (분석은 아직..)  (0) 2018.06.04
scanf() 에서 공백을 포함한 문자열 입력받기  (0) 2018.04.05
printf() 서식문자 %g  (0) 2018.03.07

[14888] 연산자 끼워넣기

BOJ/SWEA2018. 2. 27. 20:54

[14888] 연산자 끼워넣기 (http://boj.kr/14888)



1) Brute Force 풀이


< 소스코드 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
 
int a[15], op[4];
 
int ansN = 1e9;
int ansX = -1e9;
int set[15];
 
void go(int n, int ps, int mi, int mu, int dv)
{
    if(n == 1) {
        int ans = a[1];
        for(int i=2; set[i]; i++) {
            if(set[i] == 1) ans += a[i];
            else if(set[i] == 2) ans -= a[i];
            else if(set[i] == 3) ans *= a[i];
            else {
                if(ans < 0) {
                    ans *= -1;
                    ans /= a[i];
                    ans *= -1;
                }
                else
                    ans /= a[i];
            }
        }
        if(ans > ansX) ansX = ans;
        if(ans < ansN) ansN = ans;
    }
 
    if(ps) { set[n]=1; go(n-1, ps-1, mi, mu, dv); }
    if(mi) { set[n]=2; go(n-1, ps, mi-1, mu, dv); }
    if(mu) { set[n]=3; go(n-1, ps, mi, mu-1, dv); }
    if(dv) { set[n]=4; go(n-1, ps, mi, mu, dv-1); }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    go(n, op[0], op[1], op[2], op[3]);
    printf("%d\n%d\n", ansX, ansN);
    return 0;
}
 
cs


>> 연산자 순서의 모든 경우의 수를 저장해 놓고, 그 순서에 맞게 계산을 한 다음 최대값과 최소값을 구한다.



2) DP 풀이


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) { 
            tmp *= -1;
            tmp /= a[n];
            tmp *= -1;
        }
        else
            tmp /= a[n];
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
 
cs


>> 맨처음 풀이에 대해 잘못된 점을 파악한 다음(나눗셈에 대한 처리), 코드를 수정하니 AC 를 받았다.

>> 근데 다시생각해보면 왜 DP 로 가능한지 모르겠다...



< 마지막 테케가 안나오는 소스코드 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
 
int a[15], op[4];
int d[15][15][15][15][15];
int e[15][15][15][15][15];
const int INF=1e9;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int min(int a, int b)
{
    return a < b ? a : b;
}   
 
int maxV(int n, int ps, int mi, int mu, int dv)
{
    int ans = -INF;
    if(n == 1) return a[n];
    if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv];
 
    if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = maxV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = max(ans, tmp);
    }
    return d[n][ps][mi][mu][dv] = ans;
}
 
int minV(int n, int ps, int mi, int mu, int dv)
{
    int ans = INF;
    if(n == 1) return a[n];
    if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv];
 
    if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]);
    if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]);
    if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]);
    if(dv) {
        int tmp = minV(n-1, ps, mi, mu, dv-1);
        if(tmp < 0) tmp *= -1;
        tmp /= a[n];
        tmp *= -1;
        ans = min(ans, tmp);
    }
    return e[n][ps][mi][mu][dv] = ans;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<4; i++)
        scanf("%d", op+i);
 
    for(int i=0; i<15; i++)
        for(int j=0; j<15; j++)
            for(int k=0; k<15; k++)
                for(int l=0; l<15; l++)
                    for(int m=0; m<15; m++)
                        d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1;
 
    printf("%d\n", maxV(n, op[0], op[1], op[2], op[3]));
    printf("%d\n", minV(n, op[0], op[1], op[2], op[3]));
    return 0;
}
cs


>> 마지막 테케의 최소값이 -36이 나온다..... -24 라는데...ㅜ

>> 가만 생각해보니 DP 가 아닌 것 같다. 모든 경우의 수를 생각해서 풀면 될 것 같은 생각이 든다. (brute force)

>> 나눗셈에 대한 처리를 잘못했다.

'BOJ > SWEA' 카테고리의 다른 글

[14890] 경사로  (0) 2018.03.06
[14889] 스타트와 링크  (0) 2018.02.28

<3-1> 파일 입출력

Language/Python2018. 2. 23. 16:17

동영상 강의 : http://pythonkim.tistory.com/notice/77


# Day_03_01_file.py


- 파일에는 두가지 종류의 파일이 있다. 우리가 읽을 수 있는 파일(텍스트 파일)과 읽을 수 없는 파일(바이너리 피알)..!!


- 우선 Data 폴더를 만들고 텍스트 파일 하나를 만들자.


김인육, 사랑의 물리학


질량의 크기는 부피와 비례하지 않는다


제비꽃같이 조그마한 그 계집애가

꽃잎같이 하늘거리는 그 계집애가

지구보다 더 큰 질량으로 나를 끌어당긴다.

순간, 나는

뉴턴의 사과처럼

사정없이 그녀에게로 굴러 떨어졌다

쿵 소리를 내며, 쿵쿵 소리를 내며


심장이

하늘에서 땅까지 아찔한 진자운동을 계속하였다

첫사랑이었다.


>> 위의 시를 poem.txt 파일에 복붙하쟈.



- open() , close()


1
2
3
4
5
6
7
8
def read_1(filename):
    f = open(filename, 'r')
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_1(filename)
cs


>> 7 : 경로설정을 잘 해줘야한다. 현재 디렉토리에 있는 Data 폴더에 있는 poem.txt 라는 파일.

>> 프로젝트 폴더가 현재 디렉토리라고 여겨진다.


>> 2 : open() 에서의 옵션 'r' >> 파일을 읽겠다는 뜻.

>> 4 : open() 을 하고 볼일을 다 봤으면 항상 close() 를 해줘야한다.


- 경로에는 절대경로와 상대결로가 있다.

>> 절대경로 : 경로의 풀네임

>> 상대경로 : 현재 경로 기준으로 판단. // . 은 현재 디렉토리, // .. 은 상위 디렉토리

>> 일반적으로 상대경로를 많이 사용한다고 한다.


- 경로를 잘 설정했는데도 에러가 발생했다면 인코딩 문제를 의심해볼 수 있다.


1
f = open(filename, 'r', encoding='utf-8')
cs


>> 세번째 옵션으로 인코딩 옵션을 설정한다.

>> 현재 전 세계적으로 텍스트파일에 대한 표준은 utf-8 이라고 한다.

>> html 에서 기본적으로 이것을 사용한다고 한다.



- readlines()


1
2
3
4
5
6
7
8
9
10
11
def read_1(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    lines = f.readlines()
    print(lines)
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_1(filename)
cs


>> 4, 5 라인 추가. // readline 과 혼동하지 말자.

>> 실행결과

['김인육, 사랑의 물리학\n', '\n', '질량의 크기는 부피와 비례하지 않는다\n', '\n', '제비꽃같이 조그마한 그 계집애가\n', '꽃잎같이 하늘거리는 그 계집애가\n', '지구보다 더 큰 질량으로 나를 끌어당긴다.\n', '순간, 나는\n', '뉴턴의 사과처럼\n', '사정없이 그녀에게로 굴러 떨어졌다\n', '쿵 소리를 내며, 쿵쿵 소리를 내며\n', '\n', '심장이\n', '하늘에서 땅까지 아찔한 진자운동을 계속하였다\n', '첫사랑이었다.']



- 따로따로 출력을 해보자

1
2
3
4
5
6
7
8
9
10
11
12
13
def read_1(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    lines = f.readlines()
 
    for line in lines:
        print(line)
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_1(filename)
cs

>> 6, 7 라인의 변경

>> 실행결과


김인육, 사랑의 물리학




질량의 크기는 부피와 비례하지 않는다




제비꽃같이 조그마한 그 계집애가


꽃잎같이 하늘거리는 그 계집애가


지구보다 더 큰 질량으로 나를 끌어당긴다.


순간, 나는


뉴턴의 사과처럼


사정없이 그녀에게로 굴러 떨어졌다


쿵 소리를 내며, 쿵쿵 소리를 내며




심장이


하늘에서 땅까지 아찔한 진자운동을 계속하였다


첫사랑이었다. 


>> 줄바꿈이 심하다. 기본적으로 문자열 내부에 개행을 포함하며, print() 또한 개행을 포함하기 때문이다.



- 7 라인의 print() 에서 end='' 옵션을 추가해보쟈


1
2
3
4
5
6
7
8
9
10
11
12
13
def read_1(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    lines = f.readlines()
 
    for line in lines:
        print(line, end='')
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_1(filename)
cs


>> 실행결과

김인육, 사랑의 물리학


질량의 크기는 부피와 비례하지 않는다


제비꽃같이 조그마한 그 계집애가

꽃잎같이 하늘거리는 그 계집애가

지구보다 더 큰 질량으로 나를 끌어당긴다.

순간, 나는

뉴턴의 사과처럼

사정없이 그녀에게로 굴러 떨어졌다

쿵 소리를 내며, 쿵쿵 소리를 내며


심장이

하늘에서 땅까지 아찔한 진자운동을 계속하였다

첫사랑이었다. 


>> 하지만 파일을 읽어온 목적이 화면에 출력하는 것은 아니므로, 위와 같은 행위는 바람직하지 않다고 하신다.

>> 출력은 눈으로 확인용일 뿐, 중요하진 않다.



- strip() 사용하기


>> 개행문자가 필요한지 아닌지는 상황에 따라 다를 것이다.

>> 여기서는 필요 없어보인다. 그래서 strip() 을 사용

>> strip() : 문자열 양 끝에 있는 공백을 제거


1
2
3
4
5
6
7
8
9
10
11
12
13
def read_1(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    lines = f.readlines()
 
    for line in lines:
        print(line.strip())
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_1(filename)
cs


>> 7 라인과 같이 사용한다.



- strip() 사용법


1
2
3
4
5
temp = '\t\t\n\n   apple koong   \n\n\t\t'
print('[{}]'.format(temp))
 
temp = temp.strip()
print('[{}]'.format(temp))
cs


>> 2 의 실행결과

[


   apple koong   


]


>> 5 의 실행결과

[apple koong]


>> 문자열 양 끝의 모든 공백들이 제거되었다.




- 파일읽기 2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def read_2(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    while True:
        line = f.readline()
        # if len(line) == 0: break; # EOF
        if not line: break;
        print(line.strip())
 
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_2(filename)
cs


>> 5 : readline() 함수는 한줄씩 읽어온다.

>> 6 : EOF 를 만나면 line 의 길이는 0이 된다. 하지만 7 라인과 같은 코딩을 선호한다고 한다.

>> 7 : Python 에서는 비어있는 것에 대해 false 로 판단한다.



- 파일읽기 3


1
2
3
4
5
6
7
8
9
10
11
def read_3(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    for line in f:
        print(line.strip())
 
    f.close()
 
 
filename = 'Data/poem.txt'
read_3(filename)
cs


>> 4 : for in 문에서 in 다음에는 이터러블한 것이라면 올 수 있다. 이처럼 파일도 올 수 있다.

>> EOF 를 만나면 알아서 끝난다.

>> 가장 심플한 코드.



- 파일읽기 4 : with 구문 사용


1
2
3
4
5
6
7
8
9
10
11
def read_4(filename):
    with open(filename, 'r', encoding='utf-8') as f:
 
        for line in f:
            print(line.strip())
 
        # f.close()
 
 
filename = 'Data/poem.txt'
read_4(filename)
cs


>> 2 : with 구문 사용, as f: f 라는 별칭까지 준다.

>> 7 : close() 가 필요가 없다. with 구문의 장점(자동으로 호출이 된다.)



- 파일읽기 5

- 일반적으로 파일을 다루는 코드 (리스트에 넣어서 처리)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 일반적으로 파일을 다루는 코드.
# 리스트에 넣어서 처리
def read_5(filename):
    lines = []
    with open(filename, 'r', encoding='utf-8') as f:
        for line in f:
            # print(line.strip())
            lines.append(line.strip())
 
    return lines
 
 
filename = 'Data/poem.txt'
lines = read_5(filename)
cs


>>



- readlines() 가 존재하는 이유.


1
2
3
4
5
6
7
8
9
10
11
12
def read_readlines(filename):
    f = open(filename, 'r', encoding='utf-8')
 
    lines = f.readlines()
 
    f.close()
    return ''.join(lines)
 
 
filename = 'Data/poem.txt'
text_all = read_readlines(filename)
print(text_all)
cs


>> join() 을 호출하기 위해 존재한다고 한다.

>> read_readlines() 가 리턴한 데이터의 타입은 문자열..!!

>> join() 의 역할은 리스트 안에 들어있는 문자열들을 한번에 결합

>> 하나의 변수로 파일의 내용을 다루고자 할 때 readlines() 를 사용한다.


>> 실행결과

김인육, 사랑의 물리학


질량의 크기는 부피와 비례하지 않는다


제비꽃같이 조그마한 그 계집애가

꽃잎같이 하늘거리는 그 계집애가

지구보다 더 큰 질량으로 나를 끌어당긴다.

순간, 나는

뉴턴의 사과처럼

사정없이 그녀에게로 굴러 떨어졌다

쿵 소리를 내며, 쿵쿵 소리를 내며


심장이

하늘에서 땅까지 아찔한 진자운동을 계속하였다

첫사랑이었다. 



cf) 


1
return '***'.join(lines)
cs


>> 실행결과


김인육, 사랑의 물리학

***

***질량의 크기는 부피와 비례하지 않는다

***

***제비꽃같이 조그마한 그 계집애가

***꽃잎같이 하늘거리는 그 계집애가

***지구보다 더 큰 질량으로 나를 끌어당긴다.

***순간, 나는

***뉴턴의 사과처럼

***사정없이 그녀에게로 굴러 떨어졌다

***쿵 소리를 내며, 쿵쿵 소리를 내며

***

***심장이

***하늘에서 땅까지 아찔한 진자운동을 계속하였다

***첫사랑이었다. 




- split() 과 join()


1
2
3
4
5
6
a = 'AA,BB,CC'
b = a.split(',')
print(b)            # ['AA', 'BB', 'CC']
 
c = ''.join(b)
print(c)            # AABBCC
cs


>> 3, 6 의 실행결과는 주석으로 확인.

>> spit() 의 결과는 리스트



- 파일 쓰기


1
2
3
4
5
6
7
8
def write():
    f = open('Data/write.txt', 'w', encoding='utf-8')
    f.write('Hello ')
    f.write('Python')
    f.close()
 
 
write()
cs



>> Data 폴더에 write.txt 파일이 생성되고, 'Hello Python' 문자열이 저장되어 있다.



- command 키 누른 상태로 마우스를 open() 위에 가져다 놓기 (win 에서는 ctrl)

>> open() 에 대한 설명을 볼 수 있다.



- 기상청 날씨정보를 파싱 후 파일에 저장


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import requests
import re
 
url = 'http://www.weather.go.kr/weather/forecast/mid-term-rss3.jsp?stnId=108'
recvd = requests.get(url)
 
locations = re.findall(r'<location wl_ver="3">.+?</location>', recvd.text, re.DOTALL)
 
f = open('Data/kma.csv', 'w', encoding='utf-8')
 
def findData():
    for loc in locations:
        prov = re.findall(r'<province>(.+)</province>', loc)
        city = re.findall(r'<city>(.+)</city>', loc)
        data = re.findall(r'<data>(.+)</data>', loc, re.DOTALL)
 
        for datum in data:
            mode = re.findall(r'<mode>(.+?)</mode>', datum)
            tmEf = re.findall(r'<tmEf>(.+?)</tmEf>', datum)
            wf   = re.findall(r'<wf>(.+?)</wf>', datum)
            tmn  = re.findall(r'<tmn>(.+?)</tmn>', datum)
            tmx  = re.findall(r'<tmx>(.+?)</tmx>', datum)
            reli = re.findall(r'<reliability>(.+?)</reliability>', datum)
 
            row = '{},{},{},{},{},{},{},{}'.format(prov[0], city[0], mode[0], tmEf[0], wf[0], tmn[0], tmx[0], reli[0])
            print(row)
            f.write(row)
            f.write('\n')   # 개행문자는 자동으로 처리되지 않으므로.
 
 
findData()
f.close()
cs


'Language > Python' 카테고리의 다른 글

<3-3> JSON  (0) 2018.03.05
<3-2> Set 과 Dictionary  (0) 2018.03.02
<2-3> 기상청의 전국 날씨정보 파싱, 외부 모듈 추가  (0) 2018.02.22
<2-2> 리스트, 튜플  (0) 2018.02.15
<2-1> 제어문과 반복문의 연결고리  (0) 2018.02.06

[10942] 팰린드롬?

BOJ/DP2018. 2. 22. 23:49

http://boj.kr/10942


DP - basic


d[i][j] = i~j 까지가 팰린드롬인지.


< 소스코드 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <string.h>
 
int p[2001];
int d[2001][2001];
 
int isP(int s, int e)
{
    int i;
    if(s >= e) return 1;
    if(d[s][e] != -1) return d[s][e];
    if(p[s] != p[e]) return 0;
    return d[s][e] = isP(s+1, e-1);
}
 
int main()
{
    int i, j, n, m;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        scanf("%d", p+i);
 
    memset(d, -1, sizeof(d));
 
    scanf("%d", &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", isP(a, b));
    }
 
    return 0;
}
cs


>> 모든 경우를 다 구해놓고 하려다가 시간만 쓰고, 머리만 쓴거 같다.

>> 쿼리마다 필요한걸 구하면서 그때 구한걸 저장해(메모이제이션) 놓으면 된다..



< 바텀업 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
int n;
int a[2000];
bool d[2000][2000];
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n; i++) {
        d[i][i] = true;
    }
    for (int i=0; i<n-1; i++) {
        if (a[i] == a[i+1]) {
            d[i][i+1] = true;
        }
    }
    for (int k=3; k<=n; k++) {
        for (int i=0; i<=n-k; i++) {
            int j = i+k-1;
            if (a[i] == a[j] && d[i+1][j-1]) {
                d[i][j] = true;
            }
        }
    }
    int m;
    scanf("%d",&m);
    while (m--) {
        int s, e;
        scanf("%d %d",&s,&e);
        printf("%d\n",d[s-1][e-1]);
    }
    return 0;
}
cs


>> 과거 AC 받은 코드인데, 백준님 코드 같다.. 내스타일의 코드는 아니므로...


>> 길이가 1인 부분수열은 반드시 팰린드롬이다.

>> 길이가 2인 부분수열은 두 수가 같을때만 팰린드롬이다.

>> d[i][j] 가 팰린드롬이려면 a[i] == a[j] 이고 d[i+1][j-1] 이 팰린드롬이여야 한다.

'BOJ > DP' 카테고리의 다른 글

[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[11048] 이동하기  (0) 2018.02.18

[1890] 점프

BOJ/DP2018. 2. 22. 22:05

http://boj.kr/1890


DP - basic


D[i][j] : (1, 1)에서 (i, j) 까지 오는 방법의 수


< 소스코드 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
 
int n;
int g[101][101];
long long d[101][101];
 
long long jump(int r, int c)
{
    int k = g[r][c];
    long long ret = 0;
    if(r == n && c == n) return 1;
    if(r > n || c > n || k == 0) return 0;
    if(d[r][c] != -1) return d[r][c];
 
    ret += jump(r+k, c);
    ret += jump(r, c+k);
    return d[r][c] = ret;
}
 
 
int main()
{
    int i, j;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=n; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = 1LL*(-1);
        }
    }
    printf("%lld\n", jump(1, 1));
    return 0;
}
 
cs


>> 10 : ret 를 int 로 선언해서 81%에서 틀렸었다....



< 과거 소스코드 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
 
int g[101][101];
long long d[101][101];
 
long long go(int i, int j)
{
    int k;
    if(i<1 || j<1) return 0;
    if(i==1 && j==1) return 1;
    if(d[i][j]) return d[i][j];
 
    for(k=0; k<j; k++)
        if(k+g[i][k] == j)
            d[i][j] += go(i, k);
 
    for(k=0; k<i; k++)
        if(k+g[k][j] == i)
            d[i][j] += go(k, j);
 
    return d[i][j];
}
 
int main()
{
    int n, i, j;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            scanf("%d", &g[i][j]);
 
    printf("%lld\n", go(n, n));;
 
    return 0;
}
 
 
cs


>> 역시 재귀로 풀었지만, go(n, n) 으로 시작해서 불필요하게 머리를 더 쓴거 같다..

'BOJ > DP' 카테고리의 다른 글

[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[11048] 이동하기  (0) 2018.02.18
[9184] 신나는 함수 실행  (0) 2018.02.16

<3> namespace (네임스페이스)

Language/C++2018. 2. 22. 18:55

출처 : http://kks227.blog.me/60204955407



(1) namespace, using, ::


- C++ 에서 새로 도입된 개념인 이름공간(namespace)

- namespace 라는 키워드를 사용한다.

- namespace 네임스페이스명 { ... } 형태를 취한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
 
namespace ns {
    int n = 5;
    double f = 3.3;
    char c = 'G';
}
 
int k = 10;
 
int main()
{
    // n = 3; // Error
    ns::n = 3;
    printf("%d\n", ns::n);          // 3
 
    int n = 5;
    printf("%d %d\n", n, ns::n);    // 5 3
 
    using ns::f;
    using ns::c;
    //using ns::n;
    printf("%lf %c\n", f, c);       // 3.300000 G
 
    using namespace ns;    // directive
    
    printf("%d %lf %c\n", n, f, c); // 5 3.300000 G
 
    int k = 3;
    printf("%d %d\n", k, ::k);      // 3 10
}
cs


>> 3 : ns 라는 이름공간 생성

>> 13 : n 은 메인함수에서 선언되지 않은 변수 이므로 에러

>> 18 : main() 의 n 과 ns 라는 이름공간의 n

>> 20, 21 : 이름 공간의 변수를 이름공간을 생략하고 사용할 수 있다. (using 키워드 사용)

>> 22 : 이미 같은 이름의 변수가 지역적으로 선언되어 있으면, 컴파일 에러 발생

error: target of using declaration conflicts with declaration already in scope


>> 25 : 이름공간 ns 에 있는 변수들을 ns:: 없이 사용 가능.

     다만 이미 선언되어 있는 변수의 경우 무시되는 듯 하다. 27에서 n 의 값은 main() 스코프의 n.

>> 30 : ::k 는 전역번수 k  



(2) 여러개의 네임스페이스


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
 
namespace ns1 {
    int n = 11;    
}
 
namespace ns2 {
    int n = 22;
}
 
namespace ns3 {
    int n = 33;
    namespace ns4 {
        int n = 44;
    }
}
 
int main()
{
    printf("%d %d\n", ns1::n, ns2::n);  // 11 22
 
    /*
    using ns1::n;
    using ns2::n;
    printf("%d\n", n);    // error!!
    */
 
    {
        using namespace ns1;
        printf("%d\n", n);              // 11
    }
    
    {
        using namespace ns2;
        printf("%d\n", n);              // 22
    }
 
    printf("%d %d\n", ns3::n, ns3::ns4::n);     // 33 44
 
    return 0;
}








cs


>> 26 : n 이 어디소속인지 알 수 없으므로 에러.

>> 29 ~ 37 : 이런식으로 스코프를 중괄호를 만들어 주고, 그 안에서 독자적으로 특정 네임스페이스를 사용하는 방법도 있다고 한다.

>> 12 ~ 17, 39 : 네임스페이스 안에 네임스페이스



(3) 이름없는 네임스페이스, 네임스페이스 안의 함수


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
 
namespace {
    int n=4;
}
 
// n = 8; error!!
 
int func() { return n; }
 
namespace ns {
    void func();
}
 
 
int main()
{
    printf("%d\n", n);          // 4
 
    n = 8;
    printf("%d\n", n);          // 8
 
    printf("%d\n", func());     // 8
 
    ns::func();        // called ns::func()
 
    using ns::func; // not using ns::func();
    func();
 
    return 0;
}
 
namespace ns {
    void func() {
        puts("called ns::func()");
    }
}
 
cs


>> 3 : 이름없는 네임스페이스 선언

>> 18 : ::와 같은 연산자 없이 바로 사용 가능.

>> 7 : 하지만 전역 지역에서는 사용 불가.

>> 9 : 이와 같이 어떤 지역 스코프 안에서 사용 가능.


>> 12, 25 : 변수를 선언하고 사용하는것과 비슷하다.

>> 27 : using 키워드를 사용할 때는 using 네임스페이스명::함수이름; 의 형태로 써야한다. 

>>        using ns::func(); 는 잘못된 형태이다.

>> 33 : 프로토타입만 선언 후 나중에 따로 정의를 해도 된다.






'Language > C++' 카테고리의 다른 글

<2> 레퍼런스 (reference)  (0) 2018.02.12
<1> C++ 에서 확장된 기능  (0) 2018.02.12

<2-3> 기상청의 전국 날씨정보 파싱, 외부 모듈 추가

Language/Python2018. 2. 22. 00:43

동영상 강의 : http://pythonkim.tistory.com/notice/77


Day_02_03_kma.py


- import requests 에서 requests 는 외부 모듈.


- PyCharm 에서 외부 모듈 추가하기.


>>  preferences (Mac) - Project - Project Interpreter - "+ 버튼" 클릭 - "requests" 검색 - Install Package 


1
2
3
4
5
6
import requests
import re
 
url = 'http://www.naver.com'
recvd = requests.get(url)
print(recvd)    # <Response [200]>
cs



>> www.naver.com 으로부터 데이터를 성공적으로 가져온 상태. (200)



1
print(recvd.text)
cs


>> Chrome 에서 페이지 소스보기 통해 확인할 수 있는 html 소스가 출력된다.



### 기상청의 전국 날씨정보 파싱


http://www.kma.go.kr/index.jsp 에서 날씨누리 바로가기 - 생활과 산업 - 서비스 - RSS 로 이동




 RSS란?


 RSS(Really Simple Syndication, Rich Site Summary)란 블로그처럼 컨텐츠 업데이트가   

 자주 일어나는 웹사이트에서, 업데이트된 정보를 쉽게 구독자들에게 제공하기 위해 XML을 

 기초로 만들어진 데이터 형식입니다. RSS서비스를 이용하면 업데이트된 정보를 찾기 위해 

 홈페이지에 일일이 방문하지 않아도 업데이트 될 때마다 빠르고 편리하게 확인할 수 

 있습니다. 





- 전국의 중기예보 RSS 클릭 후 URL 클립보드에 복사.


1
2
3
4
url = 'http://www.weather.go.kr/weather/forecast/mid-term-rss3.jsp?stnId=108'
recvd = requests.get(url)
print(recvd)    # <Response [200]>
print(recvd.text)
cs


>> 크롤링 이라고 한다. (python 이 편리한 이유)



-


This XML file does not appear to have any style information associated with it. The document tree is shown below.


>> html 은 style 정보가 포함되어 있다.

>> xml 은 순수하게 데이터만 들어가있다.

>> 데이터 전송 포맷의 두가지 (xml, json)


- http://www.weather.go.kr/weather/forecast/mid-term-rss3.jsp?stnId=108 에서 날씨 데이터 찾아보기.


>> <item> - <description> - <body> 안에서 확인가능


>> xml 이든 html 이든 여는태그가 있으면 닫는태그가 있다...!!


1
2
3
4
5
6
url = 'http://www.weather.go.kr/weather/forecast/mid-term-rss3.jsp?stnId=108'
recvd = requests.get(url)
 
tmp = re.findall(r'<province>서울ㆍ인천ㆍ경기도</province>', recvd.text)
print(tmp)  # ['<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>']
print(len(tmp)) # 4
cs



- 모든 <province> 태그 가져오기 (정규표현식 이용)


1
2
3
prov = re.findall(r'<province>.+</province>', recvd.text)
print(prov) # ['<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>', '<province>서울ㆍ인천ㆍ경기도</province>', '<province>강원도영서</province>', '<province>강원도영서</province>', '<province>강원도영동</province>', '<province>대전ㆍ세종ㆍ충청남도</province>', '<province>대전ㆍ세종ㆍ충청남도</province>', '<province>대전ㆍ세종ㆍ충청남도</province>', '<province>충청북도</province>', '<province>광주ㆍ전라남도</province>', '<province>광주ㆍ전라남도</province>', '<province>광주ㆍ전라남도</province>', '<province>전라북도</province>', '<province>전라북도</province>', '<province>부산ㆍ울산ㆍ경상남도</province>', '<province>부산ㆍ울산ㆍ경상남도</province>', '<province>부산ㆍ울산ㆍ경상남도</province>', '<province>대구ㆍ경상북도</province>', '<province>대구ㆍ경상북도</province>', '<province>대구ㆍ경상북도</province>', '<province>제주도</province>', '<province>제주도</province>']
print(len(prov))    # 24
cs



>> <province>.+</province> 패턴은 

     <province> 로 시작하고 하나 이상의 문자가 있고, </province> 로 끝나는 패턴



# 문제

# 전체 location 가져오기


- 상위 데이터를 가져온 다음, 하위 데이터를 분리하는 방식으로 진행해야 한다.!!

- 태그를 타이핑 하지 말고 긁어오쟈 (블럭지정 후 복붙)


1
2
location = re.findall(r'<location wl_ver="3">.+</location>', recvd.text)
print(len(location))
cs


>> 실행 결과는 0 이다.

>> 위의 예제의 경우 여는 태그와 닫는 태그 사이에 한줄에 하나의 데이터만 있지만, 이 예제의 경우 데이터가 여러줄에 걸쳐서 존재한다.

>> 옵션을 추가해서 해결할 수 있다.


1
2
location = re.findall(r'<location wl_ver="3">.+</location>', recvd.text, re.DOTALL)
print(len(location))
cs


>> re.DOTALL 옵션 추가. 내가 찾고자 하는 패턴이 여러줄에 걸쳐있을 때 사용. 

>> 정확히는 개행 문자를 무시해준다.

>> 하지만 실행결과는 1.

>> 가장 짧은 패턴과, 가장 긴 패턴 중 가장 긴 패턴을 디폴트로 찾는다. (Greedy 방식)



>> 데이터가 위와 같이 있는 경우, 첫번째 한줄이 가장 짧은 패턴, 모든 줄을 포함 시킨 것이 가장 긴 패턴이 된다.



- non-greedy 방식으로 하려면 '?' 하나를 추가하면 된다.


1
2
locations = re.findall(r'<location wl_ver="3">.+?</location>', recvd.text, re.DOTALL)
print(len(locations))
cs


>> .+? 라고 적음. ? 는 작은 녀석을 먼저 찾았을 때 멈추게 한다.

>> 실행결과는 24


- 이젠 24개의 데이터에서 원하는 데이터를 다시 또 찾으면 된다.


1
2
3
def printLoc():
    for loc in locations:
        print(loc)
cs


>> 24개의 location 확인 가능



# 문제

# province 를 찾아서 출력 


1
2
3
4
def printProvince():
    for loc in locations:
        prov = re.findall(r'<province>.+</province>', loc)
        print(prov)
cs


>> 24 개의 <province> 데이터를 출력한다.

>> 한줄안에 있으므로 re.DOTALL 없어도 된다.


>> 실행결과


['<province>서울ㆍ인천ㆍ경기도</province>']

['<province>서울ㆍ인천ㆍ경기도</province>']

['<province>서울ㆍ인천ㆍ경기도</province>']

['<province>서울ㆍ인천ㆍ경기도</province>']

['<province>강원도영서</province>']

['<province>강원도영서</province>']

['<province>강원도영동</province>']

['<province>대전ㆍ세종ㆍ충청남도</province>']

['<province>대전ㆍ세종ㆍ충청남도</province>']

['<province>대전ㆍ세종ㆍ충청남도</province>']

['<province>충청북도</province>']

['<province>광주ㆍ전라남도</province>']

['<province>광주ㆍ전라남도</province>']

['<province>광주ㆍ전라남도</province>']

['<province>전라북도</province>']

['<province>전라북도</province>']

['<province>부산ㆍ울산ㆍ경상남도</province>']

['<province>부산ㆍ울산ㆍ경상남도</province>']

['<province>부산ㆍ울산ㆍ경상남도</province>']

['<province>대구ㆍ경상북도</province>']

['<province>대구ㆍ경상북도</province>']

['<province>대구ㆍ경상북도</province>']

['<province>제주도</province>']

['<province>제주도</province>']



>> 여기서 우리가 필요한 것은 <province> 태그 안의 데이터이므로 , 태그 이름까지는 없어도 된다..!!


1
2
3
4
def printProvinceData():
    for loc in locations:
        prov = re.findall(r'<province>(.+)</province>', loc)
        print(prov)
cs


>> 괄호를 치면 된다.!!

>> 실행결과 


['서울ㆍ인천ㆍ경기도']

['서울ㆍ인천ㆍ경기도']

['서울ㆍ인천ㆍ경기도']

['서울ㆍ인천ㆍ경기도']

['강원도영서']

['강원도영서']

['강원도영동']

['대전ㆍ세종ㆍ충청남도']

['대전ㆍ세종ㆍ충청남도']

['대전ㆍ세종ㆍ충청남도']

['충청북도']

['광주ㆍ전라남도']

['광주ㆍ전라남도']

['광주ㆍ전라남도']

['전라북도']

['전라북도']

['부산ㆍ울산ㆍ경상남도']

['부산ㆍ울산ㆍ경상남도']

['부산ㆍ울산ㆍ경상남도']

['대구ㆍ경상북도']

['대구ㆍ경상북도']

['대구ㆍ경상북도']

['제주도']

['제주도']




# Data 찾기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Data 찾기
 
def findData():
    for loc in locations:
        prov = re.findall(r'<province>(.+)</province>', loc)
        city = re.findall(r'<city>(.+)</city>', loc)
        data = re.findall(r'<data>(.+)</data>', loc, re.DOTALL)
 
        #print(prov[0], prov)
        #print(city[0])
        # print(data)
        # print(len(data))    # 1
 
        for datum in data:
            # print(datum)
 
            # 문제
            # mode 를 비롯한 나머지를 찾아보기
            mode = re.findall(r'<mode>(.+?)</mode>', datum)
            tmEf = re.findall(r'<tmEf>(.+?)</tmEf>', datum)
            wf   = re.findall(r'<wf>(.+?)</wf>', datum)
            tmn  = re.findall(r'<tmn>(.+?)</tmn>', datum)
            tmx  = re.findall(r'<tmx>(.+?)</tmx>', datum)
            reli = re.findall(r'<reliability>(.+?)</reliability>', datum)
            # print(prov[0], city[0], mode[0], tmEf[0], wf[0], tmn[0], tmx[0], reli[0])
 
            row = '{}, {}, {}, {}, {}, {}, {}, {}'.format(prov[0], city[0], mode[0], tmEf[0], wf[0], tmn[0], tmx[0], reli[0])
            print(row)
 
 
findData()
 
 
 
cs


>> datum 하나의 출력 결과


<data>

<mode>A01</mode>

<tmEf>2018-03-02 00:00</tmEf>

<wf>구름많음</wf>

<tmn>6</tmn>

<tmx>13</tmx>

<reliability>보통</reliability>

</data>



>> 25 : print(prov[0], city[0], mode[0], tmEf[0], wf[0], tmn[0], tmx[0], reli[0]) 의 결과


서울ㆍ인천ㆍ경기도 서울 A02 2018-02-24 00:00 구름조금 -2 7 높음

서울ㆍ인천ㆍ경기도 인천 A02 2018-02-24 00:00 구름조금 -2 5 높음

서울ㆍ인천ㆍ경기도 수원 A02 2018-02-24 00:00 구름조금 -3 7 높음

서울ㆍ인천ㆍ경기도 파주 A02 2018-02-24 00:00 구름조금 -7 6 높음

강원도영서 춘천 A02 2018-02-24 00:00 구름조금 -5 6 보통

강원도영서 원주 A02 2018-02-24 00:00 구름조금 -4 6 보통

강원도영동 강릉 A02 2018-02-24 00:00 구름조금 -1 7 보통

대전ㆍ세종ㆍ충청남도 대전 A02 2018-02-24 00:00 구름조금 -4 8 보통

대전ㆍ세종ㆍ충청남도 세종 A02 2018-02-24 00:00 구름조금 -5 7 보통

대전ㆍ세종ㆍ충청남도 홍성 A02 2018-02-24 00:00 구름조금 -4 7 보통

충청북도 청주 A02 2018-02-24 00:00 구름조금 -3 8 보통

광주ㆍ전라남도 광주 A02 2018-02-24 00:00 구름조금 0 12 보통

광주ㆍ전라남도 목포 A02 2018-02-24 00:00 구름조금 1 10 보통

광주ㆍ전라남도 여수 A02 2018-02-24 00:00 구름조금 3 12 보통

전라북도 전주 A02 2018-02-24 00:00 구름조금 -2 9 보통

전라북도 군산 A02 2018-02-24 00:00 구름조금 -3 7 보통

부산ㆍ울산ㆍ경상남도 부산 A02 2018-02-24 00:00 구름조금 3 12 보통

부산ㆍ울산ㆍ경상남도 울산 A02 2018-02-24 00:00 구름조금 0 11 보통

부산ㆍ울산ㆍ경상남도 창원 A02 2018-02-24 00:00 구름조금 1 12 보통

대구ㆍ경상북도 대구 A02 2018-02-24 00:00 구름조금 -1 12 보통

대구ㆍ경상북도 안동 A02 2018-02-24 00:00 구름조금 -3 10 보통

대구ㆍ경상북도 포항 A02 2018-02-24 00:00 구름조금 1 11 보통

제주도 제주 A02 2018-02-24 00:00 구름조금 5 12 보통

제주도 서귀포 A02 2018-02-24 00:00 구름조금 7 13 보통



>> 27 : 데이터를 재사용하기 위해 row 및 문자열 포맷 사용.

>> 데이터와 데이터 사이에 콤마로 구분. comma separated // CSV 



- 이런식으로도 할 수 있다.


1
2
items = re.findall(r'<mode>(.+?)</mode>.+<tmEf>(.+?)</tmEf>.+<wf>(.+?)</wf>', datum, re.DOTALL)
print(items)
cs


>> 태그와 태그 사이에 .+ 추가. re.DOTALL 옵션 추가.

>> 실행결과 (리스트 안의 튜플로 된 구조이다.)


[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름조금')]

[('A02', '2018-03-03 00:00', '구름많음')]

[('A02', '2018-03-03 00:00', '구름많음')]


-  

1
2
t = items[0]
print(t[0], t[1], t[2])
cs


>> item 은 리스트

>> items[0] 은 튜플




- 


1
2
3
4
5
6
7
8
def findLoc():
    for loc in locations:
        items = re.findall(r'<mode>(.+?)</mode>.+?<tmEf>(.+?)</tmEf>.+?<wf>(.+?)</wf>', loc, re.DOTALL)
        print(items)
        print(len(items))
 
 
findLoc()
cs


>> 태그와 태그 사이 .+ 가 아닌 .+? 이다!!

>> 실행결과의 일부


[('A02', '2018-02-24 00:00', '구름조금'), ('A02', '2018-02-24 12:00', '구름많음'), ('A02', '2018-02-25 00:00', '구름많음'), ('A02', '2018-02-25 12:00', '구름많음'), ('A02', '2018-02-26 00:00', '구름조금'), ('A02', '2018-02-26 12:00', '구름조금'), ('A02', '2018-02-27 00:00', '구름많음'), ('A02', '2018-02-27 12:00', '구름많음'), ('A02', '2018-02-28 00:00', '구름많음'), ('A02', '2018-02-28 12:00', '구름많음'), ('A01', '2018-03-01 00:00', '구름조금'), ('A01', '2018-03-02 00:00', '구름조금'), ('A01', '2018-03-03 00:00', '구름조금')]

13

[('A02', '2018-02-24 00:00', '구름조금'), ('A02', '2018-02-24 12:00', '구름많음'), ('A02', '2018-02-25 00:00', '구름많음'), ('A02', '2018-02-25 12:00', '구름많음'), ('A02', '2018-02-26 00:00', '구름조금'), ('A02', '2018-02-26 12:00', '구름조금'), ('A02', '2018-02-27 00:00', '구름많음'), ('A02', '2018-02-27 12:00', '구름많음'), ('A02', '2018-02-28 00:00', '구름많음'), ('A02', '2018-02-28 12:00', '구름많음'), ('A01', '2018-03-01 00:00', '구름조금'), ('A01', '2018-03-02 00:00', '구름조금'), ('A01', '2018-03-03 00:00', '구름조금')]

13

[('A02', '2018-02-24 00:00', '구름조금'), ('A02', '2018-02-24 12:00', '구름많음'), ('A02', '2018-02-25 00:00', '구름많음'), ('A02', '2018-02-25 12:00', '구름많음'), ('A02', '2018-02-26 00:00', '구름조금'), ('A02', '2018-02-26 12:00', '구름조금'), ('A02', '2018-02-27 00:00', '구름많음'), ('A02', '2018-02-27 12:00', '구름많음'), ('A02', '2018-02-28 00:00', '구름많음'), ('A02', '2018-02-28 12:00', '구름많음'), ('A01', '2018-03-01 00:00', '구름조금'), ('A01', '2018-03-02 00:00', '구름조금'), ('A01', '2018-03-03 00:00', '구름조금')]

13

[('A02', '2018-02-24 00:00', '구름조금'), ('A02', '2018-02-24 12:00', '구름많음'), ('A02', '2018-02-25 00:00', '구름많음'), ('A02', '2018-02-25 12:00', '구름많음'), ('A02', '2018-02-26 00:00', '구름조금'), ('A02', '2018-02-26 12:00', '구름조금'), ('A02', '2018-02-27 00:00', '구름많음'), ('A02', '2018-02-27 12:00', '구름많음'), ('A02', '2018-02-28 00:00', '구름많음'), ('A02', '2018-02-28 12:00', '구름많음'), ('A01', '2018-03-01 00:00', '구름조금'), ('A01', '2018-03-02 00:00', '구름조금'), ('A01', '2018-03-03 00:00', '구름조금')]

13

[('A02', '2018-02-24 00:00', '구름조금'), ('A02', '2018-02-24 12:00', '구름많음'), ('A02', '2018-02-25 00:00', '구름많음'), ('A02', '2018-02-25 12:00', '구름많음'), ('A02', '2018-02-26 00:00', '구름조금'), ('A02', '2018-02-26 12:00', '구름조금'), ('A02', '2018-02-27 00:00', '구름많음'), ('A02', '2018-02-27 12:00', '구름많음'), ('A02', '2018-02-28 00:00', '구름많음'), ('A02', '2018-02-28 12:00', '구름많음'), ('A01', '2018-03-01 00:00', '구름조금'), ('A01', '2018-03-02 00:00', '구름조금'), ('A01', '2018-03-03 00:00', '구름조금')]

13



1
2
3
4
5
6
7
8
9
10
11
def findLoc():
    for loc in locations:
        items = re.findall(r'<mode>(.+?)</mode>.+?<tmEf>(.+?)</tmEf>.+?<wf>(.+?)</wf>', loc, re.DOTALL)
        # print(items)
        # print(len(items))
 
        for item in items:
            print(item)
 
 
findLoc()
cs


>> 실행결과의 일부


('A02', '2018-02-28 12:00', '구름많고 비')

('A01', '2018-03-01 00:00', '구름많음')

('A01', '2018-03-02 00:00', '구름많음')

('A01', '2018-03-03 00:00', '구름많음')



1
2
for mode, tmEf, wf in items:
    print(mode, tmEf, wf)
cs


>> 이런식으로도 가능하다.



1
2
3
4
5
6
7
8
9
def findLoc2():
    for loc in locations:
        items = re.findall(r'<mode>(.+?)<.+?>.+?<.+?>(.+?)<.+?>.+?<.+?>(.+?)<.+?>', loc, re.DOTALL)
 
        for mode, tmEf, wf in items:
            print(mode, tmEf, wf)
 
 
findLoc2()
cs


>> 이런식으로도 가능하다.

>> 맨 앞에 <mode> 를 남긴 이유는 그 상위 데이터가 더 존재하므로...




'Language > Python' 카테고리의 다른 글

<3-2> Set 과 Dictionary  (0) 2018.03.02
<3-1> 파일 입출력  (0) 2018.02.23
<2-2> 리스트, 튜플  (0) 2018.02.15
<2-1> 제어문과 반복문의 연결고리  (0) 2018.02.06
<1-7> 정규표현식 with Python  (0) 2018.02.03

티스토리툴바