Chater 5-3 큐를 이용한 시뮬레이션
카테고리: DataStructure2
태그: C Data Structure Algorithm
홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀
ppt 캡처는 모두 교수님 강의에서 캡처한 것임을 밝힙니다.
Chapter 5. 큐
🚀 큐를 이용한 시뮬레이션
점원이 1 명 뿐인 아이스크림 가게에서
- 큐의 원소를 “손님”이라고 생각하고
- 큐가 손님들이 줄서서 대기하고 있는 “줄”이라고 생각해보자.
📜 LinkedQueue.h
typedef struct customer
{
long arrival_time; // 이 손님이 언제 도착했는지
int processtime; // 이 손님이 주문하는 아이스크림을 만드는데 걸리는 시간 (즉 이 시간동안은 다른 손님 못받음)
} Item;
나머지 코드는 지난 포스팅과 같음. (연결리스트로 큐 구현하기)
📜 LinkedQueue.c
나머지 코드는 지난 포스팅과 같음. (연결리스트로 큐 구현하기)
📜 main.c
시뮬레이션이 끝나기 직전에 주문 받은 경우에도 아이스크림을 만들어드리는 것으로 가정한다. 즉, dequeue 가 된 손님은 customers served 에 포함된다.
#include <stdio.h>
#include <string.h>
// min_per_cust = 60.0f / average_n_customers_hour;
// x : probabilistic number of n_queued_cusnotmers_per an hour
// x의 파라미터로 min_per_cust 가 들어온다. (1을 입력하면 1시간 = 60분)
// 매 분마다 손님이 올지 안올지를 확률적으로 체크
bool newcustomer_visit(double x)
{
// 확률로 결정
// rand() : 0 이상 1 이하의 수가 랜덤으로 나옴
// RAND_MAX 는 32767 로 정의가 되어 있다.
if (rand() * x / RAND_MAX < 1.0)
return true;
else
return false;
}
Item get_customer(long arrival_time)
{
Item cust;
cust.processtime = rand() % 3 + 1; // 1,2,3 중 하나. 손님의 아이스크림 만드는 시간도 랜덤으로
cust.arrival_time = arrival_time;
return cust;
}
int main()
{
Queue waiting_queue; // 아이스크림 대기 줄 (원소는 손님!)
int simulation_length_in_hours; // 이 값이 1 이면 1시간, 2 이면 2시간이라는 뜻
int average_n_customers_per_hour; // 시간 당 몇 명의 손님이 오기를 기대하는지 입력할 것
double min_per_cust; // 60 / average_n_customers_per_hour 로, 몇 분마다 손님이 오기를 기대하는지
long cycle, cyclelimit;
/* Statistics */
long n_lost_customers = 0; // 큐가 꽉차서 줄 안서고(큐에 안들어가고) 가버린 손님 수
long n_queued_customers = 0; // 큐에 들어온적이 있는 손님 수
long n_served_customers = 0; // 아이스크림 받은 손님 수, 즉 dequeue 큐에서 삭제되어 나간 손님 수
long sum_line = 0; // 큐에 들어왔든 안들어왔든 손님 전~~체의 수
long wait_time = 0; // 아이스크림을 만들기 시작해서 다 만들때까지 남은 시간 수
long line_wait = 0; // 손님들이 줄서며 기다린 총 시간
InitializeQueue(&waiting_queue);
srand((unsigned int)time(0)); // rand() 에 시드 부여. 시드마저도 랜덤으로 하기 위해 time (현재시간)으로 시드를 정하는 것
// srand(0); //고정시드
/* 프로그램 시작 */
int flag;
printf("몇 시간동안 시뮬레이션 할 것인가요? \n >> ");
flag = scanf("%d", &simulation_length_in_hours);
printf("시간 당 몇 명의 손님이 올 것 같다고 생각하나요? \n >> ");
flag = scanf("%d", &average_n_customers_per_hour);
cyclelimit = simulation_length_in_hours * 60; // 시뮬레이션 시간을 (분)으로 변경
min_per_cust = 60.0f / average_n_customers_per_hour; // 몇 분에 손님이 올 것으로 예상하는지
/* cyclelimit 분 동안의 사이클 (1분 단위로) */
for (cycle = 1; cycle <= cyclelimit; ++cycle) {
if (newcustomer_visit(min_per_cust)) { // 확률적으로 손님이 왔을 것으로 기대되는 시간(분)이라면
if (QueueIsFull(&waiting_queue)) {
n_lost_customers++;
printf("%3ld 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.\n", cycle);
}
else {
n_queued_customers++;
Item customer_ready = get_customer(cycle);
EnQueue(customer_ready, &waiting_queue);
printf("%3ld 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.\n", cycle);
}
}
if (wait_time <= 0 && !QueueIsEmpty(&waiting_queue)) {
Item customer_ready;
DeQueue(&customer_ready, &waiting_queue);
printf("%3ld 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 %d 분 동안 만들기 시작합니다.\n", cycle, customer_ready.processtime);
wait_time = customer_ready.processtime;
line_wait += cycle - customer_ready.processtime;
n_served_customers++;
}
if (wait_time > 0)
wait_time--;
sum_line += QueueItemCount(&waiting_queue);
}
printf("\n");
/* 통계 내기 */
if (n_queued_customers > 0) { // 손님이 한 명이라도 왔다면
printf("총 몇 명의 손님을 받았는지 (큐에 줄 서본 손님의 수) : %ld\n", n_queued_customers);
printf("총 몇 명의 손님이 아이스크림을 받았는지 : %ld\n", n_served_customers);
printf("총 몇 명의 손님을 못 받았는지 (줄도 서보지 못하고 가신 손님 수) : %ld\n", n_lost_customers);
printf("평균적인 대기 손님 수 (매 분마다 평균적인 큐의 사이즈) : %.2f\n", (double)sum_line / cyclelimit);
printf("손님들이 줄 서기 시작한 이래로 아이스크림 받기까지 걸린 평균적인 대기 시간 : %.2f\n", (double)line_wait / n_served_customers);
}
else
puts("손님 아무도 안 왔습니다.");
EmptyTheQueue(&waiting_queue);
}
💎출력💎
몇 시간동안 시뮬레이션 할 것인가요?
>> 1
시간 당 몇 명의 손님이 올 것 같다고 생각하나요?
>> 70
1 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
1 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
2 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
2 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
3 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
4 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
5 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
5 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
6 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
6 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
7 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
8 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
9 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
9 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
10 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
10 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
11 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
11 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
12 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
13 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
13 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
14 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
14 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
15 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
15 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
16 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
17 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
17 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
18 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
19 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
20 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
20 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
21 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
21 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
22 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
22 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
23 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
24 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
25 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
25 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
26 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
27 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
28 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
28 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
29 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
30 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
31 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
31 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
32 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
33 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
33 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
34 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
34 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
35 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
35 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
36 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
37 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
37 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
38 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
39 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
39 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
40 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
40 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
41 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
42 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
42 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
43 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
44 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
45 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
45 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
46 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
47 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
48 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
48 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
49 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
50 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
51 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
51 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
52 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
53 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
54 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
54 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
55 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
55 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 3 분 동안 만들기 시작합니다.
56 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
57 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
58 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
58 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 2 분 동안 만들기 시작합니다.
59 분 : 새로 오신 손님이 뒤에 줄을 서셨습니다.
60 분 : 새로 오신 손님이 대기 줄이 꽉차 가버리셨습니다.
60 분 : 줄 다 서신 맨 앞 손님의 아이스크림을 1 분 동안 만들기 시작합니다.
총 몇 명의 손님을 받았는지 (큐에 줄 서본 손님의 수) : 40
총 몇 명의 손님이 아이스크림을 받았는지 : 31
총 몇 명의 손님을 못 받았는지 (줄도 서보지 못하고 가신 손님 수) : 20
평균적인 대기 손님 수 (매 분마다 평균적인 큐의 사이즈) : 7.65
손님들이 줄 서기 시작한 이래로 아이스크림 받기까지 걸린 평균적인 대기 시간 : 26.48
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기