How We Coding

Week 04

Tutoring/18-1 C Lang2018. 4. 11. 23:40

< 180411 >


Week 04



1) 1의 보수, 2의 보수.


- 10은 2진수로 00001010 (8비트 기준)

- 1의 보수를 취하면 11110101 이 된다. (0은 1로, 1은 0으로)

- 2의 보수는 1의 보수의 결과에 1을 더하면 된다. 11110110


>> 2의 보수의 결과는 -10이 된다. 

>> 검증 : -1은 11111111 이다. 여기에서 9인 00001001 을 빼면 11110110 이 된다.



2) 삼항연산자( ? 연산자)


- 삼항 연산자의 폼은 (조건식) ? 식1 : 식2; 이다.

- 조건식의 결과는 참 혹은 거짓이다.

- 조건식의 결과가 참이면 식1이, 거짓이면 식2가 수행된다.



3-1) 두 수를 입력받아, 두수의 차이의 절대값을 출력하는 프로그래밍

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a > b ? a-b : b-a);
    return 0;
}
cs



3-2) 세 수를 입력받아, 가장 큰값과 가장 작은 값을 출력하는 프로그래밍

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    int a, b, c;
    int max, min;
    scanf("%d%d%d", &a, &b, &c);
    max = a > b ?(a > c ? a : c) : (b > c ? b : c);
    min = a < b ?(a < c ? a : c) : (b < c ? b : c);
    printf("%d %d\n", max, min);
    return 0;
}
cs


>> 중첩된 삼항연산자 이해해보기..!!



4) 조건식에서의 참과 거짓.

- 거짓은 0으로 표현된다.

- 참은 0이 아닌 모든값, 즉 0이 아닌 모든 정수값이 된다.


1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main()
{    
    0 ? printf("A") : printf("B");
    1 ? printf("A") : printf("B");
    13 ? printf("A") : printf("B");
    -2 ? printf("A") : printf("B");
 
    return 0;
}
cs

>> 실행결과 : BAAA



5) && 연산자 

- (조건식) && (조건식) 의 형태를 이룬다.

- 두 조건식이 참이면 참이 된다.


1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
 
int main()
{
    1 && 1 ? printf("A") : printf("B");
    1 && 0 ? printf("A") : printf("B");
    0 && 1 ? printf("A") : printf("B");
    0 && 0 ? printf("A") : printf("B");
    return 0;
}
cs


>> 실행결과 : ABBB



6) 문자 하나를 입력받아, 해당 문자가 알파벳 대문자인지 판단하는 프로그래밍.


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    char ch;
    scanf("%c", &ch);
    'A' <= ch && ch <= 'Z' ? printf("TRUE") : printf("FALSE");
    return 0;
}
cs


>> 아스키코드값의 특징, && 의 특징, 삼항연산자를 쓸 줄 알면 풀 수 있는 문제이다.



7) || 연산자.

- (조건식) || (조건식) 의 형태를 가지며, 두 조건식 중 하나의 조건식만 참이면 참이 된다.


1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main()
{
    1 || 1 ? printf("A") : printf("B");
    1 || 0 ? printf("A") : printf("B");
    0 || 1 ? printf("A") : printf("B");
    0 || 0 ? printf("A") : printf("B");
    return 0;
}
 
cs


>> 실행결과 : AAAB



8) 대입연산자


1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    int a, b;
    a = b = 0;
    printf("%d %d\n", a, b);
    return 0;
}
cs


>> 6 번 라인을 보자. b = 0; 이라는 식은 b 에 0을 대입하고, 그 식 자체의 결과는 또한 0이 된다.

>> 그렇기 때문에 a = b = 0; 은 a = (b = 0); 에서 a = (0); 으로 이어지며, 

>> 결과적으로 a 와 b 두 변수 모두에 0이 대입된다. 



9) || 연산의 단축연산


- 아래의 프로그래밍의 실행결과를 에측해보자.


1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    int a, b;
    a = b = 0;
    
    (a = 5) || (b = 3) ? printf("A") : printf("B");
    printf(" %d %d\n", a, b);
 
    return 0;
}
cs



10) ! 연산자 (NOT 연산자)


- 참을 거짓으로, 거짓을 참으로 만드는 연산자 이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    int a=0;
    int b=3;
        
    !a ? printf("A") : printf("B");
    !b ? printf("A") : printf("B");
    !0 ? printf("A") : printf("B");
    !1 ? printf("A") : printf("B");
 
    return 0;
}
cs


>> 실행결과는 ABAB



11) Shift 연산자 >>, <<


