프로그래밍노리터

변수는 값이 바뀌는 것이고 상수는 값이 변하지 않는다고 배웠는데... Rust 언어의 온라인 문서(이하 Rust Book)를 읽으면서 기존의 프로그래밍 언어와 많이 달라진 개념을 하나씩 조금 다른 관점으로 정리해 보려고 합니다. Rust 언어의 프로그래밍에 대한 시각을 음미해 보려고 합니다. https://rinthel.github.io/rust-lang-book-ko/ch03-01-variables-and-mutability.html 변수와 가변성 - The Rust Programming Language 2 장에서 언급했듯이, 기본 변수는 불변성입니다. 이것은 Rust가 제공하는 안전성과 손쉬운 동시성이라는 장점을 취할 수 있도록 코드를 작성하게끔 강제하는 요소 중 하나입니다. 하지만 여전히 rinth..

연결리스트란? 연결리스트란 노드가 연쇄적으로 연결되어 있는 구조로 각 노드는 데이터(data)와 다음 링크(next, 다음 노드의 주소)라는 두개의 필드를 가진다. data 필드는 리스트의 실제 요소를 가지고 next는 리스트의 다음 노드를 가리키는 주소를 가집니다. 그러므로 next 필드는 다음 노드에 대한 포인터가 된다. 전체 연결리스트는 제일 앞의 노드에 대한 포인터로 나타낼 수 있다. 즉 첫 번째 노드를 가리키는 변수 하나만 있으면 리스트 전체를 접근할 수 있다. 여기서는 그것을 head라고 부른다. 마지막 노드의 next는 NULL이라고 알려진 특수한 값을 가진다. 이것은 더이상 다음 노드가 없음을 나타내는 역할을 한다. 노드가 없는 리스트를 널 리스트라고 한다. 그 경우 head=NULL이 된..

