okayoki

ba#문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

#작성 코드

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

int N;
int num[12];
int op[4];
// 결과의 최댓값과 최솟값은 절댓값 10억을 넘지 않는다. 
int ret_min = 1000000001, ret_max=-1000000001;

void answer(int result, int count){
	if( count==N-1 ){
		if(ret_min>result)
			ret_min = result;
		if(ret_max<result)
			ret_max = result;
		return;
	}
	
	// N개의 수로 이루어진 수열에 대해 연산 진행.
	// N-1개의 연산자 
	for(int i=0; i<4; i++){
		if( op[i]>0 ){
			op[i]--;
			
			if(i==0){
			answer(result+num[count+1], count+1);
			}
			if(i==1){
			answer(result-num[count+1], count+1);
			}
			if(i==2){
			answer(result*num[count+1], count+1);
			}
			if(i==3){
			answer(result/num[count+1], count+1);
			}
			
			op[i]++;
		}
	}
}

int main(){
	// 숫자의 개수, 수열 입력 
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", &num[i]);
	}
	// 연산자의 개수 입력. + - * / 순서 
	for(int i=0; i<4; i++){
		scanf("%d", &op[i]);
	}
	
	answer(num[0], 0);
	// 최댓값, 최솟값 출력 
	printf("%d\n%d", ret_max, ret_min);
	return 0;
} 

##

int **arr = new int*[19];
for(int i=0; i<19; i++){
	arr[i] = new int[19];
 	memset(arr[i], 0, sizeof(int)*19);
}

19*19 사이즈의 2차원 배열 동적 할당

memset함수는 arr[i]의 값을 sizeof(int)*19만큼 0으로 초기화시킨다.

for(int i=0; i<19; i++){
	delete[] arr[i];
}

delete[] arr;

19*19 사이즈의 2차원 배열 메모리 해제

cout<<showbase;

진수 표현에 따른 접두사 출력. 자릿수에 포함된다.

cout<<hex;

16진수로 출력한다.

cout<<uppercase;

16진수를 대문자로 출력한다.

cout<<width();

width에 주어진 숫자만큼 자릿수를 확보한다.

cout<<fixed;
cout<<setprecision();

setprecision에 주어진 숫자만큼 소수점 아래 ...번째까지만 표현한다.(반올림됨)

cout<<setfill('문자');

확보한 자릿수의 빈 공간을 '문자'로 채운다.

switch( 정수값 )
{
	case 'A':
    	cout<<"에이";
        break;				// break문을 사용하지 않으면 이후 명령들도 실행된다.
    case 'B':
    	cout<<"비";
        break;
    default:				// '정수값'이 지정된 케이스가 없다면 디폴트값 실행.
    	cout<<"기본값";
}

switch()에 주어지는 매개변수는 "정수"값만 가능하지만, 문자도 아스키코드 정수이기 때문에 사용가능하다.

모든 경우의 수를 검사하되, 특정 조건에 맞을 때만 검사하는 방식!

백트래킹 문제는 보통 DFS알고리즘에 조건을 검사하는 부분을 추가하여 해결한다.

대표적인 문제로 N-Queen이 있다.

N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

퀸은 가로, 세로, 대각선 방향으로 움직일 수 있는 체스의 말이다.

모든 경우의 수를 따진다면 (각 행마다 퀸을 놓을 수 있는 방법의 수) N x (행의 개수) N 으로 O(N^N)의 시간 복잡도를 가진다.

조건 검사 없이 모든 경우의 수를 따진다면 체스판의 크기가 조금만 커져도 해답을 찾는데 시간이 오래 걸릴테지만,

백트래킹으로 조건을 검사하면서 해당 조건이 만족될 때만 퀸을 놓고, 그 다음 퀸을 놓을 자리를 찾는다면 시간을 단축할 수 있다.