- << 는 비트단위로 왼쪽으로 한칸씩 밀어낸다.

- >> 는 비트단위로 오른쪽으로 한칸씩 밀어낸다.


- 10을 2진수로 표현하면 00001010 이다.

- a = 10; a = a >> 1; 이 수행되면, 00000101 이 된다. 즉 a 에는 5가 저장지며, 결과적으로 2로 나눈 몫이 된다.

- a = 10; a = a << 1; 이 수행되면, 00010100 이 된다. 즉 a 에는 20이 저장되며, 결과적으로 2가 곱해진 결과가 된다.


- a = 10; a = a >> 2; 가 수행되면 a 는 2가 된다.

- a = 10; a = a << 2; 가 수행되면 a 는 40이 된다.



12) 기타.

- 콤마연산자

- 연산자 우선순위

- 단항, 2항, 3항, 대입, 콤마 연산자.

- 컴퓨터는 뺄셈, 곱셈, 나눗셈을 보수를 이용해서 덧셈으로 처리한다는 내용. >> 10 - 3 => 10 + (-3)

- 나눗셈의 경우에 피제수와 보수를 더하여 100이 될 때까지 더해진 횟수가 몫이 된다는 내용


>> Self...^^

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 06  (0) 2018.04.23
Week 05  (0) 2018.04.18
Week 03  (0) 2018.04.04
Week 02  (2) 2018.03.28
Week 01  (0) 2018.03.21

Week 3-1 : Linked List

Tutoring/18-1 DS2018. 4. 11. 00:23

< 180410 >


1) 수시고사 review 

- 특정 알파벳 갯수를 구하는 함수 만들기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int findCh(char *s, char ch)
{
    int cnt=0;
    while(*s) {
        if(*s == ch) cnt++;
        s++;
    }
    return cnt;
}
 
int main()
{
    char str[]="Data Structure";
    int cnt;
 
    cnt = findCh(str, 'u');
    printf("%d\n", cnt);
    return 0;
}
cs



2) 노드 디자인하기 (with 자기참조 구조체) AND 헤드 포인터 선언 및 초기화

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
int main()
{
    ListNode *head = NULL;
    
    return 0;
}
cs


>> 3-6 : 노드 디자인하기

>> 10 : 노드를 연결하는 시작끈의 역할..정도?

>>        NULL 로 초기화 해야한다.


>> main() 에서 10라인이 수행되고 나서의 상황.



3) create_node(10, NULL) 함수 만들기.

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>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int date, ListNode *link)
{
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data  = data;
    newNode->link = link;
    return newNode;
}
 
int main()
{
    ListNode *head = NULL;
    ListNode *newNode = create_node(10, NULL);
 
    return 0;
}
cs


>> 그냥 노드를 만들어서 그 노드를 리턴하는 함수..!!

>> 매개변수로는 data 에 저장할 값과 새로운 노드에 연결할 노드의 주소를 전달한다.


>> create_node() 가 호출되어 종료되기 직전의 상황이며, 빨간선으로 된 화살표는 함수가 리턴한 결과이다.

>> data 와 link 의 매개변수에 대한 그림은 생략...(사실 그렸어야 하는데, 빼먹음. 피피티 작업 다시 하기 귀찮......)


>> create_node() 함수의 호출이 끝난 다음 main() 의 상황이다.



4) 지역변수와 동적할당

1
2
3
4
5
6
7
ListNode* create_node(int date, ListNode *link)
{
    ListNode newNode;
    newNode.data  = data;
    newNode.link = link;
    return &newNode;
}
cs


>> 이런식으로 하면 newNode 의 주소가 넘어가지만, 

     newNode 는 지역변수이므로 함수가 끝나는 시점(중괄호가 끝나는 시점)에서 더이상 유효하지 않게 된다.

     그렇기 때문에, 해당 메모리는 언제 다른 변수에게 할당될 지 모르는 일. 

>> 하지만 동적할당을 하면 해당 변수의 라이프 타임은 프로그래머가 free() 로 직접 해제하기 전까지 유효하게 된다.

>> 그렇기 때문에 3) 에서 처럼 작성하는 것이 옳다. (함수가 끝나도 해당 데이터는 유효하므로..!!)



5) 헤드 포인터에 첫 노드 연결하기.


>> 이런 모양의 결과가 나오도록 add_node() 를 구현해보려고 한다.


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *link;
} ListNode;
 
ListNode* create_node(int date, ListNode *link)
{
    ListNode newNode;
    newNode.data  = data;
    newNode.link = link;
    return &newNode;
}
 
void add_node(ListNode **head, ListNode *listNode)
{
    *head = listNode;
}
 
