JArchive 프로그래밍 일기

트리란? 

뿌리에서 시작하여 가지, 잎으로 이루어진 나무와 비슷한 자료구조. 

운영체제의 파일 시스템, DOM 구조가 '트리'를 활용합니다. 

트리의  구성 요소 

부모 : 1번 노드는 2,3,4번 노드의 부모입니다. 

자식 : 2,3,4번 노드는 1번 노드의 자식입니다. 

루트(root) : 트리의 맨 꼭대기 '1'번 노드를 루트 노드라고 합니다.

가지 : 트리와 잎노드 사이의 모든 노드들을 뜻합니다. 

잎 노드(terminal node): 가장 끝의 노드, 단말 노드입니다. 

경로 : 3번 노드에서 10번 노드까지의 '경로'는 3, 7, 10 입니다. 

길이 : 3번 노드에서 10번 노드까지 2번 이동해야 하므로, 길이는 2입니다. 

노드의 깊이 : 루트 노드에서 해당 노드까지의 길이입니다. 예를 들어, 6번 노드의 깊이는 2입니다.  

(루트의 깊이는 0 입니다. )

레벨 : 깊이가  같은 노드의 집합입니다. 예를 들어, 2, 3, 4번 노드는 깊이가 1로 같으므로 레벨1 입니다. 

차수 : 자식 노드의 개수 입니다. 

트리의 차수 : 차수가 최대인 노드의 차수. 아래 그림에서는 1번 노드가 자식이 3개여서, 트리의 차수는 3입니다. 

트리 구현

왼쪽 자식-오른쪽 형제 표현법(Left Child Right Sibling)을 이용하여 노드를 만들고 부모 자식을 연결합니다. 

노드

링크드 리스트랑 똑같습니다.

typedef struct Node {
	struct Node* leftChild;
	struct Node* rightSibling;
	int data;
};

노드 생성 및 메모리 해제 

왼쪽 자식을 가리키는 포인터와 오른쪽 형제를 가리키는 포인터를 초기화 해줍니다.  

Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->leftChild = NULL;
	newNode->rightSibling = NULL;
	newNode->data = data;

	return newNode;
}

루트의 왼쪽 자식들 오른쪽 자식들을 free()하고, 루트 자신을 메모리 해제한다. 

/* 트리의 노드 전부 삭제 후, 루트 삭제. */
void FreeTree(Node* rootNode) {

	if (NULL != rootNode->leftChild) {
		FreeTree(rootNode->leftChild);
	}

	if (NULL != rootNode->rightSibling) {
		FreeTree(rootNode->rightSibling);
	}

	rootNode->leftChild = NULL;
	rootNode->rightSibling = NULL;

	FreeNode(rootNode);
}

자식 노드 연결 

부모 노드와 자식 노드 포인터를 매개변수로 입력 받습니다. 

자식이 없다면, 자식에 할당해줍니다. 

자식이 있다면, rightSibling 포인터를 이용하여 마지막 자식을 찾아내서 새 자식(?)을 연결합니다. 

/* 부모에게 자식 연결 */
void ConnectChild(Node** parent, Node* child) {

	if (NULL == (*parent)->leftChild) { // 자식이 없다면, 
		(*parent)->leftChild = child;
	}
	else {// 자식이 있다면, 끝을 찾아서 연결한다.
		Node* lastChild = (*parent)->leftChild;

		while (NULL != lastChild->rightSibling) {
			lastChild = lastChild->rightSibling;
		}

		lastChild->rightSibling = child;
	}
}

트리를 순회하며 출력 

자식과 형제를 출력하기 위해 함수를 재귀 호출 합니다.  

/* 트리 순회하며 출력 */
void Print(Node* node, int depth) {

	int num = 0;

	// 깊이 만큼 들여쓰기 
	for (num = 0; num < depth; num++) {
		printf(" ");
	}

	// 데이터 출력 
	printf("%d\n", node->data);

	// depth를 더해서 자식노드를 출력하도록 함수 재귀 호출 
	if (NULL != node->leftChild) {
		Print(node->leftChild, depth++);
	}

	// 형제노드를 출력하도록 함수 재귀 호출 (depth 유지.)
	if (NULL != node->rightSibling) {
		Print(node->rightSibling, depth);
	}
	
}

