TWpower Reading time ~1 minute

MailReminder 프로젝트 개발기


목차


개발 시작 이유

  • MailReminder라는 이름부터 즉흥적으로 지었는데… 일을 시작하고 살다보니까 도장비 입금이나 병원 신청같은 부분을 매달 알려줬으면 좋겠는데 단순한 일이라서 캘린더에는 추가하기 싫고 메일로 알림을 받으면 좋을거 같아서 개발을 시작하게 되었다.


목표

  • 최종적으로는 어떤 모습이 될지는 모르겠으나… 내가 원하는 날짜에 알림을 신청하면 메일로 알려주는 서비스를 나를 위해 만들고 싶다.
  • 추후 모습이 바뀔수도 있고 현재 내 요구사항은 등록한 사항을 원하는 날짜에 알려주자!
  • 스스로 애자일과 린 소프트웨어 개발론을 통해 개발할 예정! 물론, 나중에 개발 방법이 어떻게 바뀔지는 모르겠지만.. 우선 만들고 싶은 한 가지의 목표를 정하고 구현하고 불편한거 개선해서 추가하고 하는 방식으로 가보자


환경 및 구조

방법 설명

  • 메일을 보내주는 부분은 python을 이용해서 작성한다.
  • 리눅스에 있는 crontab을 이용해서 원하는 날짜에 메일을 보내도록 한다.
  • 메일을 보내주는 부분은 직접 smtp 서버를 만들고 도메인에 붙일수도 있지만… 빠른 개발을 위해서 우선 Google에 계정을 만들고 해당 계정으로 메일을 보내도록 했다.(최소한으로 필요한 부분을 제외하고 다른 부분들은 다 쓸 수 있는걸 가져다가 쓰자!)
  • 잘 보내졌는지 확인하기 위해 로그를 남겼습니다.(stdout으로 나오게 하고 파일로 redirection함)


코드 구현

공통

  • 계정 정보를 저장하는 account.json의 경우에는 개인 정보이니 .gitignore에 추가했다.


메인 구현 부분

reminder.py

import smtplib
from email.mime.text import MIMEText
import json
import datetime

def sendMail(sender_email, receiver_email, app_password ,msg):
    smtp = smtplib.SMTP_SSL('smtp.gmail.com', 465)
    print(str(datetime.datetime.now()) + ": " + "Access Success")
    smtp.login(sender_email, app_password)
    print(str(datetime.datetime.now()) + ": " + "Login Success")
    msg = MIMEText(msg)
    msg['Subject'] = '리마인더'
    smtp.sendmail(sender_email, receiver_email, msg.as_string())
    print(str(datetime.datetime.now()) + ": " + "Sending Success")
    smtp.quit()

email=""
app_password=""
with open('/home/twpower/MailReminder/account.json') as account_json_file:
    account = json.load(account_json_file)
    email = account['email']
    app_password = account['app_password']
    print(str(datetime.datetime.now()) + ": " + "Parsing Success")

# 나한테 보내는 메일 정보는 없음... 개인정보라서
sendMail(email, '', app_password, "입금 or 예약")

crontab

# 쉘은 bash를 사용했고 환경 변수들을 다 가져왔습니다.(PATH를 포함!)
# 환경 변수를 가져와야 일반적인 쉘과 환경이 같아지며 python 경우에는 사용하는 인터프리터 path 정보가 거기에 담겨 있기 때문에 가져오는게 좋습니다.(처음에 안해줘서 자꾸 오류떴던...)
...
* 10 17 * * python /home/twpower/MailReminder/reminder.py >> /home/twpower/test.txt
...


다음 목표

  • 우선 사용이 잘 되면 api를 통해서 on/off를 할 수 있는 기능을 만들어보고 싶다. 필요없을 때 서버에 들어가서 끄기는 귀찮으니…


참고자료

TWpower Reading time ~1 minute

Python에서 JSON 파일을 읽어서 파싱해보자


환경 및 선수조건

  • Python(3.X)


with문과 json 모듈을 이용해서 파싱

  • with문과 json모듈을 이용하면 dictionary로 쉽게 사용이 가능하다.