int main()
{
    ListNode *head = NULL;
    ListNode *newNode = create_node(10, NULL);
    add_node(&head, newNode);
    return 0;
}
cs


>> 17-20, 26 : 매개변수를 전달하는 데 있어 타입에 꼭 신경을 쓰자, 포인터 변수의 주소를 넘기므로 더블포인터로 값(주소)을 받을 수 있다.

>> 단순히 하나를 연결하기 위한 함수이다. 확장할 예정이니 태클은 ㄴㄴ.



>> add_node() 함수가 호출된 직후의 상황. add_node() 의 head 와 link 는 매개변수이지만, 해당함수의 지역변수라고 보면 된다.




>> 19 번 라인이 수행된 결과이다.



- 시간내서 http://ychooni.tistory.com/34?category=277002 여기에 있는 내용들도 확인해보자..!!


'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 4-1 : Linked List  (0) 2018.04.18
Week 3-2 : Linked List  (0) 2018.04.15
Week 2-2 : ArrayList  (0) 2018.04.05
Week 2-1 : How to code Recursive function2  (0) 2018.04.04
Week 1-2 : How to code Recursive function  (0) 2018.03.30

[TRIANGLEPATH] 삼각형 위의 최대경로

PS/종만북2018. 4. 10. 01:51

### DP ###


[TRIANGLEPATH] 삼각형 위의 최대경로 : https://algospot.com/judge/problem/read/TRIANGLEPATH



<소스코드>


d[r][c] : (r, c) 에서 n-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
#include <stdio.h>
 
int n;
int g[101][101];
int d[101][101];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int trianglePath(int r, int c)
{
    int ret;
    if(!g[r][c]) return 0;
    if(r == n-1) return g[r][c];
 
    if(d[r][c] != -1) return d[r][c];
 
    ret = trianglePath(r+1, c);
    ret = max(ret, trianglePath(r+1, c+1)); 
    return d[r][c] = g[r][c]+ret; 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<=i; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = -1;
            }
        }
    
        printf("%d\n", trianglePath(0, 0));
    }
    return 0;
}
cs


'PS > 종만북' 카테고리의 다른 글

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[PICNIC] 소풍  (0) 2018.04.09
[JUMPGAME] 외발뛰기  (0) 2018.04.09

[PICNIC] 소풍

PS/종만북2018. 4. 9. 19:53

[PICNIC] 소풍 : https://algospot.com/judge/problem/read/PICNIC



### 완전탐색 ###


<소스코드>


picnic(k) : k 명의 짝이 정해졌을 때, n-k 명으로 짝을 지을 수 있는 경우의 수..


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>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic(int k)
{
    int a, ret = 0;
    if(k == n) return 1;
    
    a = findA();
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic(k+2);
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic(0));
    }
    return 0;
}
cs


>> 쉬운듯 쉽지 않은 듯..

>> 이런 문제를 풀 때는 (0, 1) 과 (1, 0)을 따로 세면 안된다고 한다.

>> 또한 (0, 1)을 세고, (2, 3)을 센 것과 (2, 3)을 먼저 세고 (0, 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
#include <stdio.h>
#include <string.h>
 
int isFriend[11][11];
int n, hasPair[11];
 
int findA()
{
    for(int i=0; i<n; i++)
        if(!hasPair[i])
            return i;
    return n;
}
 
int picnic()
{
    int a, ret = 0;
    
    a = findA();
    if(a == n) return 1;
 
    hasPair[a] = 1;
 
    for(int i=0; i<n; i++) {
        if(isFriend[a][i] && !hasPair[i]) {
            hasPair[i] = 1;
            ret += picnic();
            hasPair[i] = 0;
        }
    }
    hasPair[a] = 0;
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int m, ans=0;
        scanf("%d%d", &n, &m);
        
        memset(isFriend, 0, sizeof(isFriend));
        while(m--) {
           int a, b;
           scanf("%d%d", &a, &b);
           isFriend[a][b] = isFriend[b][a] = 1;
        }
        printf("%d\n", picnic());
    }
    return 0;
}
cs


>> 매개변수를 없애고, 탈출조건이 조금 변경되었다.

>> 모두 짝이 있다면 하나의 경우의 수가 완성된 셈이다.

'PS > 종만북' 카테고리의 다른 글

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[JUMPGAME] 외발뛰기  (0) 2018.04.09

[JUMPGAME] 외발뛰기

PS/종만북2018. 4. 9. 00:02

### DP ###


[JUMPGAME] 외발뛰기 : https://algospot.com/judge/problem/read/JUMPGAME


