okayoki

#문제

https://www.acmicpc.net/problem/9461

#작성 코드

#include <cstdio>

int T, N;
long long int memo[101];
long long int pn(int n){
	if( n==1 ) return 1;
	if( n==2 ) return 1;
	if( n==3 ) return 1;
	if( n==4 ) return 2;
	if( n==5 ) return 2;
	if( n==6 ) return 3;
	if( n==7 ) return 4;
	if( n==8 ) return 5;
	
	if( memo[n]!=0 ) return memo[n];
	return memo[n] = pn(n-1)+pn(n-5);
}
int main(){
	scanf("%d",&T);
	for(int i=0; i<T; i++){
		scanf("%d", &N);
		printf("%lld\n", pn(N));
	}
} 

##

P(1) ~ P(6)까지는 주어진 수열을 그대로 사용하고,

 P(7)부터 P(N) = P(N-1)+P(N-5) 라는 규칙이 생긴다.

#문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

#작성 코드

#include <cstdio>
int N;
int memo[1000001];
int binary(int n){
	if( n==1 ) return 1;
	if( n==2 ) return 2;
	
	if( memo[n]!=0 ) return memo[n];
	// 15746으로 나눈 나머지를 출력하는 것이 목표이므로
	// 처음부터 15746으로 나눈 나머지를 저장해준다. 
	return memo[n] = (binary(n-1)+binary(n-2))%15746;
}

int main(){
	scanf("%d", &N);
	printf("%d", binary(N));
	return 0;
}

##

n=1 -> 1

n=2 -> 11, 00

n=3 -> 111, 001 100

n=4 -> 1100, 0000 / 1111, 0011, 1001

             n=2결과에 00 붙인것 / n=3결과에 1 붙인것

n=5 -> 11100, 00100, 10000 / 11001, 0001, 11111, 00111, 10011

              n=3결과에 00 붙인것 / n=4결과에 1 붙인것

위와 같은 규칙성을 찾을 수 있다.

=> tile(n) = tile(n-1)+tile(n-2)라고 점화식을 세울 수 있다.

#문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

#작성 코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

int N;
int S[20][20];
bool visit[20]={false,};
int minS=987654321;

void makeTeam(int n, int cnt){
	if( cnt == N/2 ){
		vector<int> start, link;
		 
		for(int i=0; i<N; i++){
			if( visit[i]==true )
				start.push_back(i);		// visit한 선수들은 start팀 
			else
				link.push_back(i);		// 다른 선수들은link팀. 
		}
		
		// 두 팀의 능력치 차이 구하기. 
		int teamStart=0, teamLink=0;
		for(int i=0; i<start.size(); i++){
			for(int j=i+1; j<start.size(); j++){
				int startX = start[i], startY = start[j];
				int linkX = link[i], linkY = link[j];
				teamStart+=S[startX][startY]+S[startY][startX];
				teamLink+=S[linkX][linkY]+S[linkY][linkX];
			}
		}
		minS = min(minS, abs(teamStart-teamLink));
		return;
	}
	
	// n번째 선수부터 탐색한다. 
	for(int i=n; i<N; i++){
		if(visit[i]==true) continue;
		visit[i] = true;
		makeTeam(i+1, cnt+1);
		// 선수 한명을 뽑고 그 선수를 뽑은 상황에서 재귀적을 다음 선수 찾기 
		// makeTeam(i+1, cnt+1)으로 호출할 경우 for문 내부의 if문 실행을 하나 줄일 수 있다. 
		visit[i] = false;
	}
}

int main(){
	scanf("%d", &N);
	
	// 입력 
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &S[i][j]);
		}
	}
	// 능력치합의 차 최소값 구하기
	makeTeam(0,0);
	printf("%d", minS);
	
	return 0;
}

##

주어지는 선수의 수는 최대 20명이므로,

능력치를 저장할 배열 S[20][20];

이 선수를 뽑았는지 체크하는 배열 visit[20] = {false, };

각 팀의 능력치 합 teamStart=0, teamLink=0;

능력치 합의 차 최솟값을 저장할 minSum = 987654321; 으로 초기화.

