큐(Queue)

큐(Queue)는 먼저 추가된 데이터가 먼저 출력 처리되는 선입선출(FIFO, First In First Out) 자료 구조로서 입력된 순서대로 처리해야 하는 상황에 이용된다. Queue는 맨 위에(tail)에 데이터를 계속 추가하고, 맨 앞(head)에서만 데이터를 읽는다.

• enQueue(인큐) : Queue의 rear(저장된 원소 중에서 마지막 원소)에서 이루어지는 삽입 연산
• deQueue(디큐) : Queue의 front(저장된 원소 중에서 첫 번째 원소)에서 이루어지는 삭제 연산

원소가 하나도 없는 공백 큐의 경우에는 front와 rear의 위치가 같은 상태가 된다. 

cf. 덱(Deque : Double-ended queue)

큐 두 개를 붙여서 만든 자료구조로 큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있는 확장된 큐로서, 스택의 특성과 큐의 특성을 모두 가지고 있는 자료구조이다. 이중 연결 리스트로 구현이 가능하다.

cf. 큐의 응용

• 프린터 버퍼 큐(Print Buffer Queue) : CPU는 출력으로 내보내는 데이터를 프린터 버퍼 큐에 삽입하고 프린터가 버퍼 큐에 있는 작업을 순서대로 처리하면서 처리가 끝난 작업은 버퍼 큐에서 삭제한다. 이와 같이 처리 속도가 다른 처리기 사이에서 처리 속도를 맞추기 위해 큐를 사용하는데, 이를 버퍼 큐라고 한다.
• 스케줄링 큐(Scheduling Queue) : 컴퓨터 운영체제에서 CPU를 사용할 프로세스들에 대해 CPU 사용 스케줄을 관리하기 위해 사용한다. 준비 큐와 대기 큐로 구성되어 있으며 CPU를 사용할 프로세스들을 준비 큐에 삽입하면 순서대로 준비 큐에서 꺼내서 CPU를 사용하게 한다. CPU를 사용하던 프로세스가 다른 처리를 기다리는 대기 상태가 되면 대기 큐에 삽입하여 대기 상태의 프로세스들을 순서대로 관리한다.
• 큐잉 이론(Queueing Theory) : 서비스를 받기 위해 기다리는 대기 행렬과 대기 시간을 실험하는데 큐가 사용된다. 모든 서비스가 끝나서 대기 행렬 큐가 공백이 될 때까지의 평균 대기 시간을 여러 상황에 대해 시뮬레이션해서 최적의 시스템을 설계한다.

Queue 클래스

.NET에는 큐를 구현한 Queue클래스와 이의 Generic 형태인 Queue<T> 클래스가 있다. 이 Queue클래스는 내부적으로 순환 배열 (Circular Array)로 구현되어 있는데, 배열의 마지막 요소에 다다른 경우 다시 배열 처음 요소로 순환하는 구조(next % arrsize)를 가지고 있다. Queue는 내부적으로 head와 tail 포인터를 가지고 있는데, tail에 데이터를 추가하고(Enqueue) head에서 데이터를 읽고 제거(Dequeue)한다. 만약 데이터 양이 많아 순환 배열이 모두 찰 경우, Queue는 Capacity를 2배로 (디폴트 Growth Factor가 2이다) 증가시키고, 모든 배열 요소를 새 순환 배열에 자동으로 복사하여 큐를 확장한다.

Queue<int> q = new Queue<int>();
q.Enqueue(120);
q.Enqueue(130);
q.Enqueue(150);

int next = q.Dequeue(); // 120
next = q.Dequeue(); // 130

문제 설명

using System;