<소스코드>


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
#include <stdio.h>
 
int n;
int g[101][101], d[101][101];
 
int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) + jump(r, c+g[r][c]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = -1;
            }
        }
 
        jump(0, 0) ? puts("YES") : puts("NO");
    }
    return 0;
}
cs


>> 기본 DP 문제. jump(r, c) : r, c 까지 점프해서 (n-1, n-1) 로 갈 수 있는지 여부. (0, 0 시작이므로..)

>> d[i][j] = 0 으로 초기화 하면 시간초과가 발생한다..



- 종만북 풀이 


1
2
3
4
5
6
7
int jump(int r, int c)
{
    if(r >= n || c >= n) return 0;
    if(r == n-1 && c == n-1) return 1;
    if(d[r][c] != -1) return d[r][c];
    return d[r][c] = jump(r+g[r][c], c) || jump(r, c+g[r][c]);
}
cs


>> jump() 에서 6번라인을 || 로 처리하였다...!!

>> 첫번째 코드는 16ms 가 나왔는데, || 로 변경한 코드는 8ms 가 나왔다..!!



- 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
#include <cstdio>
 
int g[101][101], d[101][101];
 
int jump(int y, int x)
{
    int i, ans=0;
    int &ret = d[y][x];
    if(y < 1 || x < 1) return 0;
    if(y == 1 && x == 1) return 1;
    if(ret) return ret;
    
 
    for(i=1; i<x; i++)
        if(g[y][x-i]==i)
            ans += jump(y,x-i);
    
    for(i=1; i<y; i++)
        if(g[y-i][x]==i)
            ans += jump(y-i,x);
    return ret = ans;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int i, j, n;
        scanf("%d", &n);
        
        for(i=1; i<=n; i++) {
            for(j=1; j<=n; j++) {
                scanf("%d", &g[i][j]);
                d[i][j] = 0;
            }
        }
        
        jump(n, n) ? puts("YES") : puts("NO");
    }
}
cs


>> jump(n, n) 으로 시작했다. 굳이 이럴필요가 없었는데, 거꾸로 타고 가는 것을 고집했던 것 같다.

'PS > 종만북' 카테고리의 다른 글

[TILING2] 타일링  (0) 2018.04.15
[PI] 원주율 외우기  (0) 2018.04.15
[LIS] 최대 증가 부분 수열  (0) 2018.04.13
[TRIANGLEPATH] 삼각형 위의 최대경로  (0) 2018.04.10
[PICNIC] 소풍  (0) 2018.04.09

git 초보를 위한 풀리퀘스트(pull request) 방법

git2018. 4. 7. 22:16

참고 : https://wayhome25.github.io/git/2017/07/08/git-first-pull-request-story/


2. clone, remote 설정

단계에서 


  • 로컬 저장소에 원격 저장소를 추가한다. 위 작업과 동일하게 github 저장소에서 clone or download 메뉴를 통해서 확인한 url을 사용한다.
    • 원본 프로젝트 저장소 (직접 추가 필요)
    • fork한 로컬 프로젝트 (origin이라는 별명으로 기본으로 추가되어 있다. 따로 추가할 필요 없음)
# 원본 프로젝트 저장소를 원격 저장소로 추가
$ git remote add real-blog(별명) https://github.com/원본계정/blog.github.io.git

# 원격 저장소 설정 현황 확인방법
$ git remote -v

위와 같은 내용이 있는데, 원본계정 이라 함은 타겟 저장소를 얘기하는 것 같다. 즉, fork 한 저장소..!!


'git' 카테고리의 다른 글

Git과 Github  (0) 2019.01.04

Week 7 - DFS+BFS

Tutoring/PS2018. 4. 7. 00:26

<>


Week 7 : DFS+BFS


[2146] 다리 만들기 (http://boj.kr/2146) 


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
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
 
struct P { int r, c; };
 
int n;
int g[101][101];
int checked[101][101];
 
int dr[]={1, 0, -1, 0};
int dc[]={0, 1, 0, -1};
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
bool safe(int r, int c)
{
    return (0 <= r && r < n) && (0 <= c && c < n);
}
 
void dfs(queue<P> &q, int r, int c, int cnt)
{
    g[r][c] = cnt;
 
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc)) {
            if(g[nr][nc] == 1) { 
                dfs(q, nr, nc, cnt);
            }
            else {// g[nr][nc] == 0
                if(!checked[nr][nc]) {   
                    q.push((P){nr, nc});
                    checked[nr][nc] = 1;
                }
            }
        }
    }
}
 
