#8 bigO/백준 1152(대문자를 소문자로)/list구현

수업 #7

일시 : 2020/6/29 19:00 ~ 21:00

장소 : 고려대학교 신공학관 3층

 

목표 : 

1. bigO 표기법의 개념을 안다.

2. list의 개념을 이해하고, 구현할 수 있다.

 

1. bigO

알고리즘의 목표는 시간복잡도와 공간복잡도를 줄이는 것에 있다. 시간복잡도는 연산하는데 시간이 얼마나 필요한지를 의미하며, 공간복잡도는 연산하는데 필요한 메모리가 얼마나 필요한지를 의미한다. 그리고 이러한 시간복잡도와 공간복잡도를 입력받아 처리해야하는 데이터의 크기 N을 기준으로 표기하는 것이 bigO 표기법이다.

 

ex) 탐색 알고리즘

탐색 알고리즘은 N개의 데이터 중에서 하나의 데이터를 찾는 알고리즘이다. 정렬되지 않은 일반 배열에서 데이터를 찾고자한다면, 모든 배열의 요소를 하나씩 확인해봐야하기 때문에 N번의 확인이 이루어져야한다. 그래서 이 경우의 시간복잡도는 O(N)이라고 표기할 수 있다.

 

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

점근 표기법 - 위키백과, 우리 모두의 백과사전

 

2. 백준 1152(대분자를 소문자로)

#include <stdio.h>
#include <string.h>
int english[26];
char input[1000001];

char lower(char a) {
    if (a>='A' && a<='Z') {
        return a - (1) + (2);
    }
    return a;
}

int main(void) {
    int len;
    scanf("%s", input);
    len = strlen(input);
    
    for (int i=0; i<len; i++) {
        english[lower(input[i]) - (3)]++;
    }

    int max_value=0, max_index=0, checker=0;
    for (int i=0; i<26; i++) {
        if (english[i] > max_value) {
            max_value = english[i];
            max_index = i;
            checker = 0;  
            continue;
        }
        
        if (english[i] == max_value) {
            checker = 1;
        }
    }

    if (checker == (4)) {
        printf("%c", max_index+(5));
    } else {
        printf("?");       
    }

    return 0;
}

(1) ~ (5)에 들어가야하는 코드를 채워넣어볼 것

 

참고 : string.h에서는 대문자를 소문자로, 소문자를 대문자로 바꿔주는 함수를 제공함 -> strupr(), strlwr()

 

3. list 구현

- 자료구조를 이해하고 구현할 수 있다.

- 포인터를 활용할 수 있다.(심화)

- 구조체를 활용할 수 있다.(심화)

- malloc, free를 활용할 수 있다.(심화)

- 필요한 기능을 구현할 수 있는 능력을 기른다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

typedef struct list {
    Node *head;
    int len;
} List;

Node *newNode(int value); //node 생성
List *newList(); //list관리를 위한 List 구조체 생성

Node *findNode(List *list, int index); //index번째 node를 리턴

void insertNode(List *list, int index, int value); //index번째 node 뒤에 삽입

void deleteNode(List *list, int index); //index번째 node를 삭제

void clearList(List *list); //list 비우기
void deleteList(List *list); //list 삭제

int getLenght(List *list); //list의 길이 리턴
void showAll(List *list); //list의 모든 노드의 값을 출력

int main(void) {
    List *list = newList();
    insertNode(list, getLenght(list), 10);
    insertNode(list, getLenght(list), 20);
    insertNode(list, getLenght(list), 30);
    showAll(list);

    findNode(list, getLenght(list)+1);
    
    insertNode(list, 2, 40);
    showAll(list);

    deleteNode(list, 1);
    showAll(list);

    clearList(list);
    showAll(list);

    deleteList(list);

    return 0;
}

Node *newNode(int value) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->next = NULL;
    node->value = value;
    return node;
}

List *newList() {
    List *list = (List*)malloc(sizeof(List));
    list->head = newNode(0);
    list->len = 0;
    return list;
}

Node *findNode(List *list, int index) {
    if (index > list->len || index < 0) {
        printf("findNode : wrong index\n\n");
        return NULL;
    }

    Node *node = list->head;
    for (int i=0; i<index; i++) {
        node = node->next;
    }
    return node;
}

void insertNode(List *list, int index, int value) {
    if (index > list->len || index < 0) {
        printf("insertNode : wrong index\n\n");
        return;
    }

    Node *node = newNode(value);
    Node *before = findNode(list, index);

    if (before != NULL) {
        node->next = before->next;
    } else {
        node->next = NULL;
    }
    before->next = node;
    list->len++;
}

void deleteNode(List *list, int index) {
    if (index > list->len || index < 0) {
        printf("deleteNode : wrong index\n\n");
        return;
    }

    Node *before = findNode(list, index-1);
    Node *target = before->next;

    before->next = target->next;
    free(target);
    list->len--;
}

void clearList(List *list) {
    Node *head = list->head;

    while (head->next != NULL) {
        deleteNode(list, 1); //list에 노드가 없을 때 까지, 제일 앞의 노드를 삭제 (list의 head는 삭제하지 않음)
    }
}

void deleteList(List *list) {
    clearList(list);
    free(list->head);
    free(list);
}

int getLenght(List *list) {
    return list->len;
}

void showAll(List *list) {
    int i = 0;
    Node *now = list->head;
    printf("length : %d\n", list->len);
    while (now->next!=NULL) {
        now = now->next;
        printf("index %d : %d\n", i, now->value);
        i++;
    }
    printf("\n");
}