How We Coding

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

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

Week 2-1 : How to code Recursive function2

Tutoring/18-1 DS2018. 4. 4. 00:38

<180403>


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
#include <stdio.h>
 
int max;
 
int f2(int arr[], int n)
{
    int k;
    if(n == 1) {
        max = arr[n] > arr[n-1] ? arr[n] : arr[n-1];
        return arr[n] > arr[n-1] ? arr[n-1] : arr[n];
    }
    k = f2(arr, n-1);
    
    if(arr[n] < k) return k;
    if(arr[n] > max) { int t=max; max=arr[n]; return t; }
    return arr[n];
}
 
int main()
{
    int arr[] = {50, 10, 2, 30, 11, 33};
 
    printf("%d\n", f2(arr, 5));
    return 0;
}
cs


>> n 은 마지막 인덱스

>> 12 : k 에는 n-1번째 요소들까지에서의 두번째 최대값이 저장된다.


>> 14 : n번째 요소가 두번째 최대값보다 작은 경우.
>> 15 : n번째 요소가 최대값인 경우, 기본의 max값이 두번째 최대값이 된다.
>> 16 : 나머지 경우(n번째 요소가 두 번째 최대값)


2) 팰린드롬인지 판단한는 함수 재귀함수로 구현하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <string.h>
 
int isP(char str[], int s, int e)
{
    if(s >= e) return 1;
    return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
}
 
int main()
{
    char str[100];
    scanf("%s", str);
    isP(str, 0, strlen(str)-1) ? puts("True") : puts("False");
    return 0;
}
 
cs


>> 첫번째 인덱스와 마지막 인덱스의 문자가 같을때, 그 안의 문자열이 팰린드롬이면 팰린드롬이다.

>> noon, eye, 다시합창합시다 와 같은 문자열은 모두 팰린드롬이다.



3) 하노이 타워 이동 순서. 

- Hanoi(n, from, by, to) : n개의 쟁반을 from 에서 by를 거쳐 to로 옮기는 과정을 출력하는 함수.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
void Hanoi(int n, char from, char by, char to)
{
    if(n == 1) {
        printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to);
        return ; 
    }
    Hanoi(n-1, from, to, by);
    printf("%d번 쟁반을 %c에서 %c로 이동.\n", n, from, to);
    Hanoi(n-1, by, from, to);
}
 
int main()
{
    Hanoi(3, 'A', 'B', 'C');
    return 0;
}
cs


>> A 에 있는 n 개의 쟁반을 C에 옮기려고 함.


>> A 에 있는 n개의 쟁반들 중, n-1개의 쟁반을 B에 옮기고,

>> A 에 있는 n번째 쟁반을 C로 옮긴다.

>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기면 된다.


>> A 에 있는 쟁반들 중, n-1개의 쟁반을 B에 옮기는 과정을 출력하고,

>> A 에 있는 n번째 쟁반을 C로 옮긴다.

>> 그런다음 B 에 옮겨놨던 n-1개의 쟁반을 C로 옮기는 과정을 출력한다.



>> 실행결과

1
2
3
4
5
6
7
1번 쟁반을 A에서 C로 이동.
2번 쟁반을 A에서 B로 이동.
1번 쟁반을 C에서 B로 이동.
3번 쟁반을 A에서 C로 이동.
1번 쟁반을 B에서 A로 이동.
2번 쟁반을 B에서 C로 이동.
1번 쟁반을 A에서 C로 이동.
cs



4) 별찍는 순서.


4-1)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    printf("*");
    f(n-1);
}
cs




4-2)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    f(n-1);
    printf("*");
}
cs



4-3)

1
2
3
4
5
6
7
void f(int n)
{
    if(n == 0) return ;
    printf("*");
    f(n-1);
    f(n-1);
}
cs



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

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

Week 1-2 : How to code Recursive function

Tutoring/18-1 DS2018. 3. 30. 00:35

<180329>


- 재귀함수 만들기


1) 함수를 잘 정의하고, 그 정의를 그대로 활용하기

2) 어떻게 쪼갤지 생각하기..

3) 언제까지??(재귀의 종료, 탈출조건)

4) 점화식을 알고 있다면 그대로 표현하기.



- 구현해보기.


1) Sum(n) : 1부터 n까지의 합을 구하는 함수.


1
2
3
4
5
int Sum(int n)
{
    if(n < 1) return 0;
    return n + Sum(n-1);
}
cs


>> 1부터 n까지의 합은 1부터 n-1까지의 합에 n을 더하면 된다.

>> 1보다 작은 수가 들어오면 0을 리턴하면 될 것 같다.



2) evenSum(n) : 1부터 n까지의 수 중 짝수의 합 구하기.


1
2
3
4
5
6
int evenSum(int n)
{
    if(n < 1) return 0;
    if(n&1) n--;
    return n + evenSum(n-2);
}
cs


>> n이 짝수인 경우, 1부터 n까지의 수 중 짝수의 합은 1부터 n-2까지의 수중 짝수의 합에 현재 값을 더하면 된다.

>> n이 홀수일 수도 있으므로, 4번 라인에서 예외처리를 한번 더 한다.

>> 홀수의 경우 마지막 비트는 항상 1이다. 그러므로 홀수와 1을 비트연산을 하면 1이 나온다. 조건식에서 1은 참..!!



3) combi(n, r) : n개의 수 중 r개의 수를 뽑는 방법의 수.


1
2
3
4
5
int combi(int n, int r)
{
    if(r == 0 || n == r) return 1;
    return combi(n-1, r-1) + combi(n-1, r);
}
cs


>> 우리는 nCr = n-1Cr + n-1Cr-1 이라는 점화식을 알고있다....ㅎㅎ