import json # import json module

# with statement
with open('json file path or name') as json_file:
    json_data = json.load(json_file)

    ...


예제

example.json

{
    "json_string": "string_example",
    "json_number": 100,
    "json_array": [1, 2, 3, 4, 5],
    "json_object": { "name":"John", "age":30},
    "json_bool": true
}


example.py

import json

# with를 이용해 파일을 연다.
# json 파일은 같은 폴더에 있다고 가정!

with open('example.json') as json_file:
    json_data = json.load(json_file)

    # 문자열
    # key가 json_string인 문자열 가져오기
    json_string = json_data["json_string"]
    print(json_string)

    # 숫자
    # key가 json_number인 숫자 가져오기
    json_number = json_data["json_number"]
    print(str(json_number)) # 숫자이기 때문에 str()함수를 이용

    # 배열
    # key가 json_array인 배열 가져오기
    json_array = json_data["json_array"]
    print(json_array)

    # 객체
    # key가 json_object인 객체 가져와서 만들기
    # json object의 경우에 python ojbect로 바꿀때는 따로 처리를 해줘야합니다.
    # 기본형은 dictionary입니다.
    json_object = json_data["json_object"]
    print(json_object)

    # bool형
    # key가 json_bool인 bool형 자료 가져오기
    json_bool = json_data["json_bool"]
    print(json_bool)


참고자료

TWpower Reading time ~12 minutes

업데이트(2019.02.04): 중복 및 map 관련 검증 에러 수정

업데이트(2019.01.19): 코드 수정 및 검증 코드 추가

C++에서 해시 테이블(Hash Table)을 구현해보자


환경

  • C++
  • 연결 리스트와 해시 함수에 대한 이해(제일 하단 참고자료 참고)


해시 함수(Hash Function)

해시 함수(Hash Function)란?

  • Hash Function: 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이 때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다.(H(s1) = H(s2))
  • 아래 사진의 경우에는 좌측에 파란 색들이 key이며 각 key값들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시 테이블에서는 이 key을 해시한 결과를 배열의 인덱스로 사용한다.
  • 해시 함수를 H()라고 했을 때 H(Jonh Smith) = 02


해시 충돌(Hash Collision)

  • 서로 다른 문자열을 해시한 결과가 동일한 경우
  • 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s1) = H(s2)인 경우
  • 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing을 통해서 해결해야한다.


예시

  • 아래는 아주 간단한 해시 함수의 예제로 문자열을 받아서 정수로 반환한다.
  • 검색해보면 다양한 구현법이 존재하며 Shift연산과 소수를 이용해서 하면 더 해시 충돌을 막을 수 있다고 한다.(나중에 증명 같은건 찾아봐야지…)
int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}


해시 테이블(Hash Table)

  • key와 value로 된 쌍을 저장하는 자료구조이다.
  • 아래 사진처럼 Lisa Smith라는 key로 521-8976의 value를 저장할 수 있도록 설계된 자료구조입니다.
  • C++에서는 map 그리고 python에서는 dictionary를 통해서 보다 쉽게 이용할 수 있습니다.(여기서는 한번 구현해 보는것에 의의!)
  • 성능이 좋을 때는 O(c)에 접근을 할 수 있기 때문에 공간을 소비해서 접근속도를 늘리고 싶을 때 이용한다. 물론, O(c)도 해시 테이블의 용량이 엄청 크고 해시 함수도 충돌이 일어나지 않는다는 가정이 있을 때 가능하다.
  • 해시 테이블을 구현할 때 해시 충돌이 일어나게 되면 Chaining 혹은 Open Addressing을 통해서 해결해야한다.


구현

  • 여기서는 충돌일 있을때 Chaining을 이용했으며 Singly Linked List(단순 연결 리스트)를 이용해서 작성하였다.

공통

  • key에 따른 데이터들은 Chaining을 이용했기 때문레 List로 해시테이블을 구현
  • 데이터를 저장하는 Node 선언
  • #define에 나와있는 값을 조절해서 테이블의 크기나 해시 테이블에 집어넣을 데이터의 수를 조절할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_TABLE 5 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 6 // 삭제할 데이터의 수