// 재귀적으로 함수를 호출하여 행 0~n-1까지 체크한다.
void findQueen(int n){
	if( n>=N ) count++;
	  
	for(int i=0; i<N; i++){		
        	// (n, i)에 퀸을 배치할수있는지 체크
		if( arr[i]==true ) continue;
		if( dup[n+i] == true || ddown[N-1+n-i]==true ) continue;
        	// (n,i)에 퀸을 놓고
		arr[i] = dup[n+i] = ddown[N-1+n-i] = true;
		findQueen(n+1);			// 다음 행에서 퀸을 놓을 자리를 재귀적으로 찾는다.
		// (n,i)에서 퀸을 제거하고 n번째 행에서 다른자리에 퀸을 또 놓을 수 있는지 체크할것임
        arr[i] = dup[n+i] = ddown[N-1+n-i] = false;
	}
}

백트래킹에서 중요한 것!

재귀를 타고 들어가기 전에 방문했던(작업했던) 것을 재귀에서 빠져나왔을 때 원래대로 돌리는 작업을 통해서 해당 작업(방문)을 이후에 다시 할 수 있도록 하는 것.

* 프로세스 간 문맥 교환

1. 사용자 모드에서 커널 모드로 전환

2. 재적재할 수 있도록 하기 위해 프로세스 테이블에 레지스터를 저장하는 것을 포함하여 현재 프로세스의 상태, 메모리 맵을 저장

3. 스케줄링 알고리즘을 실행하여 다음에 실행할 프로세스를 선택

4. 새로운 프로세스의 메모리 맵을 MMU로 다시 적재한다.

5. 새로운 프로세스가 수행을 시작한다.

* 프로세스의 행동

CPU-바운드 프로세스 : 대부분의 시간을 계산에 소비. 일반적으로 긴 cpu 버스트를 가지고 드물게 i/o를 기다림

I/O-바운드 프로세스 : 대부분의 시간을 I/o를 기다리면서 소비. 짧은 cpu 버스트를 가지고 빈번히 i/o를 기다림

CPU가 빨라질수록 프로세스는 점점 I/O-바운드가 되는 경향이 있다.

* 스케줄링이 필요한 시점?

1. 새로운 프로세스를 만들 때 자식 프로세스를 먼저 실행할지 부모 프로세스를 먼저 실행할지 결정해야 한다.

2. 프로세스를 종료할 때 다음으로 어느 프로세스를 실행할지 결정해야 한다.

3. 프로세스가 I/O, 세마포어, 다른 무언가 때문에 대기해야 할 때 다음에 실행할 프로세스를 선택해야 한다.

4. I/O인터럽트가 발행하는 경우 새로 준비된 프로세스를 실행할지, 인터럽트가 발생할 때 실행하던 프로세스를 실행할지, 제3의 프로세스를 실행할지 결정

* 비선점(nonpreemptive) 스케줄링 알고리즘

- 어떤 프로세스가 다음 수행 프로세스로 선정되면 이 프로세스는 I/O나 다른 프로세스를 기다리기 위해 대기하거나 자발적으로 CPU를 반환할 때까지 계속 수행할 수 있다. ( 응답 시간의 예측이 용이하다. )

-> 클록 인터럽트에서 스케줄링 결정이 이루어지지 않는다. 클록 인터럽트 처리가 끝난 후, 더 높은 우선순위의 프로세스가 기다리던 타임 아웃이 만족되어 깨어난 경우가 아니면 인터럽트 이전에 수행되던 프로세스가 다시 수행을 재개한다.

* 선점형(preemptive) 스케줄링 알고리즘

- 프로세스를 선택하고 최대 값으로 정해진 시간을 넘지 않는 범위에서 실행되도록 한다. 만약 정해진 시간 간격의 끝에 도달하면 이 프로세스는 중단되고, 스케줄러는 다음에 실행할 다른 프로세스를 선정한다.

- 선점형 스케줄링을 하기 위해서는 주기의 마지막에 클록 인터럽트가 발생하여 스케줄러가 다시 CPU의 제어를 회복할 수 있어야 한다.