Start팀에 갈 선수 N/2명만 뽑으면 Link팀 선수들은 자동으로 나머지 선수들이 된다.

시스템에 따라 스케줄러를 최적화 해야 하는 목표가 다르다.

1. 배치 시스템

    - 비선점형 알고리즘 또는 각 프로세스에게 긴 주기를 제공하는 선점형 알고리즘이 적절하다.

    -> 프로세스간 문맥교환을 줄여서 성능을 향상시킨다.

2. 대화식 시스템

    - 한 프로세스가 CPU를 독점하여 다른 사용자의 서비스를 방해하는 것을 막기 위해서 선점이 필수적이다.

3. 실시간 시스템

    - 때때로 선점이 필요하다. 프로세스들이 자신들이 실행을 오랫동안 할 수 없다는 점을 알고 있어서 보통 자신이 해야 할 일을 바로 수행하고 대기하기 때문.

# 스케줄링 알고리즘의 목표

모든 시스템

공평함 : 각 프로세스에게 공평한 몫의 CPU를 할당함.

정책 집행 : 정책이 집행되는지 관찰한다.

균형 : 시스템의 모든 부분이 활동하도록 해야 한다.

배치 시스템

성능 : 시간당 처리되는 작업의 수를 최대화 해야 한다. (처리율, throughput)

반환시간(turnaround time) : 작업의 제출부터 종료까지 걸리는 시간을 최소화해야 한다.

CPU 이용률 : CPU가 항상 활용되도록 해야 한다.

+) 처리량을 극대화하는 스케줄링 알고리즘이 반드시 반환 시간을 최소화 하지는 않는다.

대화식 시스템

응답시간 : 요청에 빠르게 응답해야 한다.

비례(proportionality) : 사용자의 기대를 만족시켜야한다.

실시간 시스템

마감시간 만족(deadline) : 마감시간 내에 처리를 끝내서 데이터 손실을 방지해야한다

예측 가능 : 멀티미디어 시스템에서 품질 저하를 방지.

#  배치 시스템의 스케줄링

선입선출 (FCFS: First Come First Served)

        : 요청 순서대로 cpu를 할당받음

최단 작업 우선 (SJF: Shortest Job First)

        : 실행 시간이 가장 짧은 작업을 선택

        작업의 실행 시간을 미리 알고 있어야 한다.

최단 잔여 시간 우선 (SRTN: Shortest Remaining Time Next)

        : 프로세스의 남은 실행 시간이 가장 짧은 작업 선택

        작업의 실행 시간을 미리 알고 있어야 한다.

        새로 도착한 짧은 작업이 좋은 서비스를 받을 수 있도록 해준다.

# 대화식 시스템의 스케줄링

라운드 로빈 스케줄링 (Round-Robin Scheduling)

        : 각 프로세스에게 '시간 할당량(time quantum)'이라 불리는 시간 주기가 할당됨. 한번에 이 시간 동안만 실행된다. 프로세스가 할당 시간 동안 실행하면 CPU는 다른 프로세스에게 주어진다. 프로세스가 할당 시간이 끝나기 전에 대기하거나 종료하면 CPU는 다른 프로세스로 전환한다.

        한 프로세스에서 다른 프로세스로 문맥교환이 자주 일어나면(시간 할당량이 짧음) 문맥교환에 걸리는 시간의 비율이 너무 커져서 CPU의 효율이 떨어짐.

        시간 할당량이 너무 크면 짧은 대화식 요청의 응답의 질이 떨어진다.

우선순위 스케줄링

        : 각 프로세스에게 우선순위가 할당되며 가장 높은 우선순위를 가진 실행 가능한 프로세스가 다음에 수행됨.

        높은 우선순위의 프로세스가 무한히 실행되는 것을 막기 위해 스케줄러는 클록 인터럽트마다 현재 실행중인 프로세스의 우선순위를 낮출 수 있다.(기아 문제 방지, starvation)

        각 프로세스는 최대로 실행할 수 있는 시간 할당량을 가진다.

        시스템의 특정 목표를 달성하기 위해 우선순위는 시스템에 의해 동적으로 할당될 수 있다.

        프로세스들을 그룹으로 묶어 우선순위 클래스를 형성하고, 우선순위 클래스마다 우선순위를 할당하며 각 클래스 내에서는 라운드 로빈을 사용하면 편리하다.

