프린세스 다이어리

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. 퀵 정렬이란 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 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. Node, Stack, push, pop, getTop 정의해주기 #include #include #include #define INF 99999999; typedef struct Node { int data; struct Node *next; } Node; typedef struct Stack { Node *top; int count; } Stack; void push(Stack *stack, int data) { Node *node = (Node*) malloc(sizeof(Node)); node -> data = data; node -> next = stack -> top; stack -> top = node; stack -> count++; } i..

1. 중위 표기법과 후위 표기법 뜻 중위 표기법이란, 일반적으로 사람이 수식을 표기할 때 사용하는 표기 방법이다. 흔히 우리는 두 개의 피연산자가 있고 한 개의 연산자가 있을 때, 피연산자 사이에 연산자가 들어갈 수 있도록 표기를 한다. 그러나 컴퓨터가 좋아하는 방식은 후위 표기법이다. 후위 표기법은 연산자가 뒤쪽에 위치한다. 중위 표기법: 7 * 9 + 2 후위 표기법: 7 9 * 2 + 2. 기본적인 구조체와 push, pop 함수 만들기 #include #include #include // 문자열을 처리할 거기 때문에 typedef struct Node{ char data[100]; // 하나의 문자열을 담을 수 있도록. 숫자 또는 연산자 등 다양한 형태가 들어가기 떄문에. struct Node *..

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

1. 가비지가 무엇이고, 왜 가비지 컬렉터가 필요한가요? 가비지 콜렉터(Garbage Collector)는 애플리케이션이 실행될 때, 메모리에 저장은 되어 있지만 어디에서도 사용되지 않는 변수를 알아서 메모리에서 치워 주는 관리 방법이다. 제대로 이해하기 위해서는 먼저 가비지, 즉 쓰레기 메모리가 무엇이고 왜 생기는지를 알아야 한다. 이전에 업로드한 동적 메모리 할당의 개념을 정리한 글과 내용이 일부 중복되어 있다. 일반적으로 C에서 배열을 선언할 때, 사전에 적절한 크기만큼 할당해 준다. int a[20] = "hello world"; 그런데 항상 사전에 메모리를 할당해주는 게 아니라, 프로그램 실행 도중에 필요시 메모리를 할당해야 할 때가 있다. C에서는 malloc() 함수를 사용해, 원하는 만큼의..

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