deque.c

deque자료구조를 만들어보자. 나중에 쓰려구 ㅎㅎ

deque STRUCTURE만들기

void	deque_init(t_deque *deque)
{
	deque->cnt = 0;
	deque->top = 0;
	deque->bottom = 0;
}

void	append(t_deque *deque, int data)
{
	t_node	*node;

	node = (t_node *)malloc(sizeof(t_node));
	node->next = 0;
	node->prev = 0;
	node->data = data;
	if (is_empty(deque))
		deque->top = node;
	else
	{
		node->prev = deque->bottom;
		deque->bottom->next = node;
	}
	deque->bottom = node;
	deque->cnt++;
}

int	pop_left(t_deque *deque)
{
	t_node	*ptr;
	int		data;

	if (is_empty(deque))
		print_emsg("Error\n");
	ptr = deque->top;
	data = ptr->data;
	if (deque->cnt == 1)
	{
		deque->top = 0;
		deque->bottom = 0;
	}
	else
	{
		deque->top = ptr->next;
		deque->top->prev = 0;
	}
	deque->cnt--;
	free(ptr);
	return (data);
}

void	append_left(t_deque *deque, int data)
{
	t_node	*node;

	node = (t_node *)malloc(sizeof(t_node));
	node->next = 0;
	node->prev = 0;
	node->data = data;
	if (is_empty(deque))
		deque->bottom = node;
	else
	{
		node->next = deque->top;
		deque->top->prev = node;
	}
	deque->top = node;
	deque->cnt++;
}

int	pop(t_deque *deque)
{
	t_node	*ptr;
	int		data;

	if (is_empty(deque))
		print_emsg("Error\n");
	ptr = deque->bottom;
	data = ptr->data;
	if (deque->cnt == 1)
	{
		deque->top = 0;
		deque->bottom = 0;
	}
	else
	{
		deque->bottom = ptr->prev;
		deque->bottom->next = 0;
	}
	deque->cnt--;
	free(ptr);
	return (data);
}

첨에 그냥 만들다가 나중에 명령어 에러뜨길래 왜 뜨지 싶어서 찾아보니 pop, pop_left에서 데이터 갯수가 1일 때 처리를 덜 해줘서 segmentation에러가 발생함

greedy.c 의 주석

// greedy알고리즘이 시작되는 부분.
// 스택 b의 모든 원소에 대해 스택a로 보낼 때 가장 명령어를 적게 사용하는 스택b를 찾는다.
// ex)
// stack a : 3 1 2
// stack b : 7 14

// case 1)7을 넣는 경우
// stack a : 1 2 3
// stack b : 7 14
// ->ra
// stack a : 7 1 2 3
// stack b : 14
// ->pa

// case 2) 14를 넣는 경우
// stack a : 1 2 3
// stack b : 14 7
// ->ra rb
// stack a : 14 1 2 3
// stack b : 7
// ->pa

// 따라서 7을 넣는 것이 가장 적은 명령어를 사용하게 된다. (물론 rr을 하면은 한 번이지만 명령어 수를 가장 적게 사용하는 b를 고르는 것이 greedy의 핵심)
// 그래서 find_min()는 현재 stack b의 데이터를 넣게되면
// stack a에서 명령어를 몇 번 할 것인지(a_location = get_loc_a())와 stack b에서 명령어를 몇 번 할 것인지(=b_location)의
// 갯수를 찾아주고 가장 작게 명령어를 움직이는 경우를 찾아서(cmp_location()) da와 db에 담아준다.

get_loc_a.c 의 주석.

// stack a의 데이터 범위가 [data - x, data + x]라고 하자.
// 만약 현재 stack b의 데이터가 stack a의 범위 밖의 수라면 stack a를 어떻게 정렬한 후 pa를 해야할까.

// case 1) b.data < data - x
// stack a의 min값이 top으로 오게한 후 append

// case 2) b.data > data + x
// stack a의 max값이 top으로 오게한 후 ra하고 append하면 됨.

// case 3) b.data 가 stack a의 사잇값인 경우
// b.data - x < b.data < b.data + x 위치를 찾고 pa

// get_location()의 flag 변수는 현재 찾는 데이터가 min인지 max인지를 판단하는 변수이다.
// max라면 ra를 한번 더 따로 해줘야하니까.. idx를 1로 초기화를 시켜준다.