>> 해당 점화식을 그대로 표현했을 뿐이다. 

>> 즉, n개의 수 중 r개의 수를 뽑는 방법의 수는 

     임의의 수 하나를 무조건 뽑는 다고 생각했을 때인, n-1개의 수 중 r-1 개를 뽑는 방법에 수와 

     그 임의의 수 하나를 무조건 안뽑는다고 생각햇을 때인, n-1개의 수 중 r 개를 뽑는 방법에 수를 더하면 된다.

>> 그리고 우리는 nC0 == nCn == 1 이라는 것을 알고 있다. 그대로 탈출조건에 적용하면 된다.



4) print1(n) : 1부터 n까지 출력하는 함수


1
2
3
4
5
6
void print1(int n)
{
    if(n < 1) return ;
    print1(n-1);
    printf("%d\n", n);
}
cs


>> 1부터 n까지 출력하는 것은 1부터 n-1까지 출력한 다음에 n만 출력하는 것과 같다.



5) print2(n) : n부터 1까지 거꾸로 출력하는 함수.


1
2
3
4
5
6
void print2(int n)
{
    if(n < 1) return ;
    printf("%d\n", n);
    print1(n-1);
}
cs


>> n부터 1까지 거꾸려 출력하는 것은 n을 먼저 출력하고 n-1부터 1까지 거꾸로 출력하는 것과 같다.



6) arrSum(int arr[], int n) : 배열 arr에서 0번째 값에서 n번째 값까지의 합을 구하는 함수.


1
2
3
4
5
int arrSum(int arr[], int n)
{
    if(n == 0) return arr[0];
    return a[n] + arrSum(arr, n-1);
}
cs


>> 배열 arr에서 0값 요소에서 n번째 값까지의 합은 배열 arr에서 0번째 값에서 n-1번째 값까지의 합에 n번째 값을 더하면 된다.



7) arrMax(int arr[], int n) :  배열 arr에서 0번째 값에서 n번째까지의 값 중 최대값을 구하는 함수


1
2
3
4
5
6
7
int arrMax(int arr[], int n)
{
    int k;
    if(n == 0) return arr[0];
    k = arrMax(arr, n-1);    
    return a[n] > k ? a[n] : k;
}
cs


>>  배열 arr에서 0번째 값에서 n-1번째까지의 값 중 최대값이 k라고 하자.

      then, k와 a[n] 중에서의 최대값이 배열 arr에서 0번째 값에서 n번째까지의 값 중에서 최대값이 된다.

>> 시각적인 이미지 참고 블로그(전에 설명 들은 동생이 정리해놨다..ㅎㅎ) : http://mattlee.tistory.com/17?category=680710



- 숙제 : 배열의 값들 중 두번째 최대값 구하기.

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

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

Week 1-1 : C Lang review

Tutoring/18-1 DS2018. 3. 28. 01:17

<180327>


- C Lang review


8-3) 문자열 복사하기. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
void myStrcpy(char *to, char *from)
{
    while(*from) 
        *(to++) = *(from++);
    *to = 0;
}
 
int main()
{
    char a[]="HS_Turoring";
    char b[100];
 
    myStrcpy(b, a);
    puts(b);
    
    return 0;
}
cs


>> 조건식에서의 참, 거짓.

>> 널문자의 아스키 코드값 == 0

>> 널문자 따로 넣어주기 (7번 라인)

>> 포인터 연산의 원리 생각해보기.

>> 배열의 이름은 상수형태의 포인터.

>> 포인터(변수)는 말그대로 변수이므로, 주소값이 바뀔 수 있다.



8-5) 문자열 뒤집기


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>
 
int myStrlen(char *s)
{
    int i=0;
    while(s[i]) i++;
    return i;
}
 
void reverse(char *to, char *from)
{
    int idx=0;
    int len=myStrlen(from);
    for(int i=len-1; i>=0; i--)
        to[idx++] = from[i];
    to[idx] = 0;
}
 
int main()
{
    char a[]="HS_Turoring";
    char b[100];
 
    reverse(b, a);
    puts(b);
    
    return 0;
}
cs


>> 널문자 삽입 코드 필수.

>> 배열의 이름[문자열의 길이] 에는 널문자가 들어있다.

>> 문자열의 길이는 reverse() 에서 구한다음 진행하면 됨.



9) 순환함수.


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 mul(int n)
{
    if(n == 1) return 1;
    return n * mul(n-1);
}
 
int mulEven(int n)
{
    if(n < 1) return 1;
    if(n%2 == 1) n--;
    return n * mul(n-2);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", mul(n)); 
    printf("%d\n", mulEven(n));
    return 0;
}
cs


>> 함수를 잘 정의하고, 그 정의를 그대로 활용하기.

>> 어떻게 쪼개서 생각할 수 있을까? 고민해보기.

>> 생각한 것을 그대로 코드로 옮기기. 함수의 기능을 그대로 활용해서..!!

>> 탈출조건 고민해보기. 



2-4) is직각삼각형?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int isTri(int max, int a, int b)
{
    return max*max == a*a + b*b;
}
 
int main()
{
    int a, b, c;
    int tri;
    scanf("%d%d%d", &a, &b, &c);
    if(a > b && a > c) tri = isTri(a, b, c);
    else if(b > a && b > c) tri = isTri(b, a, c);
    else tri = isTri(c, a, b);
 
    tri ? puts("직각") : puts("ㄴㄴ");
 
    return 0;
}
cs


>> 큰값만 알면 되므로..

>> 함수를 사용해야 하는 이유 생각해보기..!!




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

Week 3-2 : Linked List  (0) 2018.04.15
Week 3-1 : Linked List  (0) 2018.04.11
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

티스토리툴바