gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. Structure 구조체

- 자료형이 상이한 여러 멤버들을 하나의 자료로 묶어서 처리할 수 있는 복합 자료형

1-1. 구조체 변수 선언

// ex1

struct student
{
    int age;
    int grade;
    char major[20];
} kim, lee;

// ex2

struct
{ 
    int age;
    int grade;
    char major[20];
} kim, lee;

// ex3

struct student
{
    int age;
    int grade;
    char major[20];
};
struct student kim, lee;

세 가지 모두 kim과 lee라는 구조체 변수를 선언하는 문장이다.

첫 번째 방식과 같이 구조체의 이름을 줄 수 있고, 두 번째 방식과 같이 구조체 변수를 생성할 수 있다. 세 번째 방식은 구조체 변수를 struct 키워드를 이용해서 선언하는 방식이다. 

- 구조체 변수를 통해서 멤버에 값 저장

student.grade = 3;
strcpy(kim.major, "Software Convergence");

이와 같이 "." 연산자를 사용한다.

1-2. 구조체 자료형 선언

- 일반적으로 구조체를 사용할 때에는 typedef와 함께 사용되는데, typedef 키워드는 struct student_type{...}와 같이 긴 자료형 이름을 student 로 대체하여 구조체 변수를 선언할 수 있게 해준다.

// ex1

typedef struct student_type
{
    char name[10];
    int grade;
    char major[20];
} student;

// ex2

typedef struct
{ 
    char name[10];
    int grade;
    char major[20];
} student;

student kim, lee;

이처럼 struct만 쓴다면 } 이후 나오는 것은 그 구조체 자료형을 가진 "변수" 인 반면, typedef struct로 선언을 했을 때 } 뒤에 나오는 것은 구조체 "자료형" 이다.

1-3. 구조체 할당과 비교

- 할당

    - 동일한 자료형의 구조체 변수 간에 직접적인 할당 명령문은 가능하다.

    - (ex)

    studnet kim, lee;

    kim = lee; 

- 비교

    - 구조체 변수 간 직접 비교는 허용되지 않는다.

    - 구조체 멤버 별로 비교해주어야 한다.

    - (ex) 

    if (kim == lee) ...  // 오류 !!

    if (strcmp(kim.name, lee.name) ...

    if (kim.age != lee.name) ...

    if (kim.grade == lee.grade) ...

    이런식으로 멤버별로 비교해주면 된다.

    - 문자열 비교를 위해 사용된 strcmp 함수는 두 인자 값이 "다를" 경우 1을 반환한다.

1-4. 내장형 구조체

- 다른 구조체 변수를 멤버로 갖는 구조체

#include <stdio.h>
#include <string.h>

typedef struct Contact_type
{
    char phone[20];
    char email[20];
    char address[20];
} Contact;

typedef struct Student_type
{ 
    char name[20];
    int age;
    char major[20];
    int grade;
    Contact contact;
} Student;

void main() 
{
    Student kim;
    
    strcpy(kim.name, "ChulSoo Kim");
    kim.age = 22;
    strcpy(kim.major, "Software Convergence");
    kim.grade = 3;
    strcpy(kim.contact.phone, "010-3606-0418");
    strcpy(kim.contact.email, "kim@naver.com");
    strcpy(kim.contact.address, "Seoul, Korea");
}

student 구조체 안에 contact 구조체를 넣은 형태이다. 

2. Pointer 포인터

- 메모리 주소를 값으로 갖는 변수

- 간접 참조를 통해 원본 데이터를 공유하거나 변경할 수 있다.

- call by reference, 연결리스트 동적 메모리 관리 등에 사용된다.

2-1. "&" 과 "*"

- &

    - 모든 변수에 붙일 수 있는 "주소" 연산자이다. 

    - 해당 변수의 메모리 주소 값을 반환한다.

- *

    - 사용되는 위치에 따라 의미가 달라진다.

    - 반드시 포인터형 변수에만 적용해야 한다.

    - int i =3, j;

    - int *p;

    - p = &i;

        - i의 주소를 p에 할당한다.

    - kim = *p;

        - kim 변수에 p가 가리키는 주소에 저장된 "값"을 대입한다.

    - *p = j;

        - p가 참조하는 "공간"에 j의 값을 저장한다.

3. Array 배열

- 자료형이 동일한 원소들의 유한집합

- <index, value> → item

- 선언 이후 배열의 크기를 변경할 수 없다.

- 배열의 원소 수가 n개 라면 유효한 배열 인덱스의 범위는 [0, n-1] 이다. 

- 배열의 첫 번째 원소인 A[0] 을 "시작 주소 (α)"라고 부른다.   

   이후 원소들은 연속적인 메모리 주소에 저장된다. (α + sizeof(data type))

    - (ex) int → 4bytes 

    α = 100100 → 100104 → 100108 → ...

- 배열 이름 A는 시작 주소를 값을 갖고 있는 "포인터 상수"이다. 선언에 사용된 이름은 이후 다른 값(주소)을 가질 수 없다.

- A == &A[0]    : A[0]의 주소

- *A == A[0]   : A[0]의 값

3-1. 함수에 배열 전달

- 시작 주소를 가지고 있는 "배열 이름"만 전달하면 된다.

- 배열 포인터 관점에서는 call by value이지만, 배열의 관점에서는 call by reference 라고 볼 수 있다.

- int list[] == int *list

- 배열 이름 + 정수 → 첫번째 원소에서 정수의 원소 개수만큼 떨어져 있는 원소의 주소

- (ex) oneArray = 100 → oneArray + 1 = 104, oneArray +2 = 108

4. Polynomial 다항식

- 항들의 집합

- 다항식 추상자료형 연산자

    - Zero()

    - IsZero()

    - Coef (poly, expon)     : 계수 찾기

    - Lead_Exp (poly)     : 최고차항 지수

    - Attach (poly, coef, expon)     : 항 추가

    - Remove (poly, expon)

    - SingleMult (poly, coef, expon)     : 다항식과 단항의 곱셈

    - Add (poly1, poly2)

    - Mult (poly1, poly2)

- (ex) 다항식 배열 선언

#define MAX_TERMS 50

struct polynomial
{
    float coef;
    int expon;
};

struct polynomial terms[MAX_TERMS];

int avail = 0;

www.acmicpc.net/problem/1152

문제 

코드

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
    char str[1000001];
    int space = 0;
    int word = 0;
    int len;

    gets(str);
    len = strlen(str);

    for (int i = 0; i < len; i++) {
        if (str[i] == ' ')
            space++;
    }

    word = space +1;

    if (len == space) {
        word = 0;
        printf("%d\n", word);
    }

    else {
        if (isspace(str[0]))
            word--;
        if (isspace(str[len-1]))
            word--;
        printf("%d\n", word);
    }
}