public class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Array.Sort(times);
        
        long min_time = 1;
        long max_time = times[times.GetLength(0)-1]*(long)n;
        long median_time = (min_time+max_time)/2;
        long calcu_num;
        while(true)
        {
            calcu_num = 0;
            foreach(int num in times)
            {
                calcu_num = calcu_num + median_time/num;
            }
            
            if(min_time > max_time)
            {
                break;
            }
            
            if(calcu_num >= n)
            {
                answer = median_time;
                max_time = median_time-1;
                median_time = (min_time + max_time)/2;
            }
            else
            {
                min_time = median_time+1;
                median_time = (min_time + max_time)/2;
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43238#qna

이분 검색(Binary Search)

• 자료의 가운데에 있는 항목을 키 값과 비교하여 키 값이 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법
• 재귀 알고리즘
• 이미 자료가 정렬(반드시 정렬되어 있는 자료를 검색할 때만 사용)
• 한번 비교 후 비교할 대상이 1/2로 줄어듬(점점 접근해감)
• 시간 복잡도 : O(log₂n)
• 삽입이나 삭제가 발생했을 경우 항상 배열을 정렬된 상태로 유지하는 작업이 추가로 필요

문제

크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라.

입력

자연수 n, 비내림차순으로 정렬된 배열 S[1...n], 찾고자 하는 항목 x

출력

x가 S의 어디에 있는지의 위치. 만약 x가 S에 없다면 0

절차

1. x가 배열의 중간에 위치하고 있는 항목과 같으면 종료
2. 분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택
3. 정복 : 선택된 반쪽 배열에서 x를 찾는다. 부분배열이 바로 해답을 결정할 수 있을 만큼 작지 않으면, 재귀적인 방법으로 결정할 수 있도록 한다.
4. 통합 : 필요없음

x = 18이고, 다음과 같은 배열이 있다고 가정하자.
10  12  13  14  18  20  25  27  30  35  40  45  47
↑
가운데 아이템

1. 분할 : 배열을 분할한다. x <25이기 때문에, 다음 부분 배열을 검색한다.
10  12  13  14  18  20

2. 정복 : x가 그 부분 배열에 있는지 결정하여 그 부분 배열을 정복한다.
(이는 그 부분배열을 재귀적으로 분할하여 완수한다.)
예) x는 그 부분 배열에 있습니다.

3. 통합 : 그 부분 배열에서 얻은 해답으로 전체 배열에 대한 해답을 구한다.
예) x는 그 배열에 있습니다.

//이분검색 : 재귀알고리즘
//S,n,x는 global 변수로 선언하여 사용

index location(index low, index high){
	index mid;
	
	if(low>high)
		return 0; // 찾지 못했음
	else{
		mid=(low+high)/2 // 정수 나눗셈(나머지 버림)
		if(x==S[mid])
			return mid; // 찾았음
		else if(x<S[mid])
			return location(low,mid-1); // 왼쪽 반을 선택함
		else
			return location(mid+1,high); // 오른쪽 반을 선택함
	}
}
...
locationout=location(1,n);
...

스택(Stack)

스택은 마지막에 입력된 데이터가 먼저 출력되는 후입선출(LIFO, Last In First Out) 구조로서 가장 최신 입력된 데이터 순서대로 처리해야 할 상황에 이용된다. 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 되어 있다. 더욱 빠른 파서와 재귀 알고리즘 구현에 도움이 된다. 

• Push : 원소(element)를 넣어 사용한다는 의미로, 상단에 데이터를 추가한다는 의미이다.
• Pop : 스택의 Pop 메서드와 Peek 메서드를 확인한다. Pop을 호출하면 top에 위치한 요소가 리턴되며 삭제된다.

cf. Peek

Peek를 사용하면 Pop과 같은 결과가 나오지만 요소를 삭제하지는 않는다.

Stack 클래스

.NET에는 스택을 구현한 Non-generic인 Stack클래스와 이의 Generic 형태인 Stack<T> 클래스가 있다. Queue와 마찬가지로 .NET의 Stack클래스는 내부적으로 순환 배열(Circular Array)으로 구현되어 있으며, 스택이 가득 차면 자동으로 배열을 동적으로 확장하게 된다.

Stack<double> s = new Stack<double>();
s.Push(10.5);
s.Push(3.54);
s.Push(4.22);

double val = s.Pop(); // 4.22