0이면 콩이 심어진 상태, 1이면 콩이 없는 상태이다.


배열에 모두 콩을 심어놓고, 배열을 탐색하면서 거리가 2인곳에 위치한 콩을 제거해준다.



'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

5356. 의석이의 세로로 말해요(D3)  (0) 2018.08.31
5432. 쇠막대기 자르기(D4)  (0) 2018.08.31
5431. 민석이의 과제 체크하기(D3)  (0) 2018.08.31
3074. 입국심사(D4)  (0) 2018.08.09
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09

그냥 주어진 조건대로 배열을 세로로 접근해서 출력하면 된다.

이때, 쓰레기값이나 '\n'이 저장되어있으면 PASS하면 된다.



'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

4301. 콩 많이 심기(D4)  (0) 2018.08.31
5432. 쇠막대기 자르기(D4)  (0) 2018.08.31
5431. 민석이의 과제 체크하기(D3)  (0) 2018.08.31
3074. 입국심사(D4)  (0) 2018.08.09
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09

() 이렇게 괄호 열고 닫는 문자가 바로 붙어서 나오는 경우는 레이저다.


그러므로 '('를 입력받으면 먼저 막대로 파악하고 개수를 카운트해준다.


입력에서 이전에 '('를 입력받았고, 그다음 ')'을 입력받으면 레이저로 판단하고, 현재 막대 개수만큼 조각을 카운트 해준다. ( 이전에 '('입력으로 카운트 해준 값이 막대기가 아니고 레이저 입력이므로 하나 빼줘야한다)




'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

4301. 콩 많이 심기(D4)  (0) 2018.08.31
5356. 의석이의 세로로 말해요(D3)  (0) 2018.08.31
5431. 민석이의 과제 체크하기(D3)  (0) 2018.08.31
3074. 입국심사(D4)  (0) 2018.08.09
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09

vector를 이용하여 동적으로 배열을 생성한 후, 과제를 제출한 사람을 따로 체크한다.

앞에서부터 체크가 안된 번호를 출력



'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

5356. 의석이의 세로로 말해요(D3)  (0) 2018.08.31
5432. 쇠막대기 자르기(D4)  (0) 2018.08.31
3074. 입국심사(D4)  (0) 2018.08.09
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09
3066. 팀 정하기(D7)  (0) 2018.08.09

비트 연산은 우선순위가 낮은 편이기 때문에 원하는 위치에 괄호를 작성하여 정확하게 계산할 수 있도록 하는게 중요하다.



C++에서 1은 부호있는 32비트 상수이기  때문에, 64비트를 사용할 때에는 1뒤에 ull을 붙여줘야 제대로 인식한다.


unsigned long long bit = (1ull<<40)-1; (O) -> 1099511627775


unsigned long long bit = (1<<40)-1; (X) -> 18446744073709551615



공집합( 모든 비트가 0)

unsigned int bit = 0;


꽉찬 집합(모든 비트가 1)


unsigned int bit = (1<<n) - 1;


사용할 비트 수만큼 왼쪽으로 시프트한 다음 1을 빼면 된다.


unsigned int bit = (1<<32) - 1; -> 1111 1111 1111 1111 1111 1111 1111 1111



기존 비트에서 원하는 비트의 위치를 1로 바꾸기

비트를 1로 바꿀 만큼 왼쪽으로 시프트 시킨 후 , or연산을 한다.

bit |= (1<<n);



특정 비트가 1인지 확인하기

if(bit & (1<<n)) -> 특정 비트가 1이면 1<<n 반환, 0이면 0 반환



기존 비트에서 원하는 비트의 위치를 0으로 바꾸기

bit &= ~(1<<n);


n번째 비트가 0이면 1로, 1이면 0으로 바꾸기

bit ^= (1<<n); -> xor 연산을 하면 가능하다.



비트에서 1의 개수 세기

1
2
3
4
5
6
int bitCount(int x)
{
    if (x == 0)
        return 0;
    return x % 2 + bitCount(x / 2);
}
cs



처음 1인 비트 찾기

int first = ( bit & -bit);

2^n의 값이 반환된다.

즉 10진수 240 은 1111 0000로, 처음 1은 4번째 비트에서 나타난다. 그러면 위 식에 의해 2^4 = 16의 값을 가지게 된다.


처음 1인 비트를 0으로 바꾸기


bit &= (bit -1);



모든 부분집합 탐색

처음 시작은 모든 비트가 1로 채워져있어야 한다.


1
2
3
4
for (int subset = a; subset; subset = ((subset - 1) & a))
    {
        
    }
cs



참고문헌: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

이진 탐색(Binary Search)  (0) 2018.08.08

1. 배열을 이용한 큐 구현


단순히 스택과 같이 큐를 배열을 이요하여 구현하면 아래와 같다.

