okayoki

#문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

#작성 코드

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

int n;
int wine[10001];			// 각 포도주잔에 들어있는 포도주의 양 저장 
int wineSum[10001]={0,};	// i번째 포도주잔까지 마실때 최대로 마실수있는 포도주의 양 

void input(){
    cin>>n;
    for(int i=1; i<=n; i++){
	cin>>wine[i];
    }
}

int choose(){
    wineSum[0]=0;
    wineSum[1] = wine[1];
    wineSum[2] = wine[1]+wine[2];
    for(int i=3; i<=n; i++){
        // oox 경우와 oxo경우, xoo경우 중 최대 
        wineSum[i] = max( wineSum[i-1], wineSum[i-2]+wine[i] ); 
        wineSum[i] = max( wineSum[i], wineSum[i-3]+wine[i-1]+wine[i]);
    }
    return wineSum[n];
}

int main(){
    input();
    cout<<choose();
    return 0;
}

##

wineSum[i]는 i번째 포도주 잔까지 마실 때 최대로 마실 수 있는 포도주의 양을 저장한다.

2579번, 계단 오르기 문제와 다른 점은 "무조건 마지막 포도주를 마셔야 하는 것이 아니다"라는 것이다.

#191217 review

복습 중에 기존의 1차원 dp풀이말고, 2차원 dp로 푸는 아이디어가 생각나서 다시 풀어보았다.

#문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

#작성 코드

BFS를 사용한 풀이

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm> 
#include <utility> 
using namespace std;

int N;					// 지도의 크기 
int area[27][27]={0,};			// 지도(인덱스 1~25 사용) 
int danji=0;				// 단지수 
queue<pair<int,int> > q; 		// 각 단지수를 인덱스로 사용. 단지별 집의 수
int numDanji[25*25/2+1]={0,};

// 입력받는 함수 
void input(){
    cin>>N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            scanf("%1d", &area[i][j]);
        }
    }
} 

// 해당 위치가 지도 내부에 존재하는지 true, false 리턴 
bool inArea(int x, int y){
    return (x>=1&&x<=N&&y>=1&&y<=N);
}

// [x][y]집의 상하좌우를 체크하는데 사용하는 함수. 
void check(int x, int y){
    // x,y가 지도 내에 존재하고, [x][y]가 집이면 해당 단지의 큐에 넣고, danji+1 값 바꿔준다. 
    if( inArea(x, y) && area[x][y]==1 ){
        q.push(make_pair(x,y));
        area[x][y] = danji+1;
        numDanji[danji]++;
    }
}

void oneDanji(int i, int j){
    danji++;                    // 한 단지의 집 하나 발견! 
    area[i][j] = danji+1;       // n단지의 집에는 n+1을 저장해준다.
    q.push(make_pair(i, j));
    numDanji[danji]++;
	
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
		
        // 해당 집의 상하좌우 체크. 
        check(x-1, y);
        check(x, y-1);
        check(x, y+1);
        check(x+1, y);
    } 
}
// 문제를 해결하는 함수 
void findDanji(){
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            // 집이 있는 장소 찾으면 그 장소를 저장, 그 집이 포함된 단지 탐색 
            if( area[i][j]==1 )
                oneDanji(i,j);
        }
    }
	
    // 단지의 개수만큼 numDanji배열 오름차순 정렬. 
    sort(numDanji+1, numDanji+danji+1);
    // 단지의 개수 출력 
    cout<<danji<<'\n';
    // 각 단지별 집의 수 오름차순으로 출력. 
    for(int i=1; i<=danji; i++){
        cout<<numDanji[i]<<'\n';
    }
} 

int main(){
    input();
    findDanji();
    return 0;
}

DFS를 사용한 풀이.

##

상, 하, 좌, 우로 연결된 집을 하나의 단지로 본다.(대각선은 아님!)

지도의 크기는 N*N이고, N은 5이상 25이하.

1부터 N까지의 인덱스를 지도의 범위로 사용하기 위해 area[26][26]을 선언했다.