#define FIND_COUNT 8 // 찾을 데이터의 수

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들


초기화 함수

  • 랜덤 함수를 이용해서 key-value쌍들을 생성합니다.
void init() {

	// 해시테이블 초기화
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// key에 대응하는 값들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}


문자열 함수

  • 복사와 비교 함수 직접 작성(따로 사용해도 무방!)
void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}


해시 함수

  • 위에 소개했던 내용과 동일하게 Shift연산과 소수를 이용함
  • 해시 테이블의 인덱스로 활용하기 때문에 반드시 MAX_TABLE의 나머지를 반환해야함
int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}


추가

  • 일반적인 추가와 같으며 중복된 key가 있을 경우에는 값을 바꿉니다.
void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = hash(key);

	if (tb[index] == NULL) {
		tb[index] = new_node;
	}

	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// key가 중복이면 값을 바꾸기
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}

		// 중복이 아니면 앞에다가 추가
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}


값 찾기

  • 리스트를 이용하면 어렵지 않게 찾을 수 있습니다. 쭉 리스트를 따라가면서 순회하고 값을 찾으면 됩니다.
  • 값이 있으면 val에 저장하고 true를 반환하고 아니면 false를 반홥합니다.
bool find(const char * key, int * val) {

	int index = hash(key);

	Node * cur = tb[index];

	// 하나하나 찾아가면서 확인
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}


삭제

  • 삭제도 리스트를 이용하면 쉽게 할 수 있으며 첫번째 삭제만 주의해주면 됩니다.
bool destroy(const char * key) {

	int index = hash(key);

	// 처음이 비어있는지 확인
	if (tb[index] == NULL) {
		return false;
	}

	// 첫번째
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// 나머지의 경우
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

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


출력

  • 테이블의 배열을 모두 돌고 각각의 원소를 순회하면서 key-value쌍을 출렵합니다.
void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index: %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}


메인

  • 추가, 삭제 그리고 찾는 과정을 코드로 작성하여 테스트 하였습니다.
int main() {

	char tmp_key[MAX_KEY];
	init();

	// Add

	printf("Add to hash table\n");
	for (int i = 0; i < MAX_DATA; ++i) {
		add(keys[i], values[i]);
	}

	print_hash();


	printf("\n");

	// Delete

	printf("Deleted keys: ");
	for (int i = 0; i < DELETE_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		printf("%s ", tmp_key);
		destroy(tmp_key);
	}
	printf("\n");

	print_hash();


	printf("\n");

	// Find

	int val;
	printf("Found: ");
	for (int i = 0; i < FIND_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		if (find(tmp_key, &val)) {
			printf("{ %s, %d } ", tmp_key, val);
		}
	}
	printf("\n");

	return 0;
}


코드

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

#define MAX_TABLE 5 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 6 // 삭제할 데이터의 수
#define FIND_COUNT 8 // 찾을 데이터의 수

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들

void init() {

	// 해시테이블 초기화
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// key에 대응하는 값들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}

void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}

int hash(const char * str) {
	int hash = 401;
	int c;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = hash(key);

	if (tb[index] == NULL) {
		tb[index] = new_node;
	}

	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// key가 중복이면 값을 바꾸기
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}

		// 중복이 아니면 앞에다가 추가
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}

bool find(const char * key, int * val) {

	int index = hash(key);

	Node * cur = tb[index];

	// 하나하나 찾아가면서 확인
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}

bool destroy(const char * key) {

	int index = hash(key);

	// 처음이 비어있는지 확인
	if (tb[index] == NULL) {
		return false;
	}

	// 첫번째
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// 나머지의 경우
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

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

void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index: %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}