문제점은 큐의 크기를 한번 다 사용하고 나면 큐는 실제로는 비어있지만 더이상 데이터를 삽입할 수가없다.

그렇기 때문에 배열을 이요할 때에는 원형 큐를 구현하게된다.




init: 큐 초기화

isEmpty: 큐가 비어있으면 1반환, 데이터가 있으면 0 반환

isFull: 큐가 가득 차있으면 1반환, 빈공간이 있으면 0반환

enqueue: 큐에 데이터 삽입

dequeue: 큐에서 데이터 추출


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isFull(queue* q)
{
    if (q->rear == MAX_SIZE)
        return 1;
    else
        return 0;
}
void enqueue(queue* q, int data)
{
    if (isFull(q))
    {
        printf("queue is full\n");
        return;
    }
 
    q->data[q->rear] = data;
    q->rear++;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    
    return q->data[q->front++];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


2. 배열을 이용한 원형 큐 구현


원형 큐의 경우, 배열을 지속적으로 사용할 수 있는 장점이 있다.

배열이 비어있는상태, 꽉차있는 상태를 구분하기 위해, 배열의 크기 - 1 만큼을 큐에서 사용한다.

front==rear인 경우 큐가 비어있는 상태이며, front-1 = rear인 경우 큐가 가득차 있는 상태이다.


isNext: 다음 인덱스를 가져오는 함수이다.


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>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isNext(int pos)
{
    if ( pos == MAX_SIZE-1)//마지막 인덱스면 첫번째로 돌아간다.
        return 0;
    else
        return pos + 1;
}
void enqueue(queue* q, int data)
{
    if (isNext(q->rear)==q->front)
    {
        printf("queue is full\n");
        return;
    }
    q->rear = isNext(q->rear);
    q->data[q->rear] = data;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    q->front = isNext(q->front);
    return q->data[q->front];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[isNext(q->front)];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


위 코드를 실행하면 아래와 같은 값이 나온다.

큐의 크기는 10이지만, 실제로 사용하는 영역은 9칸 이기 때문에, 11개의 데이터를 삽입하려고 시도하면 2번의 에러가 발생한다.




3. 리스트를 이용한 큐 구현


리스트를 사용할 경우, 데이터 삽입을 위해 리스트의 가장 마지막을 노드를 가르키는 포인터(여기서는 Tail)이 필요하다.

큐에서 데이터 삽입시 Tail 위치에 삽입하며, 삭제시 Head가 가르키는 노드를 삭제한다.




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 <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _queue {
    node* head;
    node* tail;
}queue;
 
void init(queue* q)
{
    q->head = NULL;
    q->tail = NULL;
}
 
int isEmpty(queue* q)
{
    if (q->head == NULL)
        return 1;
    else
        return 0;
}
 
void enqueue(queue* q, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
 
    newnode->data = data;
    newnode->next = NULL;
    
    if (isEmpty(q))
    {
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
 
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
 
    int ret = q->head->data;
    node* temp = q->head;
 
    q->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->head->data;
}
 
int main(void)
{
    queue q;
    init(&q);
 
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
 
    while(!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
 
    printf("queue front : %d\n", seek(&q));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

스택(stack)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

1. 배열을 이용한 스택 구현


정해진 크기의 배열에서, 배열의 크기에 여유가 있으면 데이터를 하나씩 추가한다.



init: 스택을 초기화 하는 함수. top을 가르키는 변수를 -1로 초기화 한다.

isEmpty: 스택이 비어있는지 체크하는 함수. 비어있으면 1, 비어있지 않으면 0을 반환한다.

push: 스택에 데이터를 삽입하는 함수. 스택이 가득차 있으면 더이상 추가하지 않는다.

pop: 스택에서 데이터를 추출하는 함수. 스택의 top에 에있는 데이터를 반환한다. 스택이 비어있으면 꺼내지 않는다.

seek: 스택의 top에 저장된 데이터를 반환하는 함수. 없어도 되지만 책에 있어서 추가해봤다.


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>
 
#define MAX_SIZE 10
 
typedef struct _stack {
    int data[MAX_SIZE];
    int top;
}stack;
 
void init(stack* st)
{
    st->top = -1;
}
 
int isEmpty(stack* st)
{
    if (st->top == -1)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    if (st->top == MAX_SIZE-1)
    {
        printf("stack is full\n");
        return;
    }
 
    st->data[++st->top] = data;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top--];
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top];
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs

예전에 TOP을 초기화할 땐 -1로 했던 것 같은데 요즘엔 0이 대세인 것 같기도하다.
하지만 큰 차이없으니 개인의 취향대로 구현하면 될 것이다.

2. 리스트를 이용한 스택 구현

리스트를 이용할 경우, 배열과 다른점은 top이라는 변수가 따로 없는 것이다. Head가 top과 유사한 역할을 수행한다.
또, 리스트는 제한된 크기가 없기때문에, 메모리가 허용하는 만큼의 데이터를 삽입할 수 있다.
데이터 삽입시 새로운 노드를 생성하고, 새로운 노드에 데이터 할당, NEXT는 HEAD가 가르키고 있던 노드를 할당한다.
그다음 HEAD는 새로운 노드를 가르키게 하면된다.




함수는 배열을 이용한 스택과 같다.


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _stack {
    node* head;
}stack;
 
void init(stack* st)
{
    st->head = NULL;
}
 
int isEmpty(stack* st)
{
    if (st->head == NULL)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = st->head;
    
    st->head = newnode;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
 
    int ret = st->head->data;
    node* temp = st->head;
 
    st->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->head->data;
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

이진 탐색을 이용해서 문제를 해결했다.


최대로 걸릴 수 있는시간은 주어진 심사대 중 가장 오래 걸리는 심사대 * 사람수 가 최악의 경우가 된다.


물론 심사대가 2개 이상이면 이시간 까지는 안걸리겠지만, 1개일 때도 고려하면 위 시간이 최악의 경우다.



이 시간을 기준으로 시간을 1/2 씩 탐색해가며, 모든 사람이 심사를 받고 시간도 만족하면 끝


모든사람이 심사를 못받았으면, 시간이 더 필요하므로 오른쪽 탐색


주어진 사람보다 더 많은 사람을 심사할 수 있으면, 시간이 남으므로 왼쪽 탐색하게 된다.



'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

5432. 쇠막대기 자르기(D4)  (0) 2018.08.31
5431. 민석이의 과제 체크하기(D3)  (0) 2018.08.31
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09
3066. 팀 정하기(D7)  (0) 2018.08.09
1257. [S/W 문제해결 응용] 6일차 - K번째 문자열(D6)  (0) 2018.08.09

수학의 세계는 신기하다는 것을 다시 한번 느끼게 해준 문제이다.


이 문제는 주어진 문자열을 재구성하여, 재구성한 문자열의 부분 문자열중 팰린드롬의 수가 최대일 때, 몇개인지를 계산하는 문제이다.


주어진 abcabc는 abccba로 재구성하면 a, b, c, c, b, a, cc, bccb, abccba로 9개가 나온다.

이 뿐만 아니라 acbbca, cbaabc등으로도 재구성 할 수 있다.


처음에는 문자열 길이가 최대 10글자이니 모든 문자열을 재구성해서 구현해보았더니 당연히 시간초과이다.

신기한건 문자 a가 10개로 구성된 aaaaaaaaaa은 답이 금방 나오는데 abvcfascdf 이렇게 문자가 섞이면 답이 나오는데 오래 걸렸다.



그래서 다른사람들은 어떻게 해결했는지 찾아보았는데, 이 문제의 경우의 수를 따져서 해결했다.


앞서 abccba는 여러가지 방법으로 최대 9개가 나왔다. 이중 aabbcc 이렇게 같은 문자열을 순서대로 배치했을 때, a, a, b, b, c, c, aa, bb, cc로 똑같이 최대 9개의 팰린드롬 부분 문자열을 가지게 된다.

(뭔가 수학적으로 증명해야 할 것 같지만.. 정확한 증명은 다른 고수분들이 해주실 것이다)


그러므로 각 알파벳을 이용하여 만드는 부분 팰린드롬을 계산해주면 PASS를 받을 수 있다.




'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

5431. 민석이의 과제 체크하기(D3)  (0) 2018.08.31
3074. 입국심사(D4)  (0) 2018.08.09
3066. 팀 정하기(D7)  (0) 2018.08.09
1257. [S/W 문제해결 응용] 6일차 - K번째 문자열(D6)  (0) 2018.08.09
4583. 세븐 카드 섞기 게임(D5)  (0) 2018.08.09

인턴을 보내지 않고 최대로 만들 수 있는 팀을 먼저 계산한다.


팀을 하나씩 줄이며, 보내야 하는 인턴수를 만족하면, 그때의 팀이 최대로 만들 수 있는 팀이 된다.



'코딩,문제풀이 > SWExpertAcademy' 카테고리의 다른 글

3074. 입국심사(D4)  (0) 2018.08.09
4672. 수진이의 팰린드롬(D4)  (0) 2018.08.09
1257. [S/W 문제해결 응용] 6일차 - K번째 문자열(D6)  (0) 2018.08.09
4583. 세븐 카드 섞기 게임(D5)  (0) 2018.08.09
3977. 페르마의 크리스마스 정리(D5)  (0) 2018.08.09

+ Recent posts

티스토리툴바