How We Coding

180220 튜터링 - 스택

Tutoring/17-2 Data Structure (Winter)2018. 2. 21. 22:57

< 숙제 Review >


- 3자리마다 콤마 찍기 (재귀)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
void comma(int n)
{
    int tmp = n/1000;
    if(tmp > 0) {
        comma(tmp);
        printf(",%03d", n%1000);
    }
    else {
        printf("%d", n);
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    comma(n);
 
    return 0;
}
cs



- %03d : 3자리 확보, 빈자리는 0으로..!!




< Tutoring >


- 스택의 정의 : 나중에 들어온 데이터가 먼저 꺼내진다. 

>> 그냥 프링글스 ㅎㅎ


- 스택의 ADT 및 구현하기


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>
#define MAX 100
typedef struct stack {
    int 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, int data)
{
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int main()
{
    Stack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    isFull(&s) ? puts("Full") : puts("Not Full");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    return 0;
}
 
cs


>> 실행결과


Empty

Not Full

7

5

3

1

Empty



- 연결리스트를 이용한 구현 (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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
   char data;
   struct node * next;
} Node;
 
typedef struct listStack {
   Node * top;
} ListStack;
 
void init(ListStack * list) {
   list->top = NULL;
}
 
int isEmpty(ListStack * list) {
   return list->top == NULL;
}
 
int peek(ListStack * list) {
   if(isEmpty(list)) {
      printf("빈 스택임");
      return -111111;
   }
   
   return (list->top)->data;
}
 
void push(ListStack * list, int data) {
   Node * tmp = (Node*) malloc(sizeof(Node));
   tmp->data = data;
   tmp->next = list->top;
   list->top = tmp;
}
 
void pop(ListStack * list) {
   Node *tmp = list->top;
   list->top = tmp->next;
   free(tmp);
}
 
int main()
{
    ListStack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    return 0; 
}
 
cs


>>  



- 스택의 응용


1) 괄호검사 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ) // 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void RightBracket(const char * str) {
   ListStack l1;
   init(&l1);
   
   int i; for(i=0; str[i]; i++) {
      if(str[i] == '(') push(&l1, '(');
      if(str[i] == ')') {
         if(!isEmpty(&l1)) pop(&l1);
         else {
            printf("NO\n");
            return;
         }
      }
   }
   
   if(isEmpty(&l1)) printf("YES\n");
   else printf("NO\n");
}
cs


>> 5 줄에서 for 문의 조건식을 보자. 

>> 문자열의 마지막은 널문자이다. 널문자의 아스키코드값은 0.

>> 0은 조건식에서 거짓이다.



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
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()
{
    printf("%d\n", exp("234*+"));       // 14
    printf("%d\n", exp("82/3-32*+"));   // 7
    return 0;
}
 
cs


>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.

>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.

>> for 문의 조건식에 strlen(eq[i]) 라고 적는것은 안좋다.

     for 문의 경우 초기식 - (조건식, 바디, 증감식)의 반복 으로 이루어 지는데, 조건식을 확인할 때마다 strlen() 함수가 작동한다.

     O(n) 으로 해결할 것도 O(n^2) 이 되버리는 신기한(?) 일이 발생한다.



3) 중위식을 후위식으로 바꾸기.


- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.


- 규칙

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

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

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

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

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



< 소스코드 >


>> 숙제.





< 숙제 >

- 복습 잘하기

- 올바른 괄호 문자열인지 판단하는 함수( "(", "{", "[" : 세 종류의 괄호 사용)

