략간스트,, 처음에 문제 파악(?)하는데 쬐에끔 걸렸다ㅋㅋㅋ

말 그대로 숫자를 N개대로 입력 받고, 합쳐서 M이 나오는 경우의 수를 구하는 것인데, 연속된 숫자들을 합했을 때 M이 나오는 경우의 수이다. 근데 지금 보니까 문제를 잘못 풀은 것 같다. 전부 예전에 풀었던 문제들을 다시 공부하는 차원에서 정리하는 중인데 '투 포인터'라는 개념을 사용해서 풀어야 하는 것 같다. 일단은 내가 풀었던 코드 정리 한 번하고 다음에 다시 투 포인터라는 개념을 가지고 풀어봐야겠다.



나는 그냥 배열에 때려박았숨다. >.<

문제에서는 입력받을 숫자갯수는 N, 연속된 수의 합은 M으로 지정했는데 코드에서는 num과 sum으로 선언했다.(N = num, M = sum)

그냥 차례대로 더하면서(이 숫자는 sum_에 저장) sum과 같아지면 count++해 주고 sum을 넘기면 한칸 옆으로 넘어가서(k++) 다시 숫자들을 연속적으로 합해주었다. 참 쉽죠잉...?ㅎ... 


그르니께 그림으로 간단하게 설명하자면 다음과같이 k가 num-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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int main(void) {
    //num은 입력받을 숫자 갯수, sum은 연속된 숫자들의 합, arr은 입력받을 숫자들을 저장할 배열
    int num, sum, *arr; 
    scanf("%d %d", &num, &sum);
 
    //배열의 크기를 할당해 주고 배열에 숫자들을 저장해 줌
    arr = (int *)malloc(num * sizeof(int));
    for (int i = 0; i < num; i++)
        scanf("%d", &arr[i]);
    
    //k는 시작점, sum_은 연속된 숫자들의 합, count는 경우의 수
    int k = 0, sum_, count = 0;
 
    //k는 배열의 마지막까지 옮겨가야함
    while (k < num) {
 
        //sum_을 0으로 초기화 시킴
        sum_ = 0;
 
        //인덱스k번째부터 배열의 숫자들을 더해
        for (int i = k; i < num; i++) {
            sum_ += arr[i];
 
            //sum과 같아지면 count++해 주고 for문을 빠져나감
            if (sum_ == sum) {
                count++;
                break;
            }
            
            //sum보다 커지면 더 이상 더해 줄 필요가 없으므로 for문을 빠져나감
            else if (sum_ > sum)
                break;
        }
        
        //시작점을 한 칸 옆으로!
        k++;
    }
    printf("%d", count);
    free(arr);
    return 0;
}
 
cs


흑... 알고리즘 공부 좀 열심히해야겠다...




'백준' 카테고리의 다른 글

백준 알고리즘 2750번 수 정렬하기  (0) 2019.01.30
백준 알고리즘 10845번 큐  (0) 2019.01.26
백준 알고리즘 1011번 Fly me to the Alpha Centauri  (0) 2019.01.26
백준 알고리즘 9012번 괄호  (0) 2019.01.15
백준 알고리즘 1991번 트리순회  (0) 2019.01.08


오늘은 좀 많이 쉬운 문제를 가지고 왔다. 정렬할 숫자 갯수(n)를 먼저 입력 받고 그 다음 숫자를 무작위로 n개 만큼 입력 받은 후 그 숫자들을 오름차순으로 정렬하는 문제이다!


n개의 숫자들은 배열에 입력 받아 저장하였다.

그 배열은 크기를 알 수 없기 때문에 동적할당을 해주었당.

malloc을 사용하는게 좋을 것 같아서 일부러 자주 사용하려고 노력하는 편이다...

내가 잘 알고 그런건 아니지만 무조건 arr[1000]이런식으로 해 주는 것 보다는 동적할당을 통해서 크기를 먼저 할당해주고 나중에 해제하는 방식이 나은 것 같아서 일부러 신경써서 더 사용해 주려고 한다(이게 맞는 건지는 잘 모르겠지만 ㅎ)


여튼 알고리즘은

0번 부터 n-2번째까지 n-1번을 반복을 하는데, 무엇을 반복하느냐하면,

