20200917 공부

아이템 확률

퀵정렬

문자열

링크드리스트

 

 

아이템 확률

 

아이템 확률대로 아이템을 뽑아보자

 

아이템, 빈도수

A, 20000

B, 1

C, 20000

D, 30000

 

A + B + C + D = 70001

 

1부터 70001 사이의 숫자를 랜덤하게 생성

 

if 숫자가 20000 보다 작으면 A아이템

else if 숫자가 20001 보다 작으면 B아이템

else if 숫자가 40001 보다 작으면 C아이템

else if 숫자가 70001 보다 작으면 D아이템

 

100만번 뽑아서 각각의 아이템이 나온 개수 출력

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

int items[] =
{
	20000,
	1,
	20000,
	30000
};

int main()
{
	srand(time(0));

	int itemRange[4];
	int itemMax = 0;
	int itemGetCount[4] = { 0, };

	for (int i = 0; i < 4; i++)
	{
		itemMax += items[i];
		itemRange[i] = itemMax;
	}

	for(int i = 0; i < 1000000; i++)
	{
		int randNum = rand() << 15 | rand();
		randNum %= itemMax;
		randNum += 1;

		for (int i = 0; i < 4; i++)
		{
			if (randNum <= itemRange[i])
			{
				++itemGetCount[i];
				break;
			}
		}
	}

	for (int i = 0; i < 4; i++)
	{
		printf_s("%c item : %d\n", 'A' + i, itemGetCount[i]);
	}

	return 0;
}

 

 

퀵정렬

void QuickSort(int* arr, int start, int end)
{
	int pivot = arr[(start + end) / 2];
	int left = start;
	int right = end;

	while (left <= right)
	{
		while (arr[left] < pivot)
			++left;
		
		while (arr[right] > pivot)
			--right;

		if (left <= right)
		{
			int tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
			++left;
			--right;
		}
	}

	if (left < end)
		QuickSort(arr, left, end);

	if (right > start)
		QuickSort(arr, start, right);
}

 

 

문자열

 

strlen

int strlen(const char* str)
{
	int len = 0;
	while (*str != '\0')
	{
		++len;
		++str;
	}
	return len;
}

 

strcpy

void strcpy(char* dest, int destSize, const char* src)
{
	for (int i = 0; i < destSize; i++)
	{
		*dest = *src;
		if (*src == '\0')
			return;
		++dest;
		++src;
	}
	*(dest - 1) = '\0';
}

 

strcmp

int strcmp(char* str1, char* str2)
{
	while (1)
	{
		if (*str1 < *str2)
			return -1;

		if (*str1 > *str2)
			return 1;

		if (*str1 == '\0')
			return 0;

		++str1;
		++str2;
	}
}

 

strcat

void strcat(char* dest, int destSize, const char* src)
{
	int idx = 0;
	while (*dest != '\0')
	{
		++idx;
		++dest;
	}

	for (int i = idx; i < destSize; i++)
	{
		*dest = *src;
		if (*src == '\0')
			return;

		++dest;
		++src;
	}
	*(dest - 1) = '\0';
}

이렇게 바꿀 수 있겠군

void strcat(char* dest, int destSize, const char* src)
{
	int len = strlen(dest);
	strcpy(dest + len, destSize - len, src);
}

 

strchr

문자열에서 문자 검색

char* strchr(char* str, const char ch)
{
	while (*str != '\0')
	{
		if (*str == ch)
			return str;

		++str;
	}

	return NULL;
}

 

strstr

문자열에서 문자열 검색

char* strstr(const char* str, const char* search)
{
	char* cur = (char*)str;
	int strLen = 0;
	while (*cur != '\0')
	{
		++strLen;
		++cur;
	}

	cur = (char*)search;
	int searchLen = 0;
	while (*cur != '\0')
	{
		++searchLen;
		++cur;
	}

	for (int i = 0; i < strLen - searchLen; i++)
	{
		int flag = 1;
		for (int j = 0; j < searchLen; j++)
		{
			if (str[i + j] != search[j])
			{
				flag = 0;
				break;
			}
		}

		if (flag)
		{
			return (char*)str + i;
		}
	}

	return NULL;
}

문자열 길이 구하는 부분은 strlen으로 대치 가능하겠군

 

strlwr

문자열 소문자 변환

void strlwr(char* str)
{
	//int sub = 'a' - 'A';

	while (*str != '\0')
	{
		if (*str >= 'A' && *str <= 'Z')
		{
			//*str += sub;
			*str += 32;
		}

		++str;
	}
}

 

 

링크드리스트

간단하게 구현 연습

#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

#ifdef _DEBUG
#define new new ( _NORMAL_BLOCK , __FILE__ , __LINE__ )
// Replace _NORMAL_BLOCK with _CLIENT_BLOCK if you want the
// allocations to be of _CLIENT_BLOCK type
#else
#define new new
#endif

#include <stdio.h>

struct Node
{
	int data;
	Node* nextNode;
};

Node* beginNode;
Node* endNode;

void PushBack(int data)
{
	Node* node = new Node;
	node->data = data;
	node->nextNode = nullptr;

	if (beginNode == nullptr)
	{
		beginNode = node;
		endNode = node;
	}
	else
	{
		endNode->nextNode = node;
		endNode = node;
	}
}

void PrintAll()
{
	Node* node = beginNode;
	while (node != nullptr)
	{
		printf_s("%d ", node->data);
		node = node->nextNode;
	}
	printf_s("\n");
}

void ClearList()
{
	Node* node = beginNode;
	while (node != nullptr)
	{
		Node* nextNode = node->nextNode;
		delete node;
		node = nextNode;
	}

	beginNode = nullptr;
	endNode = nullptr;
}

void Remove(int data)
{
	Node* node = beginNode;
	Node* prevNode = nullptr;

	while (node != nullptr)
	{
		if (node->data == data)
		{
			if (node == beginNode)
				beginNode = node->nextNode;
			
			if (node == endNode)
				endNode = prevNode;

			if (prevNode != nullptr)
				prevNode->nextNode = node->nextNode;

			delete node;
			break;
		}

		prevNode = node;
		node = node->nextNode;
	}
}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	PushBack(10);
	Remove(10);
	PrintAll();
	
	PushBack(20);
	PushBack(30);
	Remove(30);
	PrintAll();

	Remove(20);
	PrintAll();

	PushBack(40);
	PushBack(50);
	PushBack(60);
	PushBack(70);
	PushBack(80);
	PrintAll();

	Remove(40);
	Remove(80);
	Remove(60);
	PrintAll();

	ClearList();

	return 0;
}