int bfs(queue<P> &q, int cnt)
{
    while(!q.empty()) {
        int curR = q.front().r;
        int curC = q.front().c; q.pop();
 
        for(int k=0; k<4; k++) {
            int nr = curR + dr[k];
            int nc = curC + dc[k];
            if(safe(nr, nc) && g[nr][nc] != cnt && !checked[nr][nc]) {
                checked[nr][nc] = checked[curR][curC]+1;
                q.push((P){nr, nc});
                if(g[nr][nc] != 0) {
                    return checked[curR][curC];
                }
            }
        }
    }
    return 1e9;
}
 
int main()
{
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%d", &g[i][j]);
 
    int cnt = 1;
    int ans = 1e9;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(g[i][j] == 1) {
                cnt++;
 
                queue<P> q;
                dfs(q, i, j, cnt); 
 
                int tmp = bfs(q, cnt);
                ans = min(ans, tmp);
 
                memset(checked, 0, sizeof(checked));                
            }                
        }
    }
    printf("%d\n", ans);
}
cs


>> 일단 하나의 섬을 하나의 컴퍼넌트로 체크를 하고, 섬 주위의 바다(0) 을 큐에 담는다.

>> 큐에 담긴 바다를 시작으로 거리를 잰다. 이때 현재섬이 아닌 섬을 만난 경우, 현재섬으로부터의 최소거리가 되므로 그 거리를 리턴한다.

>> 현재섬에는 cnt 값이 들어있다.



[]



[2573] 빙산 : http://boj.kr/2573 


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 <cstdio>
#include <queue>
using namespace std;
 
struct P { int r, c; };
struct M { int r, c, cnt; };
 
int r, c;
int g[301][301];
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int visited[301][301];
 
queue<P> q;
 
void dfs(int i, int j, int &ans)
{
    visited[i][j] = ans;
    
    for(int k=0; k<4; k++) {
        int ni = i+dr[k];
        int nj = j+dc[k];
        if(g[ni][nj] && visited[ni][nj]!=ans)
            dfs(ni, nj, ans);
    }
}
 
int solve(int sum)
{
    int ans=0;
    while(sum) {
        ans++;
        queue<M> mq;
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int cnt = 0;
            for(int k=0; k<4; k++) {
                int nr = curR + dr[k];
                int nc = curC + dc[k];
                if(!g[nr][nc]) cnt++;
            }
            mq.push((M){curR, curC, cnt});    
        }
 
        while(!mq.empty()) {
            int curR = mq.front().r;
            int curC = mq.front().c;
            int cnt = mq.front().cnt; mq.pop();
 
            if(g[curR][curC] > cnt) {
                q.push((P){curR, curC});
                g[curR][curC] -= cnt;
                sum -= cnt;
            }
            else {
                sum -= g[curR][curC];
                g[curR][curC] = 0;
            }
        }
 
        int cnt=0;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(g[i][j] && visited[i][j]!=ans) {
                    cnt++;
                    dfs(i, j, ans);
                    if(cnt == 2) return ans;
                }
            }
        }
    } 
    return 0;
}
 
int main()
{
    scanf("%d%d", &r, &c);
 
    int sum = 0;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            scanf("%d", &g[i][j]);
            if(g[i][j]) q.push((P){i, j});
            sum += g[i][j];
        }
    }
 
    printf("%d\n", solve(sum));
}
cs


>> 1년전엔 그렇게나 틀렸는데, 이번엔 바로 풀었다. (한번 틀렸는데, 문제 이해를 잘못해서...)

>> 빙산을 일단 q에 담고, 주변에 바다가 얼마나 둘러싸여있는지 mq 에 담은 다음, 녹인다. 그리고 섬이 분리가 되었는지 확인한다.


[4179] 불! : http://boj.kr/4179


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

Week 1 - DP1  (0) 2018.06.26
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-2 : ArrayList

Tutoring/18-1 DS2018. 4. 5. 23:21

< 숙제 Review >


- common(n) : 양의 정수 n에 대해여 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)
{
    if(n/1000 == 0) {
        printf("%d", n);
        return ;
    }
    comma(n/1000);
    printf(",%03d", n%1000);
    
}
 
int main()
{
    int n;
    scanf("%d", &n);
    
    if(n < 0) { printf("-"); n = -n; }
    comma(n);
 
    return 0;
}
cs


- n-3 자리에 대해 콤마를 찍고 출력한 다음, 콤마를 찍고 나머지 세자리를 출력하면 된다.

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

- 음수에 대한 예외처리는 19번 라인처럼 하면 될 것 같다.



< Tutoring >


- ArrayList


