How We Coding

Week 5-1 : Circular Doubly Linked List / Stack ADT

Tutoring/18-1 DS2018. 5. 8. 11:18

< 180503 >


1) 원형 이중연결리스트 with 더미노드


- 더미노드 : 말그대로 더미인 노드.

>> 더미노드를 사용하면, head 포인터가 가리키는 대상이 바뀔일이 없다. 항상 더미노드를 가리키므로.

>> 이전에는 head 포인터가 가리키는 대상이 변경될 여지가 있으면 이중 포인터를 써야했는데, 

     더미노드를 쓰면 그럴 필요가 없어진다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
 
typedef struct listNode {
    int data;
    struct listNode *llink, *rlink;
} ListNode;
 
int main()
{
    ListNode *head = NULL;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->rlink = head;
    head->llink = head;
 
}
cs


>> 또한 지금까지는 head 포인터는 NULL 로만 초기화 했지만, 더미노드 사용하는 경우 더미노드를 만드는 과정을 추가해야한다.

>> 여기서의 더미노드 초기화 코드는 양방향 원형 연결리스트이므로 저런식으로 하면 될 것 같다.



- 삽입하기 / 삭제하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void addNode(ListNode *before, ListNode *newNode)
{
    newNode->rlink = before->rlink;
    newNode->llink = before;
    before->rlink = newNode;
    newNode->rlink->llink = newNode;
}
 
 
void delNode(ListNode *phead, ListNode *remove)
{
    if(remove == phead) return ;
    remove->rlink->llink = remove->llink;
    remove->llink->rlink = remove->rlink;
    free(remove);
}

cs


>> 노드를 삽입하는 함수에서는 순서가 중요하다. 

>> 12번 라인의 예외처리는 삭제하려는 노드가 더미노드인경우 이다. 더미노드를 사용하는 리스트인데 더미노드를 삭제하면 안되기 때문..!



- 지금까지의 내용을 그림으로 그려보면 다음과 같다. (PPT로 안그릴꺼임...ㅡㅡ)





2) 스택 구현하기


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

>> 그냥 프링글스 ㅎㅎ


- 스택의 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
#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)
{
    if(isFull(s)) return ;
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
int pop(Stack *s)
{
    return s->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);
 
    if(!isEmpty(&s)) printf("%d\n", peek(&s));
    if(!isEmpty(&s)) printf("%d\n", pop(&s));
 
    return 0;
}
cs


>> 실행결과

Empty

Not Full

7

7


>> isFull() 에서 왜 MAX-1 일때가 가득찬 상태인지 생각해보기..!!

>> top 의 역할은 스택을 구성하는 배열에서 가장 마지막에 위치한 데이터의 인덱스..!!



2-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
#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


>>  여기서는 pop 할때 데이터를 꺼내지 않도록 설계를 한 경우.




### 스택의 응용 ###


3) 올바른 괄호 문자열

- "()()" 는 올바른 괄호 문자열

 - "(())" 는 올바른 괄호 문자열

- "(()())" 는 올바른 괄호 문자열

- "()(" 는 x

- "())(" 는 x




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

Week 6 : Maze(with stack) / Circular Queue  (0) 2018.05.16
Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 4-2 : Circular Linked List  (0) 2018.04.20
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-2 : Linked List  (0) 2018.04.15

Week 07

Tutoring/18-1 C Lang2018. 5. 5. 17:46

<180502>



- 반복문의 세계..!!


- for 문의 작동 원리


for(초기식; 조건식; 증감식) {

바디

}


1. 초기식

2. 조건식

>> 조건식이 참이면, 바디 - 증감식 후 다시 조건식으로.

>> 조건식이 거짓이면 for 문 종료.



- while 문 vs for 문

반복횟수를 알고 있는경우 for 문을, 얼마나 반복해야 할 지 모르는 경우 while 문을 추천.



- while 문 vs do ~ while 문

>> do ~while() : 바디를 일단 한번 실행 시키고 나서 조건식에 따라 반복여부 결정

>> while() :  조건식에 따라 반복




< 프로그래밍 연습 >


1. 0이 입력되기 전까지 입력된 정수들의 합과 평균 구하기.

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, sum=0;
    int count=0;
    double avg;
 
    while(1) {
        scanf("%d", &n);
        if(n == 0) 
            break;
        sum += n;
        count++;
    }
 
    avg = (double)sum/count;
 
    return 0;
}
cs