danji 변수는 0으로 초기화하고, 새로운 단지를 발견할 때마다 1씩 증가시킨다.

numDanji[danji]는 각 단지의 집 수를 카운팅한다.

25*25사이즈 지도의 경우 최대로 가능한 단지의 개수는 25*25/2+1개이므로 numDanji[25*25/2+1]={0,};으로 선언한다.

1. findDanji()함수에서 이중 for문을 순회하면서 (i, j)위치에서 처음으로 집을 발견

2. 해당 집이 속하는 단지를 탐색하기 위해 oneDanji(i, j)함수를 실행한다.

3. danji 변수를 1 증가시키고, bfs를 사용해서 해당 집의 상하좌우를 체크한다.

    발견한 집의 위치에 집을 의미하는 1 대신 danji+1을 저장하고(다음 단지 탐색시 무시하기위해서)

    , 발견한 집의 수는 numDanji[danji]에 누적시킨다.

4. 1~3을 반복해서 모든 지도 범위를 탐색한다.

5. 단지의 개수, 각 단지의 집 수를 오름차순으로 출력한다.

#문제

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

#작성 코드

#include <iostream>
using namespace std;

int mod = 1000000000;
int N;
int memo[101][10]={ 0,};

int stair(int n){
	// 1자리수 계단수는 각각 1개이다. 
	for(int i=1; i<10; i++)
		memo[1][i] = 1;
	
	// i자리수, j로 끝나는 계단수
	// n자리수까지 계산한다.	
	for(int i=2; i<=n; i++){
		for(int j=0; j<10; j++){
			// 이후에 0이 될 수 있는 경우는 이전에 1이었던 경우 뿐 
			if( j==0 ){
				memo[i][0] = memo[i-1][1]%mod;
			}
			// 이후에 9가 될 수 있는 경우는 이전에 8이었던 경우 뿐 
			else if( j==9 ){
				memo[i][j] = memo[i-1][8]%mod;
			}
			// 나머지 경우는 j의 이전, 이후 수 모두에 대해 가능하다. 
			else{
				memo[i][j] = (memo[i-1][j-1]+memo[i-1][j+1])%mod;
			}
		}
	}
	
	// n자리수의 계단수. 끝 숫자가 0~9인경우 모두의 합을 구한다. 
	int sum=0;
	for(int i=0; i<10; i++){
		sum = (sum+memo[n][i])%mod;
	}
	return sum;
}
int main(){
	cin>>N;
	cout<<stair(N);
	return 0;
} 

##

읽는자 쓰는자 문제

The Readers and Writers Problem

데이터베이스 접근을 모델링한다

다수의 프로세스가 데이터베이스에서 동시에 읽는것은 허용되지만, 한 프로세스가 데이터베이스를 갱신하고 있다면 다른 프로세스는 읽는 경우라도 데이터베이스에 접근할 수 없다.

이 문제를 해결하기 위해, 최초의 독자는 데이터베이스를 접근하기 위해 세마포어 db를 down한다.

뒤따라 오는 독자들은 카운트 rc를 증가시킨다. 독자가 일을 마치면 rc를 감소시키고 마지막 독자를 세마포어 db에 대해 up을 수행하여 대기중인 작가가 있으면 작가가 다음 코드로 진입할 수 있게 한다.

typedef int semaphore;
semaphore mutex = 1;		// rc에 대한 접근제어
semaphore db = 1;		// db에 대한 접근제어
int rc = 0;

void reader(void){
    while(TRUE){
    	down(&mutex);		// rc에 대한 접근제어 획득
        rc = rc+1;
        if( rc==1 ) down(&db);	// 첫번째 reader라면 db down
        up(&mutex);		// rc에 대한 접근제어 박탈
        
        read_data_base();
        
        down(&mutex);		// rc에 대한 접근제어 획득
        rc = rc-1;
        if( rc==0 ) up(&db);	// 마지막 reader가 읽고나면 db up
        up(&mutex);		// rc에 대한 접근제어 박탈
        
        use_data_read();
    }
}