- 중위식을 후위식으로 만드는 코드.(http://boj.kr/1918)

- 중위식을 후위식으로 만든 다음 그 후위식을 계산하는 코드

- 큐 예습해오기.


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

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06
180130 튜터링 - 재귀함수 만들기, 분석하기  (0) 2018.02.06

Week 2 - DFS

Tutoring/PS2018. 2. 21. 16:36

<180226>


Week 2 : DFS


[11724] 연결요소의 개수 (http://boj.kr/11724)


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
#include <stdio.h>
 
int n, m;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
 
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
 
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs


>> DFS 기본 

>> 모든 정점에 대해서 DFS() 실행한 횟수가 컴퍼넌트의 갯수가 된다.


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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int v;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
void addNode(List *list, int v)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->v = v;
    newNode->next = list->head;
    list->head = newNode;
}
 
int n, m;
List g[1001];
int visited[1001];
 
void dfs(int s)
{
    Node *cur = g[s].head;
    visited[s] = 1;
 
    while(cur != NULL) {
        int next = cur->v;
        if(!visited[next]) dfs(next);
        else cur = cur->next;
    }
}
 
int main()
{
    int i, ans=0;
    scanf("%d%d", &n, &m);
 
    for(i=0; i<=n; i++)
        init(g+i);
 
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        addNode(g+a, b);
        addNode(g+b, a);
    }
      
    for(i=1; i<=n; i++) {
        if(!visited[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}
 
cs




[10026] 적록색약 


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
#include <stdio.h>
 
int n;
char g[101][101];
int visited[101][101];
int di[]={1, 0, -1, 0};
int dj[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < n) && (0 <= j && j < n);
}
 
void dfs(int i, int j, char color)
{
    int k;
    visited[i][j] = 1;
    for(k=0; k<4; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && !visited[ni][nj] && g[ni][nj] == color)
            dfs(ni, nj, color);
    }
}
 
void go()
{
    int i, j, ans=0;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
           if(!visited[i][j]) {
                ans++;
                dfs(i, j, g[i][j]);
           }
        }
    }
    printf("%d\n", ans);
}
 
int main()
{
    int i, j;
    int rb=0, rgb=0;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        scanf("%s", g[i]);
 
    go();
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            visited[i][j] = 0;
            if(g[i][j] == 'G')
                g[i][j] = 'R';
        }
    }
    
    go();
    return 0;
}
 
cs


>> 



[2606] 바이러스


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 <stdio.h>
 
int n, m;
int g[101][101];
int visited[101];
 
int dfs(int s)
{
    int i, ret=1;
    visited[s] = 1;
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            ret += dfs(i);
    }
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &m);
   
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = g[b][a] = 1;
    }
        
    printf("%d\n", dfs(1)-1);
 
    return 0;
}
cs


>> 1번 컴퓨터에서 갈 수 있는 컴퓨터의 갯수.



[2583] 영역구하기


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int m, n, k;
int g[105][105];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
bool safe(int r, int c)
{
    return (0 <= r && r < m) && (0 <= c && c < n); 
}
 
int dfs(int r, int c)
{
    int ret=1;
    g[r][c] = 1;
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && !g[nr][nc])
            ret += dfs(nr, nc);
    }
    return ret;
}
 