1) 구조체를 이용한 ArrayList 모델링하기.

1
2
3
4
5
6
#define MAX 100
 
typedef struct {
    int list[MAX];
    int len;
} ArrayList;
cs


>> 멤버 len 은 배열에 들어있는 데이터의 갯수..!!



2) init() 를 통한 초기화

1
2
3
4
void init(ArrayList *plist)
{
    plist->len = 0;
}
cs


>> C++ 에서 객체 생성시 생성자의 역할을 한다고 보면 된다.

>> 처음에 무엇을 초기화 해야할지 고민해보자..!



3) isEmpty(), isFull() 함수.

1
2
3
4
5
6
7
8
9
int isEmpty(ArrayList *plist)
{
    return plist->len == 0;
}
 
int isFull(ArrayList *plist)
{
    return plist->len == MAX;
}
cs


>> 배열 요소의 갯수가 0개면 비어있는 상태.

>> len 의 갯수가 MAX 개면 가득 찬 상태..!!



4) 특정 위치에 데이터 삽입

1
2
3
4
5
6
7
8
9
10
void add(ArrayList *plist, int pos, int data)
{
    if(isFull(plist)) return ; 
    if(!(0 <= pos && pos <= plist->len)) return ;
    
    for(int i=plist->len-1; i>=pos; i--)
        plist->list[i+1] = plist->list[i];
    plist->list[pos] = data;
    plist->len++;
}
cs


>> 3 : 데이터가 가득차있으면 삽입 불가능.

>> 4 : 컨트롤 할 수 있는 인덱스의 범위를 벗어나면 삽입 불가능.


>> 6, 7 : 데이터를 중간에 삽입하는 경우, 삽입할 위치의 데이터부터 마지막 데이터까지 한칸씩 뒤로 밀어야 한다. 

>> 데이터를 뒤로 한칸씩 옮길때는 마지막 데이터부터 옮겨야 한다. (값의 복사)

>> 8 : 원하는 위치에 데이터를 저장하는 코드.

>> 9 : 데이터를 삽입햇으므로 갯수 증가시키기.



5) 특정 위치의 데이터 삭제.

1
2
3
4
5
6
7
8
9
10
11
12
int del(ArrayList *plist, int pos)
{
    int ret;
    if(isEmpty(plist)) return -9999;
    if(!(0 <= pos && pos < plist->len)) return -9999;
    
    ret = plist->list[pos];
    for(int i=pos; i<plist->len-1; i++)
        plist->list[i] = plist->list[i+1];
    plist->len--;
    return ret;
}
cs


>> 5 : pos <= plist->len 이 아니다. 등호(=)가 빠져야 한다..!!

>> 8, 9 : 값을 왼쪽으로 한칸씩 옮긴다. 마지막 위치의 데이터는 신경안써도 된다. 

>> plist->len 을 통해 유효한 데이터의 위치를 계산할 수 있다..!!



'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
Week 2-1 : How to code Recursive function2  (0) 2018.04.04
Week 1-2 : How to code Recursive function  (0) 2018.03.30
Week 1-1 : C Lang review  (0) 2018.03.28

scanf() 에서 공백을 포함한 문자열 입력받기

Language/C2018. 4. 5. 00:21

- 공백을 포함한 문자열 입력받기 


scanf("%[^\n]\n", s);


- 문자열 입력 조건을 통하여 처리하는 방법으로 문자열 조건은 [] 를 통하여 넣을 수 있다.

- ^ 는 제외를 의미. 즉 \n를 제외한 문자열을 입력받고 문자열의 끝은 \n 로 처리하는 문자열이란 뜻이 된다.



- 문자열 조건 관련 몇몇 예제


1)

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main() 
{
    char str[100];
    scanf("%[12345]s", str);
    printf("%s\n", str);
    return 0;
}
cs

>> 4567 을 입력하면 45가 출력된다.


2)

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main() 
{
    char str[100];
    scanf("%[^12345]s", str);
    printf("%s\n", str);
    return 0;
}
cs

>> 6745 를 입력하면 67이 출력된다.

>> ^ 는 []안의 문제를 제외한 나머지 문자만 인식한다.


3) 

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main() 
{
    char str[100];
    scanf("%[0-9]s", str);
    printf("%s\n", str);
    return 0;
}
cs


>> 0-9 는 0123456789 를의미한다.

>> 123ab 를 입력하면 123이 출력된다.

>> 1a2b3c 를 입력하면 1만 출력된다.

>> ab123 을 입력하면 이상한 결과가 나온다...