>> 12 번 줄의 break 문은 가장 가까이에 있는 반복문 하나를 탈출한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main()
{
    int n, sum=0;
    int count=0;
    double avg;
 
    do {
        scanf("%d", &n);
        sum += n;
        count++;
    } while(n != 0);
 
    avg = (double)sum/(count-1);
   
    return 0;
}
cs


>> do ~ while() 을 이용.



2. 1~10 까지의 합 구하기. 

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



3. 1~n 까지의 합 구하기

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



4. 1~n 까지의 수들 중 홀수의 합 구하기.

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



5. 'A'~'Z' 까지 출력하기

1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    char ch;
    for(ch='A'; ch<='Z'; ch++)
        printf("%c\n", ch);
    return 0;
}
cs



6. 아래의 실행결과가 나오는 프로그래밍

1
2
3
4
5
6
7
8
9
1
22
333
4444
55555
666666
7777777
88888888
999999999
cs


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



7.  아래의 실행결과가 나오는 프로그래밍

1
2
3
4
5
6
7
8
9
1
12
123
1234
12345
123456
1234567
12345678
123456789
cs


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


>> 6번과 7번 소스코드가 어떻게 다른지 비교해보기..!!



8. 아래의 실행결과가 나오는 프로그래밍

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
A
AB
ABC
ABCD
ABCDE
ABCDEF
ABCDEFG
ABCDEFGH
ABCDEFGHI
ABCDEFGHIJ
ABCDEFGHIJK
ABCDEFGHIJKL
ABCDEFGHIJKLM
ABCDEFGHIJKLMN
ABCDEFGHIJKLMNO
ABCDEFGHIJKLMNOP
ABCDEFGHIJKLMNOPQ
ABCDEFGHIJKLMNOPQR
ABCDEFGHIJKLMNOPQRS
ABCDEFGHIJKLMNOPQRST
ABCDEFGHIJKLMNOPQRSTU
ABCDEFGHIJKLMNOPQRSTUV
ABCDEFGHIJKLMNOPQRSTUVW
ABCDEFGHIJKLMNOPQRSTUVWX
ABCDEFGHIJKLMNOPQRSTUVWXY
ABCDEFGHIJKLMNOPQRSTUVWXYZ
cs

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    char ch, start;
    for(ch='A'; ch<='Z'; ch++) {
        for(start='A'; start<=ch; start++)
            printf("%c", start);
        printf("\n");
    }
    return 0;
}
 
cs



9. 
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
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXY
ABCDEFGHIJKLMNOPQRSTUVWX
ABCDEFGHIJKLMNOPQRSTUVW
ABCDEFGHIJKLMNOPQRSTUV
ABCDEFGHIJKLMNOPQRSTU
ABCDEFGHIJKLMNOPQRST
ABCDEFGHIJKLMNOPQRS
ABCDEFGHIJKLMNOPQR
ABCDEFGHIJKLMNOPQ
ABCDEFGHIJKLMNOP
ABCDEFGHIJKLMNO
ABCDEFGHIJKLMN
ABCDEFGHIJKLM
ABCDEFGHIJKL
ABCDEFGHIJK
ABCDEFGHIJ
ABCDEFGHI
ABCDEFGH
ABCDEFG
ABCDEF
ABCDE
ABCD
ABC
AB
A
cs


1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
 
int main()
{
    char ch, start;
    for(ch='Z'; ch>='A'; ch--) {
        for(start='A'; start<=ch; start++)
            printf("%c", start);
        printf("\n");
    }
    return 0;
}
cs



10. 구구단 몇단??


1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
 
int main()
{
    int i, n;
    scanf("%d", &n);
    for(i=1; i<=9; i++)
        printf("%d * %d = %d\n", n, i, n*i);
    return 0;
}
cs



11. 기본 별찍기.


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


>> n 이 5일대의 실행결과

*

**

***

****

*****

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

Week 09  (0) 2018.05.16
Week 08  (0) 2018.05.09
Week 06  (0) 2018.04.23
Week 05  (0) 2018.04.18
Week 04  (0) 2018.04.11

[카카오 코드 / 예선] 카카오프렌즈 컬러링북

PS/etc.2018. 5. 4. 13:31

[카카오 코드 / 예선] 카카오프렌즈 컬러링북 : https://programmers.co.kr/learn/courses/30/lessons/1829



<소스코드>


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 <vector>
 
using namespace std;
 
int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int R, C;
 
bool safe(int r, int c)
{
    return (0 <= r && r < R) && (0 <= c && c < C);
}
 