int main()
{
    int r, c, ans=0;
    scanf("%d%d%d", &m, &n, &k);
 
    while(k--) {
        int x, y, x2, y2;
        scanf("%d%d%d%d", &x, &y, &x2, &y2);
 
        for(r=y; r<y2; r++)
            for(c=x; c<x2; c++)
                g[r][c] = 1;
    } 
 
 
    vector<int> v;
    for(r=0; r<m; r++) {
        for(c=0; c<n; c++) {
            if(!g[r][c]) {
                ans++;
                v.push_back(dfs(r, c));
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", ans);
    for(int i=0; i<v.size(); i++)
        printf("%d ", v[i]);
    puts("");
}
cs


>> 영역을 칠하는 것이 핵심인데, 이게 좀 헷갈린다.

>> 영역만 구하면 다음에 할일은 컴퍼넌트 갯수 구하기와 동일하다.



[10451] 순열 사이클


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
#include <stdio.h>
 
int n;
int g[1001][1001];
int visited[1001];
 
void dfs(int s)
{
    int i;
    visited[s] = 1;
 
    for(i=1; i<=n; i++) {
        if(g[s][i] && !visited[i])
            dfs(i);
    }
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, k;
        int ans=0;
        scanf("%d", &n);
 
        for(i=1; i<=n; i++) {
            scanf("%d", &k);
            g[i][k] = 1;
        }
 
        for(i=1; i<=n; i++) {
            if(!visited[i]) {
                ans++;
                dfs(i);
            }
        }
        
        printf("%d\n", ans);
 
        for(i=1; i<=n; i++) {
            visited[i] = 0;
            for(j=1; j<=n; j++)
                g[i][j] = 0;
        }
    }
    return 0;
}
cs


>> 그래프 모델링 후 컴퍼넌트 구하는 문제.



[]


'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 1 - DFS  (0) 2018.02.20

[2216] 문자열과 점수

BOJ/DP2018. 2. 21. 08:15

http://boj.kr/2216


d[i][j] = s의 i번째 문자열까지, t의 j번째 문자열까지의 최대 점수


< AC 코드 >


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 <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
int slen, tlen;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(si == slen) return b * (tlen-ti);
    if(ti == tlen) return b * (slen-si);
 
    if(s[si] == t[ti])
        ret = max(ret, go(si+1, ti+1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si+1, ti+1)+c);
    ret = max(ret, go(si+1, ti)+b);
    ret = max(ret, go(si, ti+1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    slen = strlen(s);
    tlen = strlen(t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(0, 0)); 
    return 0;
}
 
cs


>> 0x8000000 : int 의 최소값이다.

>> 무조건 위에서 아래로 가도록 짜진 말아야겠다...



< 틀린 코드 >


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 <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(si < 0) return b * (ti-1); 
    if(ti < 0) return b * (si-1);
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(s[si] == t[ti])
        ret = max(ret, go(si-1, ti-1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si-1, ti-1)+c);
    ret = max(ret, go(si-1, ti)+b);
    ret = max(ret, go(si, ti-1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(strlen(s)-1, strlen(t))-1); 
    return 0;
}
 
cs


>> 점화식은 맞는데, 18%에서 틀렸다고 한다. 왜 틀린건지 모르겠다...ㅜㅜ

>> 17, 18 에서의 탈출조건도 ti+1, si+1 인거 같은데, 이렇게 하면 테케도 통과를 못한다...


>> 위 코드에 대한 반례


5 -3 -6 

a 

b


>> 정답코드에서는 -6이, 위 코드에서는 -4가 나온다...


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

[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22
[11048] 이동하기  (0) 2018.02.18
[9184] 신나는 함수 실행  (0) 2018.02.16
[2302] 극장 좌석  (0) 2018.02.05

170803 - Week 6

Tutoring/17-1 C Lang (Summer)2018. 2. 21. 00:15

Week 6

1. 색종이(넓이)

- 도화지를 2차원 배열(0으로 초기화)로 생각할 수 있고, 색종이를 붙인다는 건

  그 도화지에 1을 채우는 것으로 생각할 수 있다.

- 결국 1의 갯수가 색종이가 붙여진 곳의 넓이..!!

2. 색종이2(둘레)

- 000

  010

  000 에서 1은 1x1 크기의 색종이, 이 색종이의 둘레는 4


- 000

  010

  000

  010

  000 에서 도화지에 붙인 색종이의 둘레는 8.

- 즉 1의 상하좌우에 있는 0의 갯수가 둘레가 됨..!!

  for(i=0; i<100; i++) {

  for(j=0; j<100; j++) {

if(dowhaji[i][j] == 1) {

if(dowhaji[i-1][j] == 0) cnt++; // 상

if(dowhaji[i+1][j] == 0) cnt++; // 하

if(dowhaji[i][j-1] == 0) cnt++; // 좌

if(dowhaji[i][j+1] == 0) cnt++; // 우

}

}

  }

3. 통계학 문제

- 빈도수관련 하여 배열을 이용하여 카운트 할 수 있는데,

  이 문제에서 값의 범위는 절대값이 4000 이하.

  즉 -4000 ~ 4000 까지의 값이 들어오게 되는데,

  이 값을 0 ~ 8000 으로 매핑해서 빈도수를 체크할 수 있음.

  즉 scanf("%d", &k); cnt[k]++; 이런식으로 가능

- 반올림의 경우 0.5를 더한 후 버림을 하면 구할 수 있음.

4. 동적할당

- #include <stdlib.h> 헤더파일 선언 필요

- 배열의 크기를 그때그때 다르게 하고 싶을때..?

int main() {

…

f(n);

…

}

void f(int n)

{

int arr[n]; // 컴파일 에러 발생

}


int *arr = (int*)malloc(sizeof(int)*n);

>> malloc() 은 주소를 반환. int*로 캐스팅을 하는 이유는

   포인터 연산(배열의 인덱싱)을 할 때 자료형의 크기(여기서는 int)만큼

   계산되기 위해..

   위의 경우 sizeof(int) = 4Bytes * n 크기의 공간이 생성되고,

   그 공간의 시작주소를 반환하게 되며 arr에 그 시작주소가 저장됨.

   (int*)으로 캐스팅하여 arr[0] ~ arr[n-1]까지 배열처럼 사용가능.


동적할당은 힙 이라는 메모리 영역이 할당되어,

free(arr); 이라는 명령어를 통해 해당 메모리를 따로 해제시켜줘야함.

#include <stdio.h>

char* getName();


int main()

{

char *name;

name = getName();

printf("%s\n", name);

return 0;

}


char* getName()

{

char name[30];

scanf("%s",name);

return name;

}


>> 위 문장은 에러발생. 에러메세지 확인해보기. 

>> getName() 의 name은 지역변수..!!

>> 지역변수는 함수가 소멸되면 같이 소멸됨 

>> 동적할당으로 해결 가능

'Tutoring > 17-1 C Lang (Summer)' 카테고리의 다른 글

170727 - Week 5  (0) 2018.02.21
170720 - Week 4  (0) 2018.02.21
170706 - Week 2  (0) 2018.02.21
170629 - Week 1  (0) 2018.02.21

170727 - Week 5

Tutoring/17-1 C Lang (Summer)2018. 2. 21. 00:13

Week 5


1. 버블정렬(오름차순//내림차순)

for(i=0; i<N-1; i++)

for(j=0; j<N-1-i; j++)

if(a[j] > a[j+1])

swap(a[j], a[j+1]);

2. int strLen(char str[]);

3. void strCpy(char dest[], char src[]); // 널문자 삽입에 주의

4. void strCat(char dest[], char src[]); 

(위 함수들 구현하기)

5. 문자열 길이에 따른 정렬. 

>> 배열에 저장된 문자열들의 스왑은 어떻게..?

'Tutoring > 17-1 C Lang (Summer)' 카테고리의 다른 글

170803 - Week 6  (0) 2018.02.21
170720 - Week 4  (0) 2018.02.21
170706 - Week 2  (0) 2018.02.21
170629 - Week 1  (0) 2018.02.21

170720 - Week 4

Tutoring/17-1 C Lang (Summer)2018. 2. 21. 00:12

Week3


BOJ 3주차 문제 풀기!

파워업 Section 5까지 공부해오기!



Week 4 


1. 2차원 배열 char str[5][20]; 에서 str의 타입은?

>> char [20]

2. 메인함수에 2차원 배열의 이름을 전달하면,

   전달받는 함수에서의 매개변수는 어떻게 선언??

>> void f(char 배열이름[][10]); //

>> 1차원 배열 전달받을 땐 void f2(char str[]); // 타입 잘 생각해보기..!!

>> 매개변수의 한하여 void f(int *s) 와 void f(int s[])는 같은 표현!!

3. 포인터배열 : int *pArr[10]; // 포인터변수를 배열로..

4. 배열포인터 : int (*ArrP)[10]; // 포인터변수 ArrP의 타입은 int [10]

5. int main(int argc, char *argv[]) 

>> argc가 가지는 값, argv[i]에 저장되는 문자열들의 정체..!!

'Tutoring > 17-1 C Lang (Summer)' 카테고리의 다른 글

170803 - Week 6  (0) 2018.02.21
170727 - Week 5  (0) 2018.02.21
170706 - Week 2  (0) 2018.02.21
170629 - Week 1  (0) 2018.02.21

170706 - Week 2

Tutoring/17-1 C Lang (Summer)2018. 2. 21. 00:09

Week 2


1. 배열의 이름 : 배열의 시작주소(첫번째 요소의 주소)

2. 배열과 포인터와의 관계

- 배열의 이름 : 상수형태의 포인터

- 포인터 : 변수

3. 배열을 포인터처럼, 포인터를 배열처럼 사용 가능

4. 포인터 연산

- 1 증가시 자료형의 크기만큼 주소가 증가

- p++ 이후 *p vs *(p+1)

- *(p+i) == p[i] 와 동일

5. 문자열의 저장 방법

- char str1[] = "Good Morning"; // 배열의 초기화

- char *str2 = "Good Bye!"; // str2에는 문자열의 첫번째 문자의 주소가 저장됨.

- " " : 문자열은 첫 문자의 시작주소

cf) "Hello"[0] 이런 표현 가능

cf) printf(str1); 가능 // 이렇게 쓰지는 말구…!!

6. 변수형태의 문자열 vs 상수형태의 문자열

- str2에 저장된 문자열은 변경 불가능..!!

- 배열의 중간요소에 널문자를 대입하고 출력하면..? // 널문자는 문자열의 끝

- 상수(리터럴)와 변수의 차이..!!

7. 함수에 배열 전달하기.

- sizeof 연산자

'Tutoring > 17-1 C Lang (Summer)' 카테고리의 다른 글

170803 - Week 6  (0) 2018.02.21
170727 - Week 5  (0) 2018.02.21
170720 - Week 4  (0) 2018.02.21
170629 - Week 1  (0) 2018.02.21

170629 - Week 1

Tutoring/17-1 C Lang (Summer)2018. 2. 21. 00:08

170629


1. 아스키코드 특징

2. 문자열의 끝은 널문자, 널문자의 아스키값은 0

3. char형은 문자형(1바이트 정수형)

4. 1 vs '1' vs "1" // 메모리에 어떻게 저장이 되는지..

5. -1 은 2진수로 11111111 (1바이트 기준)

6. 문자끼리의 연산 : 'b'-'a'

7. '9'를 9로 만들기

8. 구구단 while()으로 짤 때 주의점.

9. 배열 선언 방법. 배열의 크기.

10. 배열을 사용하는 이유. 

11. 배열의 각 공간은 인덱스를 통해서 접근 (for문으로)

12. 배열의 이름은 배열의 시작주소 (그렇다면 함수의 이름은? )

13. 배열의 초기화 (크기만큼 안하면 0으로 채워짐, 문자열 초기화)

14. 문자배열 vs 문자열 // 널문자..!! (2번 확인)

15. 문자열의 길이 구하기 // while()문 혹은 for()문

16. while(str[i++]) { cnt++; } 이해해보기. 조건식에서 참과 거짓의 값

17. 배열에 있는 요소들중에서 최대값 혹은 최소값 구하기.

18. int arr[100] = {0}; // 모든 배열요소 0으로 초기화

19. 배열의 인덱스는 0부터 크기-1 까지..

20. 포인터 선언방법

21. &는 피연산자의 주소를 반환하는 연산자

22. *는 참조 연산자

23. *a = *b; // 포인터 변수 b가 가리키는 공간(변수)에 있는 값을 포인터변수 a가 가리키는 공간(변수)에 대입

24. L-value = R-value : 공간 = 값

25. swap(a, b); vs swap(&a, &b); 지역변수 개념 생각해보기

'Tutoring > 17-1 C Lang (Summer)' 카테고리의 다른 글

170803 - Week 6  (0) 2018.02.21
170727 - Week 5  (0) 2018.02.21
170720 - Week 4  (0) 2018.02.21
170706 - Week 2  (0) 2018.02.21

Week 1 - DFS

Tutoring/PS2018. 2. 20. 00:24

< 180219 >


Week 1 - DFS 


[BOJ/2667] 단지번호 붙이기 (http://boj.kr/2667)


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
 
#define N 101
int n, cnt, a[N][N], s[N];
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
bool cmp(int a, int b)
{
    return a < b;
}
 
void dfs(int x, int y, int k)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    a[x][y] = k;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            dfs(x+dx[i], y+dy[i], k);
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j] == 1)
            {
                cnt++;
                dfs(i, j, cnt+1);
            }
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            if(a[i][j])
                s[a[i][j]-2]++;
 
    std::sort(s, s+cnt, cmp);
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", s[i]);
 
    return 0;
}
cs





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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, cnt, a[101][101];
vector<int> v;
 
bool safe(int x, int y)
{
    return (0 <= x && x < n) && (0<= y && y < n);
}
 
int dfs(int x, int y)
{
    int i, dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    int ret = 1;
    a[x][y] = 0;
    for(i=0; i<4; i++)
        if(safe(x+dx[i], y+dy[i]) && a[x+dx[i]][y+dy[i]]==1 )
            ret += dfs(x+dx[i], y+dy[i]);
    return ret;
}    
 
void solve(void)
{
    int i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            if(a[i][j] == 1)
            {
                cnt++;
                v.push_back(dfs(i, j));
            }
        }
    }
 
    sort(v.begin(), v.end());
}
 