void writer(void){
    while(TRUE){
    	think_up_data();
        
        down(&db);		// db에 대한 접근제어 획득
        write_data_base();	// db에 데이터 기록
        up(&db);		// db에 대한 접근제어 박탈
    }
}

이 방법에도 문제가 존재한다.

적어도 하나의 독자가 이미 존재하는 한 새로운 독자는 '언제나' 진입이 허용된다.

-> 작가는 독자가 존재하지 않을 때까지 대기하게 된다. 독자의 작업이 끝나기 전에 새로운 독자가 계속해서 도착한다면 작가는 데이터베이스에 절대 접근할 수 없게 된다.

=> 작가가 기다리는 도중 독자가 도착하면 독자는 바로 진입이 허용되는 것이 아니라, 작가 뒤에 수행되도록 대기하도록 해야 한다. -> 작가는 이미 존재하는 독자들은 대기해야 하지만, 작가 이후에 도착한 독자들은 대기하지 않아도 된다.

이 방법의 단점은 병행성이 떨어져 성능이 나빠질 수 있다는 것이다.

-> Courtois et al. 은 작가에게 우선권을 주는 해결책을 제시했다.

# 식사하는 철학자 문제

Dijkstra가 제시. dining philosopher problem.

https://ko.wikipedia.org/wiki/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94_%EC%B2%A0%ED%95%99%EC%9E%90%EB%93%A4_%EB%AC%B8%EC%A0%9C

#define N 5

void philosopher(int i){
	while(TRUE){
    	think();
        take_fork(i);
        take_fork((i+1)%N);
        eat();
        put_fork(i);
        put_fork((i+1)%N);
    }
}

take_fork는 지정된 포크를 사용할 수 있을 때까지 기다린다.

다섯 명의 철학자가 모두 동시에 왼쪽 포크를 집는 상황에서 아무도 오른쪽 포크를 잡을 수 없는 문제가 발생한다.

왼쪽 포크를 집고, 오른쪽 포크를 사용할 수 있는지 검사하고, 사용할 수 없으면 왼쪽 포크를 내려놓도록 코드를 수정하더라도 문제는 발생한다. 모든 철학자가 동시에 왼쪽 포크를 집고, 오른쪽 포크를 사용할 수 없음을 알고 다시 왼쪽 포크를 내려놓음을 반복하게 될 수 있다.

이런 식으로, 모든 프로그램이 무기한 계속 실행하지만 아무런 진전도 없는 경우를 기아(starvation)이라 한다.

교착상태가 기아가 없도록 하려면 think 호출 이후, 포크를 집고, 포크를 놓는 상황을 이진 세마포어로 보호해야한다.

포크를 집기 전에 철학자는 mutex를 down한다. 포크를 집은 후 철학자는 mutex를 up한다.

이 해답에는 실용적인 문제가 발생한다. 이 상황에서 한 번에 한 철학자만 식사할 수 있다. (두 명의 철학자가 식사 가능함에도 불구하고.)

state라는 배열을 사용해서 철학자가 식사 중인지, 생각하고 있는지, 포크를 집으려고 시도하는지 추적한다.

철학자는 오직 이웃이 식사중이 아닌 경우에만 식사중인 상태가 될 수 있다.(양 옆 포크를 모두 사용해야하므로)

프로그램이 철학자 한 명 당 세마포어 배열을 사용하므로 이제 필요한 포크가 사용 중이면 배고픈 철학자는 대기하게 된다.

#define N			5
#define LEFT			(i-N-1)%N		// 현재 철학자의 왼쪽 이웃
#define RIGHT			(i+1)%N			// 현재 철학자의 오른쪽 이웃

#define THINKING		0
#define HUNGRY			1
#define EATING			2

typedef int semaphore;
int state[N];						// 각 철학자의 상태 저장
semaphore mutex = 1;
semaphore s[N];						// 철학자 당 하나씩 가지는 세마포어