int dfs(vector<vector<int>> &picture, int r, int c, int val)
{
    int ret = 1;
    picture[r][c] = 0;
    
    for(int k=0; k<4; k++) {
        int nr = r+dr[k];
        int nc = c+dc[k];
        if(safe(nr, nc) && picture[nr][nc]==val)
            ret += dfs(picture, nr, nc, val);
    }
    return ret;
}
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    R = m; C = n;
    
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(picture[i][j] != 0) {
                int tmp = dfs(picture, i, j, picture[i][j]);
                number_of_area++;
                if(max_size_of_one_area < tmp)
                    max_size_of_one_area = tmp;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}
cs


'PS > etc.' 카테고리의 다른 글

[POJ/1182] 먹이 사슬  (0) 2018.07.25
[POJ/2431] Expedition  (0) 2018.06.27
<3-1> 나열하기 - 경우의 수  (0) 2018.03.06

[BOGGLE] 보글게임

PS/종만북2018. 4. 30. 00:44

[BOGGLE] 보글 게임 : https://algospot.com/judge/problem/read/BOGGLE?c=16921



### DP ###


check(i, j, word) : (i, j) 에서 문자열 word 를 만들수 있는지. 


<소스코드>


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
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
 
char boggle[5][6];
int di[]={1, 1, 0, -1, -1, -1, 0, 1};
int dj[]={0, 1, 1, 1, 0, -1, -1, -1};
 
int sNum = 1;
map<string, int> msi;
int d[5][5][10000];
 
int check(int curI, int curJ, char *word)
{
    if(*(word+1) == 0) return true;
 
    int num;
    if(msi.find(word) == msi.end()) {
        msi[word] = sNum;
        num = sNum++;
    }
    else num = msi[word];
    
    int &ret = d[curI][curJ][num];
    if(ret != 0) return ret;
 
    for(int k=0; k<8; k++) {
        int nextI = curI+di[k];
        int nextJ = curJ+dj[k];
        if((0 <= nextI && nextI < 5) && (0 <= nextJ && nextJ < 5)) {
            if(boggle[nextI][nextJ] == *(word+1) && check(nextI, nextJ, word+1) == 1)
                return ret = 1;
        }
    }
    return ret = -1;
}
 
bool BOGGLE(char *word)
{
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            if(boggle[i][j] == *word && check(i, j, word) == 1)
                return true;
    return false;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        for(int i=0; i<5; i++)
            scanf("%s", boggle[i]);
        
        memset(d, 0, sizeof(d));
 
        int n;
        scanf("%d", &n);
        while(n--) {
            char word[11];
            scanf("%s", word);
            printf("%s ", word);
            BOGGLE(word) ? puts("YES") : puts("NO");
        }
    }
}    
cs


>> 완전 탐색으로 소개되는 문제지만, 시간초과가 난다.

>> 해결방법은 DP 라는데... 

>> 문자열을 메모이제이션 할 방법이 도무지 떠오르질 않아 푸는데 오래 걸렸던 문제..!! >> 해싱으로 처리하였다. 

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

[RUNNINGMEDIAN] 변화하는 중간 값  (0) 2018.07.20
[DICTIONARY] 고대어 사전  (0) 2018.05.22
[MATCHORDER] 출전 순서 정하기  (0) 2018.04.20
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16

Week 06

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

< 180420 >


중간고사 대비 모의고사



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

Week 08  (0) 2018.05.09
Week 07  (0) 2018.05.05
Week 05  (0) 2018.04.18
Week 04  (0) 2018.04.11
Week 03  (0) 2018.04.04

[9252] LCS2

BOJ/DP2018. 4. 22. 02:07

[9252] LCS2 : http://boj.kr/9252



### DP -Track ### (참고 : https://kks227.blog.me/221028710658)


< 소스코드 >


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
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
 
struct P { int ret, si; };
 
char s[1001], t[1001];
int d[1001][1001];
char a[1001];
 