자바스크립트 기본 문법을 기록합니다. 

자바스크립트 란 ?

HTML을 동적으로 제어한다. 

개발 환경 구축

VScode 설치 

SourceTree 설치 

GitHub 가입하고 javascript playground 레포지토리 하나 생성 

Atlassian 계정 만들고 sourceTree에 로그인

VScode의 다양한 확장기능 설치 :)

크롬 켜고, Ctrl + i 눌러서 개발자 모드 켜고 끄기!  Console 과 Source 보면서 조작해보자. 

자료형 

어떤 종류의 데이터인지 컴퓨터에게 알려준다. 

자료형이 같아야 연산이 가능하다. 

Number : 정수와 실수 

String : 문자열 (Immutable 특징을 가진다)  '+' 문자열끼리 이어붙일 수 있다. 

Boolean : true  false를 구분 

Null

Undefined 

Object

Immutable 특징이란? 
변경이 불가능한 객체. 한 번 만들면 상태를 변경할 수 없다.
상수 라고 이해하면 좋다. 변형 하려면, 무조건 객체를 새로 만든다. 

자료형 확인해보기 

변수 

데이터를 담은 메모리 공간

변수를 선언하고 값을 할당한다  '='을 사용한다. 

유의 :  '같다'를 표시하는 것은 연산자 === 을 쓴다. '다르다'를 표시하려면 != 를 쓴다. 

문자열의 길이 

문자열을 대소문자로 변환 하는 함수 

undefined : 값이 정의되지 않았다 

null: 값이 비어있다.

NaN: 값이 아니다 (=== 계산이 불가능 )

alter() 와 prompt() 함수 

프롬프트를 띄워서 질문과 입력을 받아본다. 

입력받은 것은 변수에 저장된다. 

프롬프트에 대답을 입력한다. 

Number() 함수

링크드 큐 

링크드 리스트로 만든 큐입니다.

배열로 만든 순환 큐와는 달리 공백/포화를 구분할 필요가 없습니다. 

head 노드에서 제거하고, tail 노드에서 삽입합니다. 

노드 선언과 큐 

노드는 링크드 리스트의 노드와 똑같습니다. 

링크드 큐 구조체는 전단과 후단을 가리킬 포인터와 총 노드 개수 변수를 가집니다. 

typedef struct Node {
	char* data;
	struct Node* nextNode;
};

typedef struct LQ {
	struct Node* front;
	struct Node* rear;
	int nodeCnt;
};

노드 생성과 메모리 해제

void CreateQueue(LQ** lq) {

	(*lq) = (LQ*)malloc(sizeof(LQ));
	(*lq)->front = NULL;
	(*lq)->rear = NULL;
	(*lq)->nodeCnt = 0;
}

삽입

/* 후단에 삽입 */
void Enqueue(LQ* lq, Node* newNode) {

	if (NULL == lq->front) {
		lq->front == newNode;
		lq->rear == newNode;
	}
	else {
		lq->rear->nextNode = newNode;
		lq->rear = newNode;
	}

	lq->nodeCnt++;

}

제거 

/* 전단에서 제거 */
Node* Dequeue(LQ* lq) {

	Node* out = lq->front;

	if (NULL == lq->front->nextNode) {
		lq->front = NULL;
		lq->rear = NULL;
	}
	else {
		lq->front = lq->front->nextNode;
	}

	lq->nodeCnt--;

	return out;
}

큐

큐는 먼저 들어온 일부터 먼저 처리하는 자료구조 입니다. 

선입 선출, First In First Out (FIFO) 라고 합니다. 

큐의 기능 

큐의 가장 앞 요소를 전단, 마지막 요소를 후단이라고 합니다. 