int main() {

	char tmp_key[MAX_KEY];
	init();

	// Add

	printf("Add to hash table\n");
	for (int i = 0; i < MAX_DATA; ++i) {
		add(keys[i], values[i]);
	}

	print_hash();


	printf("\n");

	// Delete

	printf("Deleted keys: ");
	for (int i = 0; i < DELETE_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		printf("%s ", tmp_key);
		destroy(tmp_key);
	}
	printf("\n");

	print_hash();


	printf("\n");

	// Find

	int val;
	printf("Found: ");
	for (int i = 0; i < FIND_COUNT; ++i) {
		my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
		if (find(tmp_key, &val)) {
			printf("{ %s, %d } ", tmp_key, val);
		}
	}
	printf("\n");

	return 0;
}


검증

  • hash 함수명이 충돌나서 변경(hash->my_hash)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <map>
#include <string>

#define TOTAL_TEST_CASE 100

#define MAX_TABLE 300 // 테이블 크기
#define MAX_KEY 8 // include null
#define MAX_DATA 2000 // 해시테이블에 넣을 데이터의 수
#define DELETE_COUNT 1000 // 삭제할 데이터의 수

using namespace std;

struct Node {
	char key[MAX_KEY];
	int value;
	Node * next;
};

Node * tb[MAX_TABLE]; // 해시 테이블(해당 인덱스에 리스트로 작성)
char keys[MAX_DATA][MAX_KEY]; // 문자열 key들
int values[MAX_DATA]; // key에 대응하는 값들

void init() {

	// 해시테이블 초기화
	for (int i = 0; i < MAX_TABLE; ++i) {
		Node * cur = tb[i];
		Node * tmp;
		while (cur != NULL) {
			tmp = cur;
			cur = cur->next;
			free(tmp);
		}
		tb[i] = NULL;
	}

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// key에 대응하는 값들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		values[i] = rand() % 100 + 1;
	}

	// 문자열 key들 초기화
	for (int i = 0; i < MAX_DATA; ++i) {
		for (int j = 0; j < MAX_KEY - 1; ++j) {
			keys[i][j] = rand() % 26 + 97; // ASCII 97 ~ 122
		}
		keys[i][MAX_KEY - 1] = '\0';
	}

}

void my_str_cpy(char * dest, const char * src) {

	while (*src != '\0') {
		*dest = *src;
		dest++; src++;
	}
	*dest = '\0';

}

int my_str_cmp(const char * str1, const char * str2) {

	while (*str1 != '\0' && (*str1 == *str2)) {
		str1++;
		str2++;
	}
	return *str1 - *str2;

}

int my_hash(const char * str) {
	int hash = 401;

	while (*str != '\0') {
		hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
		str++;
	}

	return hash % MAX_TABLE;
}

void add(const char * key, int value) {

	Node * new_node = (Node *)malloc(sizeof(Node));
	my_str_cpy(new_node->key, key);
	new_node->value = value;
	new_node->next = NULL;

	int index = my_hash(key);

	// 처음이 비어있으면 할당
	if (tb[index] == NULL) {
		tb[index] = new_node;
	}
	// 아니면 하나하나 찾아서 중복이면 치환 아니면 제일 뒤에 추가
	else {

		Node * cur = tb[index];

		while (cur != NULL) {

			// key가 중복이면 값을 바꾸기
			if (my_str_cmp(cur->key, key) == 0) {
				cur->value = value;
				return;
			}

			cur = cur->next;
		}
		// 중복이 아니면 앞에다가 추가
		new_node->next = tb[index];
		tb[index] = new_node;
	}
}

bool find(const char * key, int * val) {

	int index = my_hash(key);

	Node * cur = tb[index];

	// 하나하나 찾아가면서 확인
	while (cur != NULL) {
		if (my_str_cmp(cur->key, key) == 0) {
			*val = cur->value;
			return true;
		}
		cur = cur->next;
	}

	return false;

}