stack<P> st;
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs2(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs2(si-1, ti-1)+1;
        st.push((P){ret, si});
    }
    else {
        ret = max(lcs2(si-1, ti), lcs2(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
 
    int ans = lcs2(sLen-1, tLen-1);
    printf("%d\n", ans);
 
    while(!st.empty()) {
        if(st.top().ret == ans) {
            a[--ans] = s[st.top().si];
        }
        st.pop();
    }
    puts(a);
}
cs


>> 아이디어는 부분문제의 답을 통해 역으로 그 답을 끼워 맞춘다.


>> 테스트 케이스는 아래와 같다.

ACAYKP

CAPCAK


>> 위 테케에 대한 아웃풋은 아래와 같다.

4

ACAK


>> 위 코드의 경우, 스택 st의 ret 에는 3 4 2 1 3 2 1 가 저장이 된다. 

>> 맨 처음 정답에 해당하는 4일때의 si, 그다음 작은 숫자인 3일때의 si, ...

>> 이렇게 문자를 거꾸로 저장한 다음 출력하면 답이 된다.



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

[9177] 단어 섞기  (0) 2018.05.22
[2602] 돌다리 건너기  (0) 2018.05.17
[9251] LCS  (0) 2018.04.21
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22

[9251] LCS

BOJ/DP2018. 4. 21. 02:14

[9251] LSC : http://boj.kr/9251


### DP ###


lcs(si, ti) : 문자열 s의 si번째 문자까지, t의 ti번째의 문자까지의 가장 긴 증가하는 부분 문자열 (최장 공통 부분 수열)


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>
#include <string.h>
 
char s[1001], t[1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lcs(int si, int ti)
{
    int ret = 0; 
 
    if(si < 0 || ti < 0) return 0;
    if(d[si][ti] != -1) return d[si][ti];
 
    if(s[si] == t[ti]) {
        ret = lcs(si-1, ti-1)+1;
    }
    else {
        ret = max(lcs(si-1, ti), lcs(si, ti-1));
    }   
    return d[si][ti] = ret;
}
 
int main()
{
    int sLen=0, tLen=0;
    scanf("%s%s", s, t);
 
    while(s[sLen]) sLen++;
    while(t[tLen]) tLen++;
 
    memset(d, -1, sizeof(d));
    printf("%d\n", lcs(sLen-1, tLen-1));
    return 0; 
}
cs


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

[2602] 돌다리 건너기  (0) 2018.05.17
[9252] LCS2  (0) 2018.04.22
[14002] 가장 긴 증가하는 부분 수열 4  (0) 2018.04.18
[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22

[MATCHORDER] 출전 순서 정하기

PS/종만북2018. 4. 20. 22:36

[MATCHORDER] 출전 순서 정하기 : https://algospot.com/judge/problem/read/MATCHORDER



### Greedy ###


< 소스코드 >


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
#include <cstdio>
#include <algorithm>
using namespace std;
 
int Rus[101], Kor[101];
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) 
            scanf("%d", Rus+i);
 
        for(int i=0; i<n; i++) 
            scanf("%d", Kor+i);
 
        sort(Rus, Rus+n);
        sort(Kor, Kor+n);
        
        int ri=0, ki=0;
        int ans=0;
 
        while(ri < n && ki < n) {
            if(Rus[ri] <= Kor[ki]) {
                ans++; ri++; ki++;
            }
            else ki++;
        }
        printf("%d\n", ans);
    }
}
cs


>> 차이가 최소가 되도록, 각각 오름차순 정렬 후 Korea 가 같거나 크면 이기고,

>> 러시아가 크면 다음으로 큰 한국 점수가 나올때까지 인덱스를 증가시킨다.

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

[DICTIONARY] 고대어 사전  (0) 2018.05.22
[BOGGLE] 보글게임  (0) 2018.04.30
[NUMBERGAME] 숫자게임  (0) 2018.04.17
[POLY] 폴리오미노  (0) 2018.04.16
[ASYMTILING] 비대칭 타일링  (0) 2018.04.16

Week 4-2 : Circular Linked List

Tutoring/18-1 DS2018. 4. 20. 00:29

< 180419 >


< Homework >


- 단일 연결리스트에서 최대값을 가지는 노드를 맨 마지막으로 보내기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void maxLast(ListNode **phead)
{
    ListNode *p, *cur = *phead;
    ListNode *pMax, *cMax = cur;
 
    if(cur == NULL) return ;
 
    while(cur) {
        if(cur->data > cMax->data) {
            pMax = p; cMax = cur;
        }
        p = cur; cur = p->link;
    }
 
    if(pMax == NULL) *phead = cMax->link;
    else pMax->link = cMax->link;
 
    p->link = cMax;
    cMax->link = NULL;
}
cs


>> while() 문이 끝나면 cur 는 NULL, p 는 마지막 노드를 가리키게 된다.

>> cMax 는 최대값을 가지고 있는 노드를, pMax 는 최대값을 가지고 있는 노드의 이전 노드를 가리키게 된다.



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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct cListNode {
    int data;
    struct cListNode *next;
} CListNode;
 
void CircularListAdd(CListNode **phead, int data)
{
    CListNode *p, *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
 
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    p = *phead;
    while(p->next != *phead)
        p = p->next;
 
    p->next = newNode;
    newNode->next = *phead;
    //*phead = newNode;
}
 
void cDisplay(CListNode *phead)
{
    CListNode *cur = phead;
 
    if(cur == NULL) return ;
 
    do {
        printf("%d\n", cur->data);
        cur = cur->next;
    } while(cur != phead);
}
 
int main()
{
    CListNode *head = NULL; 
    CircularListAdd(&head, 1);
    CircularListAdd(&head, 3);
    CircularListAdd(&head, 7);
    CircularListAdd(&head, 5);
 
    cDisplay(head);    
 
    return 0;
}
cs


>> 9 : 원형 연결리스트의 데이터를 삽입하는 함수.

>> 29 : 원형 연결리스트의 데이터를 출력하는 함수. do ~ while() !!


>> 49 라인의 결과는 1, 3, 7, 5

>> 26 라인의 주석을 해제하면, 49 라인의 결과는 5, 7, 3, 1

>> 즉 26가 없으면 뒤로 삽입, 있으면 앞으로 삽입을 하는 결과가 만들어진다.


>> 다만 위의 코드에서는 삽입을 할때, 항상 맨 마지막 노드를 찾아야 하는 번거로움(?)이 있다. (21-22 라인)

     하지만 헤드포인터를 테일이라고 생각하고 코드를 작성하면 그럴필요가 없어진다..!!


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void CircularListAdd2(CListNode **phead, int data)
{
    CListNode *newNode = (CListNode*)malloc(sizeof(CListNode));
    newNode->data = data;
    
    if(*phead == NULL) {
        *phead = newNode;
        newNode->next = newNode;
        return ;
    }
 
    newNode->next = (*phead)->next;
    (*phead)->next = newNode;
    //*phead = newNode;
}
cs


>> main() 에서의 head 를  tail 이라고 생각하는 것이 그림을 그려가는데 있어서 이해하기 쉽다.

>> 14 가 없으면 뒤로 삽입, 14가 있으면 앞으로 삽입하는 코드가 된다.


>> 뒤로 삽입시 출력 결과는 1 5 7 3, 

>> 앞으로 삽입했을 때 결과는 5 1 3 7 이 나온다. 

>> 우리가 작성한 코드대로라면 마지막 노드를 먼저 출력하고 나머지를 출력하기 때문이다.

>> head 포인터가 항상 마지막 노드를 가리키고 있기 때문이다.

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

Week 5-2 : infix to postfix, exp(postfix)  (0) 2018.05.08
Week 5-1 : Circular Doubly Linked List / Stack ADT  (0) 2018.05.08
Week 4-1 : Linked List  (0) 2018.04.18
Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11

[14002] 가장 긴 증가하는 부분 수열 4

BOJ/DP2018. 4. 18. 18:36

[14002] 가장 긴 증가하는 부분 수열 4 : http://boj.kr/14002


< 소스코드 >


lis(s) : s 번째에서 시작하는 가장 긴 증가하는 부분 수열 


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 <stdio.h>
#include <string.h>
 
int n;
int a[1001], d[1001];
int next[1001];
 
int lis(int s)
{
    int ret=0;
 
    if(d[s]) return d[s];
 
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i]) {
            int cur = lis(i);
            if(ret < cur) {
                ret = cur;
                next[s] = i;
            }
        }
    }
    return d[s] = ret+1;
}
 
void path(int k)
{
    if(k == -1) return ;
    printf("%d ", a[k]);
    path(next[k]);
}
 
 
int main()
{
    int k, ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    memset(next, -1, sizeof(next));
 
    for(int i=0; i<n; i++) {
        int tmp = lis(i);
        if(ans < tmp) {
            ans = tmp;
            k = i;
        }
    }
 
    printf("%d\n", ans); 
    path(k);
    puts("");
 
    return 0;
}
 
cs


>> next[i] 는 i의 다음 수열에 해당하는 인덱스.

>> n 제한이 1000 이라, O(n^2) 인 재귀로 가능하다.

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

[9252] LCS2  (0) 2018.04.22
[9251] LCS  (0) 2018.04.21
[10942] 팰린드롬?  (0) 2018.02.22
[1890] 점프  (0) 2018.02.22
[2216] 문자열과 점수  (0) 2018.02.21

티스토리툴바