(스택은 최상위 노드가 있는 입구에서만 삽입/제거가 수행됩니다. )

큐는 전단에서 Dequeue (제거) 되고, 후단에서만 Enqueue (삽입) 됩니다. 

순환 큐 

유의할 점은 큐가 비었는지 가득찼는지 구분을 위해 큐를 실제 용량보다 1 크게 만드는 것입니다. 

용량이 7인 큐를 만든다고 하면, 

구현할 때는 8인 큐를 만듭니다. 

비었을 때는 전단과 후단이 같은 곳을 가리킵니다 

큐가 꽉 찼을 때는 후단 바로 다음이 전단이 됩니다. 

이렇게 후단과 전단 사이에 공간을 두어 큐의 상태를 구분합니다. 

후단은 실제 데이터가 있는 칸의 바로 다음칸을 가리키고 있음을 유의해야 합니다.

후단 인덱스는 항상 빈 칸을 가리키고 있어야 합니다. 

순환 큐 구현

노드와 큐 구조체를 선언합니다.

typedef struct Node {
	int data;
};

typedef struct Cqueue {
	int capacity;
	int front;
	int rear;
	Node* nodeArray;
};

Cqueue구조체에서 nodeArray 포인터는 자유저장소에 존재하는 배열의 첫번째 칸을 가리킵니다. 

공백과 포화를 구분하기 위해 실제 capacity + 1하기 위한 '더미 노드'를 하나 둡니다.  

큐를 만들고 메모리 해제하는 함수 

void CreateCqueue(Cqueue** cqueue, int capacity) {

	(*cqueue) = (Cqueue*)malloc(sizeof(Cqueue));

	(*cqueue)->capacity = capacity;
	(*cqueue)->front = 0;
	(*cqueue)->rear = 0;
	(*cqueue)->nodeArray = (Node*)malloc(sizeof(Node) * (capacity + 1));

}

nodeArray 라는 이름의 배열은 사용자가 요구한 용량보다 1개 크게 만들어집니다. 더미 노드를 포함하기 때문입니다. 

void FreeCqueue(Cqueue* cqueue) {

	free(cqueue->nodeArray);
	free(cqueue);
}

삽입(Enqueue)

뒤에서 삽입하니까 rear를 관리합니다. 

rear는 항상 삽입'할' 타겟 인덱스를 가리키고 있습니다.

즉, 빈 공간을 가리키고 있다는 뜻입니다. 

capacity + 1인 인덱스는 공백/포화를 구분할 더미노드의 위치입니다. 

void Enqueue(Cqueue* cqueue, int data) {

	int position = 0;

	if (cqueue->capacity + 1 == cqueue->rear) {
		position = cqueue->rear;
		cqueue->rear = 0;
	}
	else {
		position = cqueue->rear++;
	}

	cqueue->nodeArray[position].data = data;
}

제거(Dequeue)

앞에서 제거하니까 front를 관리합니다. 

front와 capacity가 같은 상황은 전단이 배열 맨 끝에 와있다는 것입니다. 

노드를 하나 제거 하면, 인덱스를 0으로 돌려놔야 합니다. 

이 경우를 제외하면 front를 하나 감소시키면 됩니다.

int Dequeue(Cqueue* cqueue) {

	int position = cqueue->front;

	if (cqueue->front == cqueue->capacity ) {
		cqueue->front = 0;
	}else{
		cqueue->front++;
	}
	
	return cqueue->nodeArray[position].data;
}

큐의 공백과 포화 확인하기 

공백 : front 와 rear 가 같은 곳을 가리키고 있습니다. 

int IsEmpty(Cqueue* cqueue) {
	return 	(cqueue->front == cqueue->rear);
}

포화: rear의 바로 다음이 front 입니다. 또는 rear에서 front를 빼면 그 길이가 capacity가 됩니다. 

int IsFull(Cqueue* cqueue) {
	if (cqueue->front < cqueue->rear) {
		return (cqueue->rear - cqueue->front == cqueue->capacity);
	}
	else {
		return (cqueue->front == cqueue->rear + 1);
	}
}