bool destroy(const char * key) {

	int index = my_hash(key);

	// 처음이 비어있는지 확인
	if (tb[index] == NULL) {
		return false;
	}

	// 첫번째
	if (my_str_cmp(tb[index]->key, key) == 0) {
		Node * first = tb[index];
		tb[index] = tb[index]->next;
		free(first);
		return true;
	}

	// 나머지의 경우
	else {

		Node * cur = tb[index]->next;
		Node * prev = tb[index];

		while (cur != NULL && my_str_cmp(cur->key, key) != 0) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

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

void print_hash() {

	for (int i = 0; i < MAX_TABLE; ++i) {
		if (tb[i] != NULL) {

			printf("index: %d\n", i);

			Node * cur = tb[i];

			while (cur != NULL) {
				printf("{ %s, %d }, ", cur->key, cur->value);
				cur = cur->next;
			}
			printf("\n");
		}
	}

}

int main() {

	int test_case = 1;
	int correct = 0;


	for (test_case = 1; test_case <= TOTAL_TEST_CASE; ++test_case) {

		init();

		bool is_equal = true;

		map<string, int> m;
		map<string, int>::iterator it;


		for (int i = 0; i < MAX_DATA; ++i) {
			add(keys[i], values[i]);
		}
		for (int i = 0; i < MAX_DATA; ++i) {
			if (m.count(keys[i]) == 0) {
				m.insert(make_pair(keys[i], values[i]));
			}
			else {
				m[keys[i]] = values[i];
			}

		}

		for (int i = 0; i < MAX_DATA; ++i) {

			int tmp;
			find(keys[i], &tmp);

			if (m[keys[i]] != tmp) {
				is_equal = false;
			}
		}

		char tmp_key[MAX_KEY];
		for (int i = 0; i < DELETE_COUNT; ++i) {
			my_str_cpy(tmp_key, keys[rand() % MAX_DATA]);
			destroy(tmp_key);
			m.erase(tmp_key);
		}

		for (int i = 0; i < MAX_DATA; ++i) {

			int tmp = -1;

			if (find(keys[i], &tmp) == false && m.count(keys[i]) == 0) {
				continue;
			}

			if (find(keys[i], &tmp) == true && m.count(keys[i]) == 1 && m[keys[i]] == tmp) {
				continue;
			}
			else {
				is_equal = false;
			}

		}

		if (is_equal) correct++;

	}

	printf("Total: %d / %d\n", correct, TOTAL_TEST_CASE);

	return 0;
}


참고자료

TWpower Reading time ~1 minute

업데이트(2018.03.16): 옵션 및 설명 추가

Linux 기반 운영체제에서 scp 명령어를 사용해서 로컬-원격 사이에 파일을 주고 받아보자.


환경 및 선수조건

  • Linux
  • Bash shell(/bin/bash)


scp 명령어

기본

  • scp: secure copy (remote file copy program)의 줄임말로 ssh를 이용해 네트워크로 연결된 호스트간에 파일을 주고 받는 명령어입니다.
  • 로컬 -> 리모트 (보내기), 리모트 -> 로컬 (가져오기)와 리모트 -> 리모트 (다른 호스트끼리 전송) 로 복사가 모두 가능합니다.
  • ssh를 이용하기 때문에 password를 입력하거나 ssh 키파일과 같은 identity file을 이용해 파일 송수신이 가능합니다.


기본 사용 문법

  • manual page에 있는 자료
scp [options ...] [source] [target]
  • 기본 형태
# Local -> Remote
scp 목적파일명(경로) 유저명@IP주소:목적디렉토리

# Remote -> Local
scp 유저명@IP주소:파일디렉토리 목적파일명(경로)

# Remote(source) -> Remote(target)
scp 유저명@IP주소:파일디렉토리 유저명@IP주소:파일디렉토리


옵션

  • -r: 재귀적으로 모든 폴더들을 복사합니다. 폴더를 복사할 때 사용하는 옵션으로 이때 전송하고자 하는 대상은 폴더로 지정하면 됩니다. 아래에 예제를 참고하시면 됩니다. symbolic link가 있는 경우에는 target에 symbolic link를 생성하지 않고 symbolic link가 가리키는 파일 혹은 폴더를 복사합니다.
  • -P: ssh 포트를 지정하는 옵션
  • -i: ssh 키파일과 같은 identity file의 경로를 지정하는 옵션
  • -v: verbose 모드로 상세내용을 보며 디버깅을 할 때 사용합니다.
  • -p: 파일의 수정 시간과 권한을 유지합니다.


예제

로컬 -> 리모트

  • 패스워드 사용하는 경우
scp ~/test.txt twpower@[IP주소]:/home/twpower
  • -i 옵션
  • identity file을 지정해서 사용할 때
scp -i ~/.ssh/twpower-private-server ~/test.txt twpower@[IP주소]:/home/twpower
  • -r 옵션
  • 폴더를 복사하는 경우
scp -r ~/test_folder/ twpower@[IP주소]:/home/twpower
  • -P 옵션
scp -P 22 ~/test.txt twpower@[IP주소]:/home/twpower


리모트 -> 로컬

  • 패스워드 사용하는 경우
scp twpower@[IP주소]:/home/twpower/test.txt /Users/taewoo
  • -i 옵션
  • identity file을 지정해서 사용할 때
scp -i ~/.ssh/twpower-private-server twpower@[IP주소]:/home/twpower/test.txt /Users/taewoo
  • -r 옵션
  • 폴더를 복사하는 경우
scp -r twpower@[IP주소]:/home/twpower/test_folder /Users/taewoo
  • -P 옵션
scp -P 22 twpower@[IP주소]:/home/twpower/test.txt /Users/taewoo


참고자료

TWpower Reading time ~5 minutes

업데이트(2019.01.19): 코드 수정 및 검증 코드 추가

C++에서 힙(Heap)을 구현해보자


환경

  • C++


Heap이란?

개념

  • Heap이란 완전 이진 트리의 일종으로 부모 노드와 자식 노드간에 항상 대소관계가 성립하는 자료구조를 의미합니다.
  • 아래의 사진을 보면 부모 노드가 자식 노드보다 항상 크며 이러한 구조를 최대힙(Max Heap)이라고 하고 그 반대를 최소힙(Min Heap)이라고 합니다.
  • 이 때 부모와 자식 노드의 대소관계만 중요하며 형제 노드들간에는 관계가 없습니다.
  • 이렇게 아래처럼 구현하고 위와 같은 속성(부모와 자식간에 대소관계)을 띄기 때문에 최상단 부모인 루트에는 항상 가장 크거나 작은 값이 오며 이를 이용해서 그 유명한 우선 순위 큐(Priority Queue)의 구현이 가능합니다.


구현

공통

  • 완전 이진 트리는 배열로 구현합니다.
  • 구현을 쉽게 하기 위해 배열을 사용할 때 인덱스는 1부터 사용합니다.
  • 특정 노드의 배열 인덱스가 current라고 한다면 부모 노드는 current / 2를 통해 찾아갈 수 있고 자식 노드는 current * 2(좌측 자식 노드) 또는 current * 2 + 1(우측 자식 노드)을 통해서 찾아갈 수 있습니다.
  • 현재 노드 인덱스: current
  • 부모 노드 인덱스: current / 2
  • 자식 노드들 인덱스 (순서 대로 좌우): current * 2, current * 2 + 1


삽입

  • 완전 이진 트리 가장 끝에 원소를 추가하고 추가한 부분의 원소와 해당 원소의 부모 노드와 크기를 비교하고 바꿔가면서 위치를 찾습니다.
void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}


삭제

  • 힙의 가장 첫번째 원소를 반환하고 첫번째 위치에 힙의 가장 끝 원소를 대입합니다.
  • 첫번째 원소를 자식과 계속 비교하고 값을 바꿔가면서 힙을 재정렬합니다.
  • 이 때, 자식은 왼쪽과 오른쪽 2개가 생기기 때문에 최대힙을 구현하는 경우에는 더 큰 자식과 값을 바꿉니다.(최소힙일 때는 그 반대!)
int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}