void philosopher(int i){
    while(TRUE){
        think();
        take_forks(i);		// 두 개의 포크를 동시에 잡을 수 없으면 대기
        eat();
        put_forks(i);		// 두 개의 포크를 동시에 놓는다.
    }
}

void take_forks(int i){
    down(&mutex);
    state[i] = HUNGRY;
    test(i);					// 두 개의 포크를 집으려고 시도한다.
    up(&mutex);
    down(&s[i]);
}

void put_forks(int i){
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);				// 왼쪽, 오른쪽 이웃이 포크를 집을 수 있는 상황인지 체크
    test(RIGHT);
    up(&mutex);
}

void test(int i){
	if( state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING ){
    	// 주어진 철학자가 배가 고프고, 좌우 이웃이 식사중이 아니어야 포크를 둘 다 집을 수 있다.
    	state[i] = EATING;
        up(&s[i]);
    }
}

I/O장치와 같은 제한된 개수의 자원을 배타적으로 접근하기 위해 경쟁하는 프로세스들을 모델링하는데 유용하다.

여러 개의 프로세스들이 다수의 스레드를 가지고 있을 때 프로세스와 스레드라는 두 개의 병렬성이 존재.

이러한 시스템에서 스케줄링은 사용자 레벨 스레드 또는 커널 레벨 스레드가 지원되는지에 따라 다르다.

1. 사용자 레벨 스레드

커널은 스레드의 존재를 인식하지 못하므로 커널은 항상 하던대로 프로세스 A를 선택.

할당 시간만큼 A에게 CPU의 제어를 넘긴다.

A내부의 스레드 스케줄러는 어느 스레드를 실행시킬지 결정한다.

스레드를 다중 프로그래밍 하기 위한 클록 인터럽트가 존재하지 않으므로 이 스레드는 자신이 원하는 만큼 실행할 수 있다.

이 스레드가 프로세스에게 할당된 할당 시간을 모두 소비하면 커널은 다른 프로세스를 선택하여 실행한다.

사용자 레벨 스레드 스케줄링의 유일한 제약 : 너무 오래 실행되는 스레드를 중단시킬 수 있는 클록 인터럽트가 없다는 것.

2. 커널 레벨 스레드

커널은 어떤 스레드를 선택하여 실행한다. 커널은 스레드가 어느 프로세스에 속하는지 고려하지 않지만, 커널이 원한다면 고려할 수 있다. 스레드는 할당 시간을 부여받고 이 시간을 초과하면 강제로 중단된다.

사용자 레벨 스레드와 커널 레벨 스레드 사이의 차이 : 성능

사용자 레벨 스레드에서 스레드 문맥 교환 : 몇 개의 기계어로 수행. 빠르다.

커널 레벨 스레드에서 스레드 문맥 교환 : 메모리 맵을 바꾸고 캐시를 무효화하는 몇 배나 오래 걸리는 완전한 문맥교환

=> 동등하게 중요한 두 개의 스레드가 있고, 하나는 방금 대기하게 된 스레드와 동일한 프로세스에 속하고, 다른 하나는 다른 프로세스에 속한다면 동일한 프로세스에 존재하는 스레드로 문맥교환하는 것을 선호한다.

커널 레벨 스레드에서 한 스레드가 I/O에 대해 대기하는 경우, 이것이 해당 프로세스 전체를 중단시키지는 않는다.

사용자 레벨 스레드에서는 해당 프로세스가 중단됨.

사용자 레벨 스레드는 응용에 특화된 스레드 스케줄러를 사용할 수 있다. -> 작업 스레드가 종종 디스크 I/O를 위해 대기하는 환경에서 병렬성을 극대화시킨다.( 런타임 시스템이 모든 스레드가 무슨 일을 하는지 알 때 )

커널 레벨 스레드에서 커널은 스레드가 무슨 일을 하는지 절대 알 수 없다.