이차원배열을 어떻게 malloc하느냐는 질문을 받았는데, 쉽지 않은 주제네요. 이차원 배열을 함수 매개변수로 넘기는 방법을 먼저 살펴보겠습니다. C 언어에서 2차원 배열은 포인터의 배열이고 각 포인터는 COLS칸 배열의 주소를 가집니다. 여기서 ROWS, COLS는 상수를 나타내고 rows, cols는 변수일 수 있습니다. (참고) void func(int array[ROWS][COLS]) { ... void func_vla(int rows, int cols, int array[rows][cols]) { ... void test(int array[][COLS], int rows) { ... void test(int (* array)[COLS], int rows) { ... 첫번째는 상수 크기의 배열을 넘..

스택은 데이터의 순서를 뒤집어야 하는 경우에 유용하게 쓰인다. 스택을 임시 메모리로 사용하면 코드가 간결해진다. (1) 문자열 뒤집기 문자열의 글자 순서를 뒤집는 문제는 스택을 이용하여 다음과 같이 해결할 수 있다. (널문자는 그대로 있음) void reverse(char* word) { stack_t stack; int i; for (i = 0; i < strlen(word); i++) push(&stack, word[i]); i = 0; while (!is_empty(&stack)) word[i++] = pop(&stack); } (2) 2진수로 바꾸기 2진수로 바꾸는 문제는 2로 나눈 나머지를 거꾸로 이어 붙여서 2진수를 만들 수 있다. 이 문제도 스택을 이용해서 다음과 같이 간단하게 바꿀 수 있다..

큐에서 디큐한 후에 남는 공간을 비워두지 않기 위해 원형 큐를 사용할 수 있는데, 스택으로 큐를 구현하는 방법도 있다. 여기서는 스택 두 개를 이용해서 큐를 구현하는 방법을 살펴본다. 먼저 큐 구조체의 정의를 살펴보자. (요소의 타입(typedef ... element)은 스택에서 정의된다.) typedef struct queue_t { // 큐 타입 stack_t instack; stack_t outstack; } queue_t; 그러면 큐의 연산들은 다음과 같이 정의된다. init_queue: 두 개의 스택을 초기화한다. transfer: instack의 것을 pop하여 모두 outstack으로 옮겨 push한다. enqueue: 요소를 instack에 넣는다. instack이 꽉차있으면 ERROR...

트리 정보를 입력하여 생성하는 것은 쉽지 않은 일이다. 일반적으로 많이 사용되는 이진 트리 형태로 데이터를 읽어 구축하는 프로그램을 생각해 보자. 먼저 후위표기식 형태의 이진연산자로 구성된 수식을 읽어들여 트리를 구축할 수 있다. 다음과 같은 후위표기식을 입력으로 받아 이진 트리를 구축하는 문제를 생각해 보자. 94-385%+*435+2*++ 이 수식에 대한 이진트리는 다음과 같은 형태로 나타낼 수 있다. 이것은 트리의 출력기능을 통해 출력한 결과다. 트리의 노드는 연산자인 경우 넌터미널로 자식을 가진 노드가 되고 숫자는 터미널 노드여서 자식을 갖지 않는다. 그리고 숫자의 경우는 그 숫자를 노드의 데이터로 가진다. 다음 코드는 스택을 이용해 후위표기식의 계산과 같은 방식으로 숫자는 푸시하고 연산자가 나오..

선형큐 큐는 들어온 순서대로 처리되어 나가는 자료구조다. 배열 기반 큐의 구조체 정의는 다음과 같다. #define MAX_Q_SIZE 10// 큐의 최대 크기 typedef int elem_t; typedef struct queue_t { elem_t data[MAX_Q_SIZE]; int front; int rear; } queue_t; 여기서도 요소타입을 typedef int element;와 같이 선언하였음을 확인할 수 있다. 위와 같이 정의된 큐의 데이터에 대해 적용가능한 기능을 다음과 같이 함수 선언으로 미리 정의한다. (이것을 추상데이터타입(ADT)이라고 한다) void init(queue_t* q); int is_full(queue_t* q); int is_empty(queue_t* q);..

이번에는 스택을 이용하여 중위표기식을 후위표기식으로 바꾸는 것을 해보자. 실행결과는 다음과 같이 보여주고 싶다. 중위표기식에서 후위표기식으로 바꾸기 위해서는 다음과 같은 사항을 고려해야 한다. (1) 괄호를 처리할 수 있어야 한다. 괄호는 이항연산자가 아니므로 별도로 처리되어야 하고 괄호로 묶인 부분은 최우선으로 실행된다. (2) 이항연산자의 우선순위가 고려되어야 한다. 일단 우리는 다음과 같은 우선순위를 고려한다. 우선순위 연산자 1 &, | (and, or) 2 >, =, 2 - b * c ... 라는 수식을 생각해 보자. >는 -보다 낮고 -는 *보다 낮으므로 *가 수행되고 나서 -와 >가 수행될 수 있다. ... 부분에 >보다 더 낮은 우선순위 연산(&나 |)이 오면 드디어 >는 출력될 수 있다...

앞의 글에서 살펴본 스택의 기본 코드에 입력과 출력을 추가해 보자. 다음과 같은 형식으로 스택 명령을 처리하는 프로그램을 만들어보자. 앞 글에서 살펴본 stack.h와 stack.c를 이용하여 작성하면 된다. typedef int element; 로 정의되어 있으므로 스택의 요소 타입은 int다. #include "stack.h" stack_t stack; // 스택을 지역변수 객체로 선언. 이 변수가 스택객체를 나타낸다. char command[10]; void doit() { elem_t val; scanf_s("%s", command, 10); // 명령을 한 줄씩 읽어서 if (strcmp(command, "end") == 0) { return; } if (strcmp(command, "push"..

후위표기식은 수식을 표현하는 한 방법이다. 일반적으로 우리가 쓰는 표기식은 중위표기식, 즉 이항연산자를 두 개의 피연산자 가운데 쓰는 방법인데, 이것은 사람이 보기에 편리하지만 컴퓨터가 수식을 계산하기에는 매우 불편한 형태다. 그 이유는 우리가 수식을 계산할 때 사용하는 순서를 보면 알 수 있다. 7 + 3 * (5 - 2) + 4 이러한 수식을 계산하기 위해서 우리는 우선순위를 고려해야 한다. 즉 +보다 *가 우선순위가 높고 괄호는 가장 먼저 해야 한다. 그러므로 5-2가 먼저 계산된 후 3*3을 계산하고 그 다음에 7+9를 계산해야 한다. 이 때 수식을 왼쪽부터 차례로 읽어가면서 이러한 순서를 판단하여 계산하려면 매우 복잡한 코드가 필요하다. 이 문제를 해결하기 위해 조상 프로그래머들이 발견한 방법이..