메인함수 - 삽입/제거 해보기 

5개를 저장할 수 있는 배열을 만들고, 8번 삽입, 6번 제거해봤습니다. 

삽입 전에 포화인지 검사하고 포화이면 탈출합니다. 

제거 전에 비었는지 검사하고 비었으면 탈출합니다. 

int main(void) {

	int i = 0; 
	Cqueue* queue;

	// 5개를 저장할 수 있는 배열 
	CreateCqueue(&queue, 5);

	// 8번 삽입 
	for (int cnt = 1; cnt < 9; cnt++) {
		if (!IsFull(queue)) {
			printf("%d를 삽입.\n", cnt);
			Enqueue(queue, cnt);
		}
		else {
			printf("큐가 꽉 찼습니다.\n");
			break;
		}
	}

	// 6번 제거
	for (int cnt = 1; cnt < 7; cnt++) {
		if (!IsEmpty(queue)) {
			printf("%d 를 제거.\n", Dequeue(queue));
		}
		else {
			printf("큐가 비었습니다.\n");
			break;
		}
	}

	return 0;
}

오늘 한 일 

잠시 놓았던 자료구조를 다시 봤다. (링크드 리스트, 스택, 큐, 트리)

생각거리 

3월 3일(화) ~ 3월 5일(목) 3일 동안 할아버지를 잘 보내드리고 왔다. 할아버지 이제 할머니 곁에서 편히 쉬세요. 

오늘 한 일 

스택으로 사칙연산 함수, 큐, 트리 기본구조를 공부했다. 

내일은 코딩에 비중을 두고 진행해야겠다. 

생각거리 

공부 집중을 위해 공부하는 공간을 바꿔보는 것도 가끔 해볼 만한 시도다.

오늘 한 일 

스택을 응용하여 사칙연산 계산을 하는 함수를 만들고 있다. 

책에 나온 코드를 참고하려고 하는데, 애를 먹었다.

생각거리 

사칙연산 계산 함수가 하루 안에는 끝날 줄 알았는데. 

이해 안가는 것이 한 두개가 아니었고 힘들었다. 

오늘 한 일 

알고리즘 스터디에서 더블,환형 링크드 리스트, 스택, 큐를 공부했다. 

나는 배열로 짜는 스택, 리스트로 짜는 스택을 맡았고,

스터디원은 리스트와 큐를 맡았다. 

리스트로 짜는 스택을 만들 때 불필요해 보이는 코드가 있어서 같이 고민했다. 

다음주에는 내가 스택으로 짜는 사칙연산과 큐를 준비해가기로 했다. 

생각거리

알고리즘 공부를 오랜만에 하려니 쉽지가 않다. 

그래도 이정도 해내가고 있는 것에 자신감을 갖고 화이팅해야지.

코로나가 4월에 피크라는데, 앞으로 2달동안은 정말 몸사리면서 주의해야겠다.

더 이상 확진자가 안나왔으면 좋겠다. 

오늘 한 일 

배열로 스택을 짰다. 

링크드 리스트로 스택을 짰다. 

생각거리 

스택 짜는게 약간 헷갈린다. 

내일은 사칙연산계산기를 스택으로 짜보고, 큐를 공부할 계획이다. 

윈도우 시스템 프로그래밍 책을 보다가 막힌 부분이 있었다. 매크로가 기억이 안난다. 

기본서를 다시 봐야겠다. 

오늘 한 일 

SQLD 모델링쪽 공부했다. 

리스트를 다시 짜봤다. 

배열로 스택을 다시 짜봤다. 

생각거리

연차가 끝나고 실질적으로 회사에 안나간지 25일이 지났다. 거의 한달.

시간이 빠르다. 

SQLD 시험이 코로나 때문에 4월 11일로 연기되서 맥빠진다. 

코로나 확진자가 977명이다. 조심하자 조심!