4)

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main() 
{
    char str[100];
    scanf("%[a-zA-Z]s", str);
    printf("%s\n", str);
    return 0;
}
cs


>> 영문자만 입력을 받는다.



줄바꿈을 입력받지 않기 때문에, 편리한 방법이지만, 각 줄의 앞 뒤에 있는 공백은 무시하고 입력을 받아들이게 된다.

- 따라서 빈 줄은 입력받을 수 없다.

- 또한, 공백으로 시작하는 경우, 공백을 무시하고 문자부터 입력받게 된다.



참고1 : 백준 슬라이드


참고2 : http://blog.daum.net/_blog/BlogTypeView.do?blogid=09ehJ&articleno=18230445&categoryId=789155

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

비트 연산을 이용한 정수의 산술연산 (분석은 아직..)  (0) 2018.06.04
printf() 서식문자 %g  (0) 2018.03.07
배열에서 배열의 크기 이상의 인덱스를 사용하게 되면...  (0) 2018.02.27

Week 03

Tutoring/18-1 C Lang2018. 4. 4. 18:51

< 180404 >


1) 과제풀이.


1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    int t, s;
    int bits, bytes;
    scanf("%d%d", &t, &s);
 
    bits = 2 * t * s * 4000;
    bytes = bits/8;
    return 0;
}
cs


>> 7 : scant() 에서 %d 는 10진수 정수를 입력받기 위한 서식문자.

>> 7 : &변수명 인 경우, &는 변수의 주소를 반환해주는 연산자..!!



2) %d 와 %c ..

- 숫자를 입력하고, 엔터를 친 다음, 문자를 입력하고 엔터를 쳤을때, 어떤 결과를 원한다.

- 아래 코드의 문제점은..??


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    int n;
    char ch;
 
    scanf("%d", &n);
    scanf("%c", &ch);
 
    printf("%d %c\n", n, ch);
    printf("End\n");
 
    return 0;
}
cs

 

>> 숫자를 입력하고 엔터를 치면, 해당 숫자는 n에 저장되는데, 

     다음에 문자를 치기전에 쳤던 엔터도 문자로 인식이 되어 %c 에 저장이 된다.


- 해결책 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main()
{
    int n;
    char ch;
 
    scanf("%d", &n);
    getchar();
    scanf("%c", &ch);
 
    printf("%d %c\n", n, ch);
    printf("End\n");
 
    return 0;
}
cs


>> 스캔에프 사이에 getchar() 을 추가한다. 이유가 궁금하면 검색을... 

     getchar() 을 검색하기전에 '입력버퍼' 라는 것에 대해 검색을 먼저 해보자.


- 해결책2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    int n;
    char ch;
 
    scanf("%d", &n);
    scanf(" %c", &ch);
 
    printf("%d %c\n", n, ch);
    printf("End\n");
 
    return 0;
}
cs


>> 9 : "%c" 를 " %c" 라 바꿧다. 즉 빈칸이 엔터키를 포함시켜, 정상적으로 문자를 입력받을 수 있게된다. 

>> 이 원리가 궁금하면 스캔에프 사용법에 대해 검색을 해보자..

>> 해결책 2를 권함..^^



3) 입력 프롬프트에서 1을 입력했다. 프로그램은 이 1이란 것을 숫자 1인지, 문자 '1' 인지 어떻게 구분을 하여 저장을 할까??


1
2
3
scanf("%d", &n);
 
scanf("%c", &ch);
cs


>> 서식문자를 무엇으로 지정했는지에 따라 구분이 가능하다.



4) 10진수 정수를 입력받아, 8진수, 16진수로 출력하기. 문자를 입력받아 그 문자의 아스키코드값 출력하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
int main()
{
    int n;
    char ch;
 
    scanf("%d", &n);
    printf("10진수: %d\n", n);
    printf("8진수: %o\n", n);
    printf("16진수: %x\n", n);
 
    printf("\n");
    scanf(" %c", &ch);
    printf("%c의 ASCII 코드값: %d\n", ch, ch);
 
    return 0;
}
 
cs


>> 실행결과

1
2
3
4
5
6
7
10
10진수: 10
8진수: 12
16진수: a
 
A
A의 ASCII 코드값: 65
cs



5) 10진수 vs 8진수 vs 10진수


10진수 : 1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17 ...

 8진수 : 1    2    3    4    5    6    7    10   11    12    13    14    15    16   17    20   21 ...

16진수 : 1    2    3    4    5    6    7    8    9    10    A    B    C    D    E    F    G    10 ...