코드

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

#define HEAP_SIZE 256
#define ARRAY_SIZE 10

// Max Heap 구현
// 구현을 쉽게 하기 위해서 값들은 모두 양수라고 가정!
// 배열에서 값 0은 비어있음을 의미한다고 가정하자!
// heap은 배열의 인덱스가 1부터 시작합니다!

int heap[HEAP_SIZE]; // max heap
int heap_count = 0; // heap의 원소의 갯수를 나타냄과 동시에 배열의 가장 끝 원소를 나타내며 heap의 끝을 나타내기도 합니다.

void swap(int * a, int * b) {
	int tmp = *a; *a = *b; *b = tmp;
}

void init() {
	heap_count = 0;
}

int size() {
	return heap_count;
}

void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}

int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}

int main() {

	int arr[ARRAY_SIZE];

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 배열 초기화
	for (int i = 0; i < ARRAY_SIZE; i++) {
		// 1 ~ 50까지의 난수 생성
		arr[i] = rand() % 50 + 1;
	}

	// 삽입
	for (int i = 0; i < ARRAY_SIZE; i++) {
		push(arr[i]);
	}

	// pop 하면서 값들 하나씩 확인
	// Max Heap이기 때문에 값들이 내림차순으로 정렬됨 -> Heap Sort
	for (int i = 0; i < ARRAY_SIZE; i++) {
		printf("%d ", pop());
	}
	printf("\n");

	return 0;
}


