기본 자료구조, 검색, 스택과 큐

기본 자료구조

배열 역순, 기수변환, 소수 출력

1. 배열 역순 - Swap 이용
2. 기수변환

String st = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
st.charAt(num % r); // num을 r로 나눈 나머지를 이용해 변환 

1. 1000이하의 소수 출력

일일이 다 확인 할 수 있지만 계산이 오래걸림. 소수의 제곱이 i보다 작은 경우에만 소수와 i가 나누어지는지 확인해도 전부 확인 가능하다. (5x20과 20x5는 같기 때문)

prime[ptr++] = 2;
prime[ptr++] = 3;
for(int i = 5; i <= 1000; i+=2) // 5보다 큰 짝수는 소수가 아니므로 제외.
{ 
	boolean flag = false;
	for(int j = 0; prime[j]*prime[j] < i; j++) // 
	{ 
		if(i % prime[i] == 0)
		{
			flag = true;
			break;
		}
	}
	if(flag == false)
	{
		prime[ptr++] = i;
	}
}

검색

1. 이진검색 정렬된 배열에 사용할 수 있다. ptrLeft, ptrRight, ptrCenter를 이용
   • ptrCenter < num -> ptrLeft = ptrCenter + 1
   • ptrCenter > num -> ptrRight = ptrCenter - 1

스택과 큐

1. Stack FILO 구조 push(), pop()

2. Queue FIFO 구조 front, rear, num(데이터의 개수), max(용량), arr 이용 front = rear 일 때 큐가 비어있거나 가득차있다. enqueue(), dequeue(), indexOf()

public void enqueue(int n){
	if(num >= max)
	{
		System.out.print("용량이 가득 참");
	}
	else{
		arr[rear++] = n;
		num++;
		if(rear == max)
		{ rear = 0; }
	}
}

public int dequeue(){
	if(num <= 0) System.out.print("큐가 비어있음");
	else{
		int x = arr[front++];
		num--;
		if(front == max)
		{
			rear = 0;
		}
	}
}

public int indexOf(int x)
{
	for(int i = 0; i < num; i++)
	{
		int idx = (i + front) % max;
		if(arr[idx] == x)
		{
			return idx;
		}
	}
	return -1;
}