6) 4자리 정수(1000 ~ 9999) 까지의 정수를 입력받았을 때, 이를 거꾸로 출력해보기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int main()
{
    int n, res;
    scanf("%d", &n);
 
    res = n%10;
    n /= 10;
 
    res = res*10 + n%10;
    n /= 10;
 
    res = res*10 + n%10;
    n /= 10;
    
    res = res*10 + n%10;
    printf("%d\n", res);
    return 0;
}
cs


>> 1234 를 입력하면, 4321 이 출력된다.

>> 8 : res 에는 4가 저장된다.

>> 9 : n 에는 123 이 들어있다.

>> 11 : res 에는 43 이 저장된다.

>> 12 : n 에는 12 가 저장된다.

>> 14 : res 에는 432 가 저장된다.

>> 15 : n 에는 1 이 저장된다.

>> 17 : res 에는 4321 이 저장된다.



7) 증감 연산자. a++ vs ++a


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    int a, b, c;
 
    a = 5;
    b = a++;
    c = ++a + b++;
    printf("%d %d %d\n", a, b, c);
 
    return 0;
}
cs


>> 실행결과 : 7 6 12


>> 8라인이 끝나기 전에는 a에는 5가, b에도 5가 저장되어 있다. 

>> 8라인이 끝나고 나서야 a에 값이 6으로 증가한다.


>> 9번 라인이 끝나기 전에는 a는 1이 증가한 7이, b에는 5가, c에는 그 둘의 합인 12가 저장된다.

>> 9번 라인이 끝나고 나서야 b의 값은 1이 증가하여 6이된다.


>> 그렇기 때문에 10라인에서 최종적으로 7 6 12 라는 결과가 출력된다. 



8) scanf() 에서의 서식문자 %lf vs %f


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>
 
int main() 
{
    float 키1, 키2, 키3, 키4;
    char 혈1, 혈2, 혈3, 혈4;
 
    printf("학생1의 키와 혈액형:");
    scanf("%f %c", &키1,&혈1);
  
    printf("학생2의 키와 혈액형:");
    scanf("%f %c", &키2, &혈2);
    
    printf("학생3의 키와 혈액형:");
    scanf("%f %c", &키3, &혈3);
    
    printf("학생4의 키와 혈액형:");
    scanf("%f %c", &키4, &혈4);
    
    printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4);
    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
#include <stdio.h>
 
int main() 
{
    double 키1, 키2, 키3, 키4;
    char 혈1, 혈2, 혈3, 혈4;
 
    printf("학생1의 키와 혈액형:");
    scanf("%f %c", &키1,&혈1);
  
    printf("학생2의 키와 혈액형:");
    scanf("%f %c", &키2, &혈2);
    
    printf("학생3의 키와 혈액형:");
    scanf("%f %c", &키3, &혈3);
    
    printf("학생4의 키와 혈액형:");
    scanf("%f %c", &키4, &혈4);
    
    printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4);
    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
#include <stdio.h>
 
int main() 
{
    double 키1, 키2, 키3, 키4;
    char 혈1, 혈2, 혈3, 혈4;
 
    printf("학생1의 키와 혈액형:");
    scanf("%lf %c", &키1,&혈1);
  
    printf("학생2의 키와 혈액형:");
    scanf("%lf %c", &키2, &혈2);
    
    printf("학생3의 키와 혈액형:");
    scanf("%lf %c", &키3, &혈3);
    
    printf("학생4의 키와 혈액형:");
    scanf("%lf %c", &키4, &혈4);
    
    printf("평균 키:%.1lf\n", (키1 + 키2 + 키3 + 키4) / 4);
    return 0;
}
cs


>> 원하는 결과가 출력될 것이다.


>> 결론 : scarf() 에서의 서식문자 %lf 는 double 형 변수에 , %f 는 float 형 변수에 맞는 서식문자이다.



9) 기타


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int main() 
{
    int a=20, b=10;
 
    a = a+b;
    a += b;
 
    a = a-b;
    a -= b;
 
    a = a*b;
    a *= b;
 
    a = a/b;
    a /= b;
 
    return 0;
}
cs


>> 7, 8과 10, 11과 13, 14와 16, 17은 같은 연산이다.


- printf() 함수를 통해 %를 출력하고 싶으면 %% 를 써야한다.


1
2
3
4
5
6
7
#include <stdio.h>
 
int main() 
{
    printf("%d%%\n", 10);
    return 0;
}
cs


>> 실행결과 : 10%

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 06  (0) 2018.04.23
Week 05  (0) 2018.04.18
Week 04  (0) 2018.04.11
Week 02  (2) 2018.03.28
Week 01  (0) 2018.03.21

티스토리툴바