Krafton_jungle 5기 23일차 TIL - 그리디, CSAPP

CSAPP

 

기계수준 프로그램에서 제어와 데이터의 결합

포인터

포인터 이해하기

지금까지 어셈블리어를 사용하며 계속 사용했던 () 참조 방식을 포인터라고 생각하고 학습했다. 포인터는 C 언어의 핵심으로 주소의 값을 가르키는 화살표라고 이해하면 된다. 모든 포인터는 특정값을 가진다. 이 값은 특정 자료형을 갖는 어떤 객체의 주소다. 포인터에 대한 이해는 linked list를 직접 구현해가며 학습했다.

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

//
// Created by 전병준 on 24. 4. 9.
//
typedef struct NODE{
    int data;
    struct NODE* next;
} node;

node* list;

// 초기화
void init() {
    if (list == NULL) {
        return;
    } else {
        node* cur;
        cur = list;

        while (cur != NULL) {
            list = cur -> next;
            free(cur);
            cur = list;
        }
    }
}

// append_left 방식
void add(int key) {
    node *new_node;
    new_node = (node *) malloc(sizeof(node)); //    노드의 크기만큼 메모리 할당 및 노드 생성
    new_node->data = key;
    new_node->next = NULL;

    if (list == NULL) {
        list = new_node;
    } else {
        new_node->next = list;
        list = new_node;
    }
}

// 정렬하며 노드를 삽입하는 방법
void ascending_order_add(int key) {
    node *new_node; // 노드 초기화
    new_node = (node *) malloc(sizeof(node)); //    노드의 크기만큼 메모리 할당 및 노드 생성
    new_node->data = key;
    new_node->next = NULL;

    if (list == NULL) { // list가 비어있으면
        list = new_node;
    } else {
        node* cur = list; // 첫번째 노드
        node* prev = NULL;

        if (cur -> data > new_node -> data) { // 만약 새로 추가한 노드가 가장 작은 수를 가졌으면
            new_node -> next = cur;
            list = new_node;
        } else {
            while (cur != NULL && cur -> data < new_node -> data) {
                prev = cur;
                cur = cur-> next;
            }
            if (cur != NULL) {
                new_node -> next = cur;
                prev -> next = new_node;
            } else {
                prev -> next = new_node;
            }
        }
    }
}

// unique key값만 추가하는 로직
void add_unique(int key) {
    node *new_node; // 노드 초기화
    new_node = (node *) malloc(sizeof(node)); //    노드의 크기만큼 메모리 할당 및 노드 생성
    new_node->data = key;
    new_node->next = NULL;

    if (list == NULL) { // 만약 list가 비어있으면
        list = new_node;
    } else {
        node* cur = list; // 현재 노드

        while (cur != NULL) {
            if (cur -> data == key) {
                return;
            }
            cur = cur -> next;
        }

        new_node -> next = list;
        list = new_node;
    }
}

bool remove_node(int key) {

    if (list == NULL) {
        return false;
    }

    if (list -> data == key) { // 첫번째 요소가 key와 일치하면
        node* cur = list;
        list = list -> next;
        free(cur);
        return true;
    }
    else {
        node* cur = list -> next;
        node* prev = list;
        while (cur != NULL && cur -> data != key) {
            prev = cur;
            cur = cur -> next;
        }
        if (cur == NULL) return false; // 만약 탐색을 마쳤는데 일치하는 값이 없으면

        prev -> next = cur -> next;
        free(cur);
        return true;
    }
}

void traverse() {
    node* cur = list;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur -> next;
    }
    printf("\n");
}

int main(void) {

    int arr[9] = {2,4,1,2,6,7,8,3,6};
    int arr_duplicated[18] = { 2,2,1,1,6,2,8,7,6,4,2,5,6,3,7,8,3,9};
    int arr_rmv[4] = {2,9,8,100};

    init();
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        add(arr[i]);
    }
    printf("After add(nomal) : ");
    traverse();

    init();
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        ascending_order_add(arr[i]);
    }
    printf("After add(ascending) : ");
    traverse();

    init();
    for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
        add_unique(arr_duplicated[i]);
    }
    printf("After add(unique) : ");
    traverse();

    for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
        remove_node(arr_rmv[i]);
    }
    printf("After remove : ");
    traverse();

    return 0;
}

해당 코드는 포인터를 통해 각 노드의 주소를 가르키고, 이를 통해 정렬, 삭제를 수행한다.

 

범위를 벗어난 메모리 참조와 버퍼 오버플로우

버퍼 오버플로우

C에서는 배열 참조시 범위를 체크하지 않으며, 이는 스택에 저장된 상태정보가 범위를 벗어난 데이터에 의해 덮어씌워질 수도 있다는 것을 뜻한다. 이를 막기 위해 fgets 함수를 사용하는데, 이는 읽어들일 최대 바이트 수를 인자로 사용하기 때문에 비교적 안전하다.

 

 

알고리즘

 

1463 1로 만들기

import sys
input = sys.stdin.readline
n = int(input())

dp_table = [0] * (n+1)

for i in range(2, n + 1):
    dp_table[i] = dp_table[i-1] + 1
    if i % 2 == 0:
        dp_table[i] = min(dp_table[i], dp_table[i//2]+1)
    if i % 3 == 0:
        dp_table[i] = min(dp_table[i], dp_table[i//3]+1)

print(dp_table[n])

누적된 최적해를 다시 사용해서 최대의 결과값을 가져오는 코드이다.

점화식은 찾아냈지만 세부적인 조건을 설정하지 못해 계속 실패가 나와서 답지를 봤다.

DP 문제는 결국 점화식을 찾아내느냐, 못찾아내느냐의 차이인 것 같다.

 

 

1541 잃어버린 괄호

import sys
input = sys.stdin.readline

result = 0

string_list = list(map(str, input().rstrip().split("-")))

for i in string_list[0].split("+"):
    result += int(i)

for i in string_list[1:]:
    for j in i.split("+"):
        result -= int(j)

print(result)

이 방법은 그리디 알고리즘을 사용했다.

어차피 처음 + 연산을 수행한 뒤 오는 모든 수는 어차피 모두 -연산으로 계산해도 무방함으로 다음과 같이 코드를 작성했다.

 

 

11053 가장 긴 증가하는 수열

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr_dp = [1] * n

for i in range(1,n):
    for j in range(i):
        if arr[i] > arr[j]:
            arr_dp[i] = max(arr_dp[i], arr_dp[j]+1)

print(max(arr_dp))

해당 코드는 dp 알고리즘을 사용했다.

각 수열마다 증가하는 경우의 수를 구하고 이를 dp_arr에 저장한다. 그리고 dp_arr에 저장된 최대의 값을 출력하면 끝