프린세스 다이어리

1. 이진 트리 노드 구현 이진 트리는 부모가 왼쪽 자식, 오른쪽 자식을 가지고 있다는 점에서 포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능하다. 노드 구조체는 다음과 같다. #include #include typedef struct Node { int data; struct Node *leftChild; struct Node *rightChild; } Node; 하나의 노드는 내부적으로 하나의 data를 가지고 있다. 여기 예시 코드에서는 정수형 데이터 하나만 들어가는 걸로 설정했지만, 실제로는 다양한 데이터가 data에 들어갈 수 있다. 특정 노드를 초기화하는 함수는 다음과 같다. Node* initNode(int data, Node* leftChild, Node* rightChild) { ..

1. 트리란 트리는 나무를 뒤집어 놓은 형태의 자료구조다. 일반적으로 트리의 최상단 노드를 루트 노드라고 하고, 루트 노드에서 가지를 이용해서 각각의 노드로 연결되며, 가장 마지막에 해당하는 원소들을 리프 노드라고 부른다. 또한 트리는 기본적으로 부모와 자식 간의 관계로 이루어져 있다. 가지로 연결된 관계에서 루트 노드에 가까운 노드를 부모 노드, 리프 노드에 가까운 노드를 자식 노드라고 한다. 트리 구조에서 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다. 가지를 2번 거쳐서 1번 노드에서 35번 노드까지 간다면, 길이가 2가 되는 것이다. 깊이란 루트 노드에서 특정 노드까지의 길이를 의미한다. 높이는 가장 높은 노드부터 가장 깊은 노드까지의 길이를 의미한다. 2. 이진 트리란 이진..

1. 퀵 정렬이란 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다. 퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다. 피벗 값이 가장 왼쪽이라고 가정한다. 5 4 3 8 9 6 7 1 10 2 (1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해..

1. 선택 정렬 1-1. 선택 정렬의 원리 선택 정렬이란, 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산을 하기 때문에 O(N2)의 시간 복잡도를 가진다. 이렇게 초기 원소가 있다고 했을 때, 2 4 3 1 9 6 7 8 10 5 가장 작은 원소는 1이므로 맨 앞으로 보내준다. 기존의 맨 앞에 있었던 원소와 자리를 바꿔준다. 1 4 3 2 9 6 7 8 10 5 나머지 원소 중 가장 작은 값인 2를 1 다음으로 넣어 주고 마찬가지로 그 자리에 있었던 원소와 자리를 바꿔준다. 1 2 3 4 9 6 7 8 10 5 이렇게 해서 결과적으로 올림차순으로 정렬할 수 있는 것이다. 1 2 3 4 5 6 7 8 9 10 1-2. 선택 정렬..

1. 연결 리스트, 큐 구조체 만들기 #include #include #define INF 99999999 typedef struct Node { int data; struct Node *next; } Node; typedef struct Queue { Node *front; Node *rear; int count; } Queue; Queue에는 front, rear, 그리고 큐에 들어가 있는 원소들의 개수를 count로 정했다. 2. push 함수 구현하기 큐는 rear가 가리키는 노드 뒤쪽에 들어가기 때문에, 먼저 노드를 뒤에 만들어 놓고 rear의 next가 그 노드를 가리키게 만든 다음에, rear가 그 노드를 가리키도록 하면 된다. void push(Queue *queue, int data) {..

연결 리스트 구조체를 만드는 과정에서 다음과 같은 에러가 발생했다. #include #include typedef struct { int data; struct Node *next; } Node; Node *head; int main(void) { head = (Node*) malloc(sizeof(Node)); Node *node1 = (Node*) malloc(sizeof(Node)); node1 -> data = 1; Node *node2 = (Node*) malloc(sizeof(Node)); node2 -> data = 2; head -> next = node1; node1 -> next = node2; node2 -> next = NULL; Node *cur = head -> next; whi..

전처리기 구문은 다른 프로그램 영역과 독립적으로 처리되고, 소스코드 파일 단위로 효력이 존재한다는 특성이 있다. 전처리기 사용은 필수는 아니다. C언어에서는 보다 이식성, 생산성 높게 안정적으로 코드를 작성하기 위해 활용된다. 1. 파일 포함 전처리기 1. #include는 전처리기에서 가장 많이 사용되는 문법이다. 2. 특정한 파일을 라이브러리로서 포함시키기 위해 사용한다. 3. #include 구문으로 가져올 수 있는 파일에는 제약이 없다. #include "filename" #include 특정한 외부 파일을 라이브러리의 형식으로 현재 소스에 불러오기 위해서 사용한다. 어떤 파일이든 현재의 소스코드 파일로 가져올 수 있고 이 include라는 전처리 구문 자체를 그 파일의 전체 소스코드로 대체한다는..

1. 파일 입출력의 필요성 프로그램이 꺼진 이후에도 데이터를 저장하기 위해서는 파일 입출력이 필요하다. 예를 들어, 게임을 껐다 켰는데 다시 캐릭터를 처음부터 만들어야 한다면 시간 버린 느낌이 들 것이다. 즉, 어떠한 데이터를 프로그램 안에서만 사용하는 게 아니라, 프로그램의 외부에 일시적으로 저장을 해 놨다가 프로그램을 다시 실행시킬 때 다시 불러올 수 있도록 하는 역할을 한다. 흔히 SSD, RAM, CPU는 일반적으로 컴퓨터에 들어가는 부품이다. 이 중 파일이 실질적으로 저장이 되는 위치를 고르라면, 바로 SSD다. 컴퓨터 아키텍처마다 조금씩 차이는 있겠지만 램과 CPU는 휘발성이 있다는 특징이 있다. 그래서 바탕화면 등에 있는 파일은 SSD와 같은 보조기억장치에 저장되고, 그것을 더블클릭해서 실행..