1번 부터 n-1번째(배열의 맨 마지막) 저장 된 숫자를 비교한다.

아래 그림과 같이 하면 된다!

아래 그림이 0번째부터 n-2번까지 반복하는 것 중 한 번(분홍색 한 번)을 완료한 것이다.


다시 말해 0번 인덱스를 1번부터 n-1번까지의 인덱스와 비교 한다.

다음은 1번 인덱스를 2번부터 n-1번까지의 인덱스와 비교한다.

그 다음은 2번 인덱스를 3번부터 n-1번까지의 인덱스와 비교한다.


이렇게 반복해서 마지막으로

n-2번 인덱스를 n-1번 인덱스와 비교한다.


비효율적이다.

비효율적이지만 코드는 쉽다.

여튼 나는 이렇게 무식한 알고리즘으로 풀었다ㅋㅎㅋㅎ


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(void)
{
    int n;
    scanf("%d", &n);
    int *arr=(int*)malloc(n*sizeof(int)); 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    for (int i = 0; i < n-1; i++) {
        for (int j = i + 1; j < n; j++)
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", arr[i]);
    free(arr);
}
cs


정렬문제가 두 개가 더 있는데 다음엔 이런 무식한 방법으루다가 말구~

다른 방식으로 풀이해보겠담~!

'백준' 카테고리의 다른 글

백준 알고리즘 2003 수들의 합2  (0) 2019.02.22
백준 알고리즘 10845번 큐  (0) 2019.01.26
백준 알고리즘 1011번 Fly me to the Alpha Centauri  (0) 2019.01.26
백준 알고리즘 9012번 괄호  (0) 2019.01.15
백준 알고리즘 1991번 트리순회  (0) 2019.01.08

이번에는 정답률 높은 큐 입니당



책으로 공부 꼼꼼하게 한 다음에 풀어봤던 문제여서 그런지 그때 당시에는 막힘없이 술술 코드를 썼었눈데,,,

지금 다시 해보라카믄 잘 할 수 있을런즤

사실 스택 큐는 당연히 기본적으로 술술 해야하는곤데,,, ^^(쥬륵)


<함수 설명>

* 내가 생각하기에 구조체 짜는것(?)이 중요한 것 같다. 그러면 함수는 술술 만들어지는 것 같당,,,(아님말공)

* 맨날 헷갈림 : pop는 front에서 push는 rear로


1. Queue 구조체 : max부터 차례대로 큐의 크기, 큐에 들어있는 데이터 갯수, rear, front, 큐에 저장될 데이터 배열을 말한다.

2. Initialize : 큐를 초기화 해주는 함수이다. 큐를 빈 상태로, 크기만 할당해 줍니당.

3. Enque : 이름 그대로 큐에 데이터를 삽입하는 함수이다. 큐에 들어있는 데이터 갯수(num)와 큐의 크기(max)가 같으면 큐가 가득 찼다는 의미이므로 enqueue가 불가능하기 때문에 -1을 반환해서 가득 찼음을 알린다.  스택코드에서도 그랬던 것처럼, q->num >= p->max 에서 >=라고 해 준 이유는, =만 써주어도 되지만 오류를 방지하기 위함이다. 큐가 가득차지 않았을 경우에는 큐 배열에 데이터가 추가 되었기 때문에 갯수(q->num)를 ++해 주고 큐는 push될 때 rear로 추가 되기 때문에 q->que[q->rear]에 데이터를 대입하고 rear를 ++해준다.

또한 else문 안의 if는 마지막 데이터(x)를 대입함으로서 큐가 가득찼을 때를 의미한다.

4. Deque : 마찬가지로 큐에서 데이터를 pop하는 함수이다. 큐에 아무것도 들어있지 않을 경우(que->num<=0)에는 pop할 수 없기 때문에 -1을 반환해준다(이 함수에서는 -1을 출력해 줌). 큐가 비어있지 않을 경우에는 데이터를 없애야하기 때문에 q->num을 --해준당. 또한 pop될때에는 front에서 데이터가 빠져나가기 때문에 q->front는 ++해준다! (헷갈리지 말자)

5. back : 맨 마지막 데이터 즉, 가장 나중에 들어온 데이터 출력하는 함수이다. rear-1을 해 주는 이유는 rear는 맨 마지막 데이터 다음을 가리키기 때문이다.

6. front : 맨 앞의 데이터 즉, 가장 먼저 들어온 데이터 출력하는 함수이다.

7. size : 데이터가 저장 된 큐의 크기 구하는 함수이다.

8. IsEmpty : 큐가 비어있는지의 여부를 알 수 있는 함수이다. 비어있으면 1, 아니면 0을 출력한다.

9. Isfull : 큐가 가득 차있는지의 여부를 알 수 있는 함수이다. 가득차 있으면 1, 아니면 0을 출력한다.

10. main : push, pop등 문자열 명령(?)들을 입력받아서 배열 ans1[]에 저장하여 strcmp함수로 비교하여 맞는 명령의 조건문(if)에서 함수를 사용하여 명령을 실행한다. 처음에 입력 받은 숫자만큼 명령을 입력 받고 실행해야하기 때문에 while문을 이용하였다.


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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10000
 
typedef struct {
    int max;
    int num;
    int rear;
    int front;
    int *que;
}Queue;
 
int Initialize(Queue *q, int max) {
    q->num = q->front = q->rear = 0;
    if ((q->que = (int*)calloc(max, sizeof(int))) == NULL) {
        q->max = 0;
        return -1;
    }
    q->max = max;
    return 0;
}
 
int Enque(Queue *q, int x) {
    if (q->num >= q->max)
        return -1;
    else {
        q->num++;
        q->que[q->rear++] = x;
        if (q->rear == q->max)
            q->rear = 0;
        return 0;
    }
}
 
void Deque(Queue *q, int *x) {
    if (q->num <= 0)
        printf("%d\n", -1);
    else {
        q->num--;
        *x = q->que[q->front++];
        if (q->front == q->max)
            q->front = 0;
        printf("%d\n", *x);
    }
}
 
void back(Queue *q) {
    if (q->num <= 0)
        printf("%d\n", -1);
    else
        printf("%d\n", q->que[q->rear-1]);
}
 
void front(Queue *q) {
    if (q->num <= 0)
        printf("%d\n", -1);
    else
        printf("%d\n", q->que[q->front]);
}
 
void size(Queue *q) {
    printf("%d\n", q->num);
}
 
void IsEmpty(Queue *q) {
    if (q->num <= 0)
        printf("%d\n", 1);
    else
        printf("%d\n", 0);
}
 
int IsFull(Queue *q) {
    return q->num >= q->max;
}
 
int main() {
    Queue q;
    int ans = 0, input = 0;
    char ans1[] = "empty";
    ans1[0] = '\0';
 
    Initialize(&q, MAX);
    scanf("%d", &ans);
 
    while (ans > 0) {
        scanf("%s", ans1);
 
        if (strcmp(ans1, "push") == 0) {
            scanf("%d", &input);
            Enque(&q, input);
        }
        else if (strcmp(ans1, "pop") == 0)
            Deque(&q, &input);
 
        else if (strcmp(ans1, "size") == 0)
            size(&q);
 
        else if (strcmp(ans1, "empty") == 0)
            IsEmpty(&q);
 
        else if (strcmp(ans1, "front") == 0)
            front(&q);
 
        else if (strcmp(ans1, "back") == 0)
            back(&q);
 
        ans--;
    }
    return 0;
}
cs


'백준' 카테고리의 다른 글

백준 알고리즘 2003 수들의 합2  (0) 2019.02.22
백준 알고리즘 2750번 수 정렬하기  (0) 2019.01.30
백준 알고리즘 1011번 Fly me to the Alpha Centauri  (0) 2019.01.26
백준 알고리즘 9012번 괄호  (0) 2019.01.15
백준 알고리즘 1991번 트리순회  (0) 2019.01.08

<다시 편집할 예정!>



이 문제 또한 너무 오래 전에 풀어서 지금 다시 보니까 새롭지만 복습 차원에서 한번 보겠다 ㅋㅎㅋㅎ

이건 근데 문제읽어보고 숫자를 쫘악 나열해보고 거기서 규칙만 찾으면 간단하게 구현할 수 있었던 문제였다.

그 규칙 찾는게 오래 걸리고 귀찮았던 것 같당

숫자 쫙 나열해보면서 에 설마 여기에 규칙이 있겠어 하면서 숫자 조금만 써보고 말아서 규칙 찾기까지가 은근히 걸렸당

앞으로는 귀찮아 하지 말자...!




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <math.h>
 
int main() {
    int x, y, z, ans;
    scanf("%d", &ans);
    for (int k = 0; k < ans; k++) {
        scanf("%d %d", &x, &y);
        z = y - x;
        int i = sqrt(z);
            if ((z >= i * i - i + 1) && (z <= i * i)) {
                printf("%d\n", i + (i - 1));
            }
            else if ((z >= i * i + 1) && (z <= i * i + i)) {
                printf("%d\n", i + i);
            }
            else
                printf("%d\n", (i + 1) + i);
    }
    return 0;
}
cs


'백준' 카테고리의 다른 글

백준 알고리즘 2750번 수 정렬하기  (0) 2019.01.30
백준 알고리즘 10845번 큐  (0) 2019.01.26
백준 알고리즘 9012번 괄호  (0) 2019.01.15
백준 알고리즘 1991번 트리순회  (0) 2019.01.08
백준 알고리즘 10828번 스택  (0) 2019.01.07


ㅋㅋㅋㅌㅋㅌ갸많이 틀림,,,^^ 캬ㅑ캌캬

오래전에 풀었던거라 기억은 잘 안 나즤만서도~

복습 차원에서 한 번 끄적여 봅니다



<기본적인(?) 개념>

1. '(' 일때에는 push를, ')' 일때에는 pop를 한다.

2. 스택이 비어있을 때 pop을 하게 되면 NO를 출력한다.

3. 스택이 비어있지 않았을 때 문자열에 저장된 괄호 확인(?)이 끝나면 NO를 출력한다.

4. 스택이 비어있고, 문자열에 저장된 괄호 확인이 끝나면  YES를 출력한다.


코드 설명은 주석으로 달아 놓았습니당~!

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>
#include <stdlib.h>
#include <string.h>
#define MAX 10000
 
typedef struct {
    int    max;     //스택 배열의 최대 크기
    char *stk;     //스택 표현할 배열
    int ptr;     //현재 위치
}Stack;
 
int initialize(Stack* s, int max) {
    s->ptr = 0;
    if ((s->stk = (char*)calloc(max, sizeof(char))) == NULL) {
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}
 
int push(Stack* s, char x) {
    if (s->ptr >= s->max) //스택이 가득 차 있을 때
        return -1;
    s->stk[s->ptr++] = x;
    return 0;
}
 
int pop(Stack* s, char *x) {
    if (s->ptr <= 0) //스택이 비어있을 때
        return -1;
    *x = s->stk[--s->ptr];
    return *x;
}
 
int empty(Stack* s) { //스택이 비어있으면 1, 아니면 0
    if (s->ptr <= 0) //스택이 비어있을 때
        return 1;
    return 0;
}
 
int main(void) {
    Stack s;
    int num = 0, str;
    char ans2[50]= " ";
    //가장 먼저 숫자를 입력 받는다.
    scanf("%d", &num);
 
    //입력받은 숫자(num)만큼 반복
    while (num > 0) {
        //스택 초기화
        initialize(&s, MAX);
        //괄호 문자열을 입력받고 str에 문자열의 길이를 저장한다.
        scanf("%s", ans2);
        str = strlen(ans2);
        
        //입력받은 괄호 문자열을 처음부터 문자열 길이만큼 반복한다.
        for (int i = 0; i < str; i++) {
            //'('일 때, 스택에 push한다.
            if (ans2[i] == '(') {
                push(&s, ans2[i]);
            }
            //')'일 때, 스택이 비어있으면 NO를 출력
            else if (ans2[i] == ')') {
                if (empty(&s) == 1) {
                    printf("NO\n");
                    break;
                }
                //비어있지 않으면 pop한다.
                else
                    pop(&s, &ans2[i]);
            }
            
            //만약 문자열의 마지막 문자일 때,
            if (i == str - 1) {
                //비어있으면 YES를 출력, 비어있지 않으면 NO를 출력한다.
                if (empty(&s) == 1)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
        num--;
    }
    return 0;
}
cs



ㅜㅡㅠㅜㅡㅜㅠ휴ㅜㅠㅜ

'백준' 카테고리의 다른 글

백준 알고리즘 2750번 수 정렬하기  (0) 2019.01.30
백준 알고리즘 10845번 큐  (0) 2019.01.26
백준 알고리즘 1011번 Fly me to the Alpha Centauri  (0) 2019.01.26
백준 알고리즘 1991번 트리순회  (0) 2019.01.08
백준 알고리즘 10828번 스택  (0) 2019.01.07


풀면서 뜬금없이 scanf에서 애 먹었던 문제이다 ㅡㅡ



코드에 대한 세부적인 설명은 코드에 주석으로 달아놨습니당~!

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    char data;
    struct Node *left;
    struct Node *right;
}node;
 
//노드생성 함수
node* Create(char x) {
    node* newNode = (node*)malloc(sizeof(node));
 
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->data = x;
 
    return newNode;
}
 
void preorder(node* t) {
    if (t == NULL)
        return;
    
    printf("%c", t->data);
    preorder(t->left);
    preorder(t->right);
}
 
void inorder(node* t) {
    if (t == NULL)
        return;
    
    inorder(t->left);
    printf("%c", t->data);
    inorder(t->right);
}
 
void postorder(node* t) {
    if (t == NULL)
        return;
    
    postorder(t->left);
    postorder(t->right);
    printf("%c", t->data);
}
 
int main() {
    node * root[27];
    int num;
    char a, b, c, arr[81][2];
 
    scanf("%d", &num);
    
    for (int i = 0; i < num; i++) {
        //노드갯수와 각 노드의 자식노드를 입력받아 arr배열에 저장
        scanf(" %c %c %c", &a, &b, &c);
        arr[i][0] = b;    arr[i][1] = c;
        //num개의 노드 각각 생성
        root[i] = Create(a);
    }
 
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            //arr배열의 0번째 열에 저장된 값은 노드의 왼쪽 자식 노드가 된다.
            //배열에 저장된 값과 노드의 데이터(root->data)가 같을 때 그 노드를 왼쪽 자식노드로 저장 
            if (arr[i][0] == root[j]->data)
                root[i]->left = root[j];
            //arr배열의 1번째 열에 저장된 값은 노드의 오른쪽 자식 노드가 된다.
            //배열에 저장된 값과 노드의 데이터(root->data)가 같을 때 그 노드를 오른쪽 자식노드로 저장 
            if (arr[i][1] == root[j]->data)
                root[i]->right = root[j];
        }
    }
 
    preorder(root[0]);
    printf("\n");
    inorder(root[0]);
    printf("\n");
    postorder(root[0]);
 
    return 0;
}
cs


문제를 풀 때 57번째 줄인 scanf(" %c %c %c", &a, &b, &c);를 첫번째 %c앞에 공백 없이 scanf("%c %c %c", &a, &b, &c); 와 같은 방식으로 써주었더니 에러가 났다. 

이유를 찾아보았다. 컴퓨터는 Enter값도 입력값으로 받아들여서 버퍼에 Enter값이 추가된다고 한다. 그렇기 때문에 내가 사용한 코드는 scanf를 for문으로 반복했기 때문에 Enter값이 다음 scanf의 %c에 입력이 되는 것이다. 그런데 %c앞에 공백을 주면 구분자로 간주하여 오류가 생기지 않는다고 한다. 


문제 푸는 당시에 도저히 해결이 안돼서 게시판에 질문까지 올렸당 ㅠㅠ 나중에라도 또 이런식으로 갈팡질팡할 상황이 올 것 같아서 정리해 보았다... 아래는 내가 올렸던 질문에 대해 받았던 답변이다.



<<줄 바꿈 정의>>

carriage return(\r) : 현재의 위치를 나타내는 커서의 위치를 앞으로 이동한다.

line feed(\n) : 현재 위치에서 바로 아래로 이동한다.

윈도우에서 사용하는 Enter은 CR+LF가 된다.


'백준' 카테고리의 다른 글

백준 알고리즘 2750번 수 정렬하기  (0) 2019.01.30
백준 알고리즘 10845번 큐  (0) 2019.01.26
백준 알고리즘 1011번 Fly me to the Alpha Centauri  (0) 2019.01.26
백준 알고리즘 9012번 괄호  (0) 2019.01.15
백준 알고리즘 10828번 스택  (0) 2019.01.07

+ Recent posts

티스토리툴바