다단계 큐 (Multiple Queues)

        : 우선순위 클래스들을 설정. 우선순위가 높은 클래스일수록 프로세스마다 할당된 시간이 짧다. 프로세스가 할당된 시간을 모두 소비하면 한 단계 낮은 클래스로 이동한다.

최단 프로세스 순번 (SPN: Shortest Process Next)

        : 과거의 행동을 기반으로 추정하여 예상 실행 시간이 가장 짧은 프로세스를 실행한다.

        현재 측정된 값과 이전 예상치를 가중 평균하여 연속적으로 다음 값을 예상하는 '에이징(aging)'기법을 사용한다.

보장 스케줄링 (Guaranteed Scheduling)

        : 사용자에게 성능에 대한 현실적인 약속을 하고 이를 보장하는 방법. '단일 사용자 시스템에서 n개의 프로세스가 실행하면 동일하게 각 프로세스는 1/n만큼의 CPU시간을 받아야 한다.'

        어느 프로세스가 받아야 할 CPU시간에 대한 실제 받은 CPU시간 비율이 작은 프로세스를 가장 가까운 경쟁자의 비율을 초과할 때까지 수행시킨다.

복권 스케줄링 (lottery Scheduling)

        : 스케줄링 결정을 내릴 때마다 무작위로 복권 티켓을 선택하고 이 티켓을 가진 프로세스가 자원을 할당 받는다.

        더 중요한 프로세스는 여분의 티켓을 더 받아서 자원 할당 확률을 높일 수도 있고, 협동하는 프로세스들이 티켓을 교환할 수도 있다.

공평-몫 스케줄링 (Fair-Share Scheduling)

        : 스케줄링 하기 전에 프로세스의 소유자를 고려한다. 각 사용자는 CPU시간의 일정 비율을 할당받는다. 스케줄러는 이 비율이 지켜지도록 프로세스를 선택한다.

# 실시간 시스템에서 스케줄링

경성 실시간 (hard real-time) : 마감 시간이 절대적으로 만족되어야 한다.

연성 실시간 (soft real-time) : 때때로 마감시간을 지키지는 않아도 된다.

#작성 코드

#include <cstdio>

int T;	// 테스트 케이스의 개수 
int n;
long long int memo[41];
long long int fibo(int i){
	if( i==0 ){
		memo[i] = 0;
		return 0;	
	}
	if( i==1 ){
		memo[i] = 1;
		return 1;	
	} 
	
	if( memo[i]!=0 ) return memo[i];
	return memo[i]= fibo(i-1)+fibo(i-2);
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		if( n==0 )
			printf("1 0\n");		// fibo(0)에 대해서만 예외 출력 
		else
			printf("%d %d\n", fibo(n-1), fibo(n));
	} 
	return 0;
}

##

fibo(0) = 0

fibo(1) = 1

fibo(2) = fibo(1) + fibo(0) = 1

fibo(3) = fibo(2) + fibo(1) = 2*fibo(1) + fibo(0) = 2

fibo(4) = fibo(3) + fibo(2) = 3*fibo(1) + 2*fibo(0) = 3

...

fibo(n)을 호출했을 때 fibo(0)은 fibo(n-1)번 호출되고, fibo(1)은 fibo(n)번 호출됨을 알 수 있다.

#작성 코드

#include <cstdio>

int n;
long long int memo[91];
long long int fibo(int i){
	if( i==0 ) return 0;
	if( i==1 ) return 1;
	
	if( memo[i]!=0 ) return memo[i];
	return memo[i] = fibo(i-1)+fibo(i-2);
} 

int main(){
	scanf("%d", &n);
	printf("%lld", fibo(n));
		// 최대 90번째 피보나치수 출력할수있으므로 
		// 아주 큰 수 출력에 대비해야한다! 
	return 0;
}

##

최대 90번째 피보나치수를 출력해야하므로 출력값은 아주 큰 수가 된다. 따라서 계산한 값을 저장할 memo배열의 자료형과, 피보나치 수를 계산하는 함수의 리턴 자료형을 long long int로 해야했다.