www.acmicpc.net/problem/10828

문제

코드

#include <stdio.h>
#include <string.h>

int stack[100001];
int count = 0;

void push(int x);
void pop();
void size();
void empty();
void top();

int main() {
    int n, x;
    char order[6];

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", &order);

        if (!strcmp(order, "push")) {
            scanf("%d", &x);
            push(x);
        }

        else if (!strcmp(order, "pop")) pop();
        else if (!strcmp(order, "size")) size();
        else if (!strcmp(order, "empty")) empty();
        else if (!strcmp(order, "top")) top();
        else break;
    }
    return 0;
}

void push(int x) {
    stack[count] = x;
    count++;
}

void pop() {
    if (count != 0) {
        count--;
        printf("%d\n", stack[count]);
        stack[count] = 0;
    }
    else printf("%d\n", -1);
}

void size() {
    printf("%d\n", count);
}

void empty() {
    if (count == 0) printf("%d\n", 1);
    else printf("%d\n", 0);
}

void top() {
    if (count > 0) 
        printf("%d\n", stack[count-1]);
    else printf("%d\n", -1);
}

www.acmicpc.net/problem/1259

문제

코드

#include <stdio.h>
#include <string.h>

int main() {
    char num[6];
    int len = 0;

    while(1) {
        scanf("%s", &num);

        if (num[0] == '0')
            break;

        if (strlen(num) == 1)
            printf("yes\n");
            len = 0;
            break;

        while (num[len] != '\0') {
            len = strlen(num);
            
            for (int i = 0; i < len/2 ; i++) {
                if (num[i] != num[len - 1 - i]) {
                    printf("no\n");
                    len = 0;
                    break;
                }
                    
                else {
                    if (num[i + 1] == num[len - i - 2]) {
                        printf("yes\n");
                        len = 0;
                        break;
                    }

                    else {
                        printf("no\n");
                        len = 0;
                        break;
                    }
                }
            break;
            }
        break;
        }
    }
    return 0;
}

www.acmicpc.net/problem/10818

#include <stdio.h>

int main() {
    int n, num;
    int min = 1000001;
    int max = -1000001;
    
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (num > max)
            max = num;
        if (num < min)
            min = num;
    }
    
    printf("%d %d", min, max);
}

www.acmicpc.net/problem/2753

연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오.
윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다.
예를 들어, 2012년은 4의 배수이면서 100의 배수가 아니라서 윤년이다. 1900년은 100의 배수이고 400의 배수는 아니기 때문에 윤년이 아니다. 하지만, 2000년은 400의 배수이기 때문에 윤년이다.

#include <stdio.h>

int main() {
    int year;
    scanf("%d", &year);
    
    if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) 
        printf("1");
    else
        printf("0");
}

www.acmicpc.net/problem/2884

상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.
상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.
이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.
바로 "45분 일찍 알람 설정하기"이다.
이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.
현재 상근이가 설정한 알람 시각이 주어졌을 때, 창영이의 방법을 사용한다면, 이를 언제로 고쳐야 하는지 구하는 프로그램을 작성하시오.

#include <stdio.h>

int main() {
    int hour, min;
    int phour = 0;
    int pmin = 0;
    scanf("%d %d", &hour, &min);

    if (min >= 45) {
        pmin = min - 45;
        phour = hour;
    }
    else {
        pmin = 60 - (45 - min);
        if (hour == 0)
            phour = 23;
        else
            phour = hour - 1;
    }

    printf("%d %d", phour, pmin);

}