int main(void)
{
    int i, j;
    scanf("%d", &n);
 
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            scanf("%1d", &a[i][j]);
 
    solve();
 
    printf("%d\n", cnt);
    for(i=0; i<cnt; i++)
        printf("%d\n", v[i]);
 
}
 
cs


>> dfs() 의 리턴형이 int 이다. 결국 dfs() 호출된 횟수를 리턴하게 된다.

>> vector 를 사용했다.



[BOJ/1012] 유기농 배추 (http://boj.kr/1012)


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
#include <stdio.h>
 
int r, c;
int g[51][51];
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int r, int c)
{
    int k;
    g[r][c] = 0;
 
    for(k=0; k<4; k++) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if(safe(nr, nc) && g[nr][nc])
            dfs(nr, nc);
    }
 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    
    while(tc--) {
        int i, j, k;
        int ans = 0;
        scanf("%d%d%d", &r, &c, &k);
    
        while(k--) {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][b] = 1;
        }
                
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
cs


>> 16 : 방문체크 배열을 따로 안만들고, 방문한곳을 0으로 바꿔줌으로써 다시 방문할 수 없도록 하였다.



[BOJ/4963] 섬의 개수 (http://boj.kr/2963)


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
#include <stdio.h>
 
int r, c;
int g[51][51];
int di[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dj[]={-1, 0, 1, -1, 1, -1, 0, 1};
 
int safe(int i, int j)
{
    return (0 <= i && i < r) && (0 <= j && j < c);
}
 
void dfs(int i, int j)
{
    int k;
    g[i][j] = 0;
 
    for(k=0; k<8; k++) {
        int ni = i+di[k];
        int nj = j+dj[k];
        if(safe(ni, nj) && g[ni][nj])
            dfs(ni, nj);
    }
}
 
int main()
{
    while(1) {
        int i, j;
        int ans=0;
        scanf("%d%d", &c, &r);
 
        if(!r && !c) break;
        
        for(i=0; i<r; i++)
            for(j=0; j<c; j++)
                scanf("%d", &g[i][j]);
 
        for(i=0; i<r; i++) {
            for(j=0; j<c; j++) {
                if(g[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
cs


>> 위와 같은 유형의 문제. 차이점이라면 8방탐색..!!

'Tutoring > PS' 카테고리의 다른 글

Week 6 - BFS (숨박꼭질)  (0) 2018.03.30
Week 5 - BFS  (0) 2018.03.24
Week 4 - BFS  (0) 2018.03.11
Week3 - DFS  (0) 2018.03.07
Week 2 - DFS  (0) 2018.02.21

[11048] 이동하기

BOJ/DP2018. 2. 18. 01:24

http://boj.kr/11048


기본 DP2.


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
#include <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int go(int n, int m)
{
    int a, b;
    if(!n || !m) return 0;
    if(d[n][m] != -1) return d[n][m];
 
    a = go(n-1, m);
    b = go(n, m-1);
    return d[n][m] = (a > b ? a : b) + g[n][m];
}
 
int main()
{
    int i, j;
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", go(n, m));
    return 0;
}
 
cs


>> go(n-1, m-1) 은 고려할 필요가 없다. 



< Bottom Up >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
int n, m, g[1001][1001], d[1001][1001];
 
int main()
{
    int i, j, tmp;    
    scanf("%d %d", &n, &m);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d", &g[i][j]);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            d[i][j] = g[i][j];
            tmp = d[i-1][j] > d[i][j-1] ? d[i-1][j] : d[i][j-1];
            d[i][j] += tmp;
        }
    }
    printf("%d\n", d[n][m]);
    return 0;
}
cs


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

[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21
[9184] 신나는 함수 실행  (0) 2018.02.16
[2302] 극장 좌석  (0) 2018.02.05
[1937] 욕심쟁이 판다  (0) 2018.02.01

티스토리툴바