검증

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <functional>

#define HEAP_SIZE 256
#define TOTAL_TEST_CASE 100
#define TEST_ARRAY_SIZE 20

using namespace std;

int heap[HEAP_SIZE];
int heap_count = 0;

void swap(int * a, int * b) {
	int tmp = *a; *a = *b; *b = tmp;
}

void init() {
	heap_count = 0;
}

int size() {
	return heap_count;
}

void push(int data) {

	// 힙의 가장 끝에 데이터 추가
	heap[++heap_count] = data;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 올리는 부분
	int child = heap_count;
	int parent = child / 2;
	while (child > 1 && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);
		child = parent;
		parent = child / 2;
	}

}

int pop() {

	// 힙의 가장 첫번째 원소를 반환
	// 힙의 가장 앞만 보고 있다!
	int result = heap[1];

	// 첫번째 원소를 힙의 가장 끝에 원소와 바꾸고
	// 가장 끝은 이제 쓰지 않을 예정이니 heap_count를 내려준다.
	swap(&heap[1], &heap[heap_count]);
	heap_count--;

	// 아래의 과정은 child를 parent와 비교하면서 알맞은 위치로 하나씩 내리는 부분
	int parent = 1;
	int child = parent * 2;
	if (child + 1 <= heap_count) {
		child = (heap[child] > heap[child + 1]) ? child : child + 1;
	}

	while (child <= heap_count && heap[parent] < heap[child]) {
		swap(&heap[parent], &heap[child]);

		parent = child;
		child = child * 2;
		if (child + 1 <= heap_count) {
			child = (heap[child] > heap[child + 1]) ? child : child + 1;
		}
	}

	return result;
}

int main() {

	int arr[TEST_ARRAY_SIZE]; // heap에 이용할 자료들
	int ans_arr[TEST_ARRAY_SIZE]; // 검증에 사용할 자료들

	srand(time(NULL));

	int test_case;
	int correct = 0;

	for (test_case = 1; test_case <= TOTAL_TEST_CASE; ++test_case) {

		// 같은지 확인하는 변수
		bool is_equal = true;

		// 자료들 입력
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			arr[i] = rand() % 2000 + 1; // 1 ~ 2000 사이의 난수 생성
			ans_arr[i] = arr[i];
		}

		// heap 정렬
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			push(arr[i]);
		}
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			arr[i] = pop();
		}

		// 정답 생성
		// greater<int>()는 내림차순을 위해서 사용
		// sort(ans_arr, ans_arr+TEST_ARRAY_SIZE)만 사용하면 오름차순이 됨
		sort(ans_arr, ans_arr + TEST_ARRAY_SIZE, greater<int>());

		// 정답과 힙정렬 결과 비교
		for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
			if (ans_arr[i] != arr[i]) {
				is_equal = false;
				break;
			}
		}

		if (is_equal) correct++;

	}

	printf("Total: %d / %d\n", correct, TOTAL_TEST_CASE);

	return 0;
}


참고자료