ITwork

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력 1 
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1 
5

예제 입력 2 
7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

예제 출력 2 
6

예제 입력 3
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

예제 출력 3 
1

예제 입력 4
5
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3

예제 출력 4
1

문제 풀이

/*baekjoon 2468 안전 영역*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int) 1e2) 

int N,cnt=0,maxval=0,minval=MAXN;
int Map[MAXN+10][MAXN+10];
int reMap[MAXN+10][MAXN+10];
int visited[MAXN+10][MAXN+10];

int dy[]={-1, 1, 0, 0};
int dx[]={0, 0, 1, -1};
int nx,ny;
bool inRange(int y, int x){
    return( (y>=1) && (y<=N) && (x >=1) && (x<=N));}

void DFS(int y, int x,int n){
    visited[y][x] = 1;

    for(int i=0; i<4; i++){
        ny=y+dy[i];
        nx=x+dx[i];
        if(Map[ny][nx] > n && visited[ny][nx] == 0){
            DFS(ny, nx, n);
        }
    }
}
void BFS(int y, int x){
    int ny, nx; 
    queue <pair<int, int>> q;
    q.push(pair<int,int>(y,x));

    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;

        q.pop();
        for(int i=0; i<4; i++){
            ny = y + dy[i];
            nx = x + dx[i];
            if(inRange(ny, nx) && reMap[ny][nx]){
                q.push(pair<int,int>(ny,nx));
                reMap[ny][nx] =0; 
            }
        }
    }   
}
void remap(int num){
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
        if(Map[i][j] <= num){
            reMap[i][j] = 0;
        }else{
            reMap[i][j] = 1;
        }
        }
    }
}
void Solve(){
    int maxcnt=0;
    for(int k=0; k<100; k++){
    memset(visited, false, sizeof(visited));
    cnt=0;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            if(Map[i][j] > k && visited[i][j]==0 ){
                cnt++;
                DFS(i,j,k);
                //BFS(i,j);
            }
        }
    }
        if( cnt > maxcnt) maxcnt = cnt;
    }
    cout << maxcnt << endl;
}
void InputData(){
    cin >> N;
    for( int i=1; i<=N; i++){
        for( int j=1; j<=N; j++){
            cin >> Map[i][j];
            if(minval > Map[i][j] ) minval= Map[i][j];
            if(maxval < Map[i][j] ) maxval= Map[i][j];
        }
    }
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*baekjoon 2468 안전 영역*/

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1 
0
1
1
3
1
9

/*baekjoon 4963 섬의개수*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN 50
int w,h,cnt;
int Map[MAXN+10][MAXN+10];
int dy[] = {-1,1,0,0,-1,-1,1,1};
int dx[] = {0,0,-1,1,-1,1,-1,1};

void DFS(int y, int x){
    if(Map[y][x] != 1) return;
        Map[y][x] = 0;
    for(int i=0; i<8; i++){
        DFS(y+dy[i], x+dx[i]);
    }

}
void Solve(){
    cnt=0;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            if( Map[i][j]==1){
                DFS(i,j);
                cnt++;
            }
        }
     }
    cout << cnt << endl;
}
void InputData(){
    while(1){
        cin >> w >> h;
        if(w==0 && h==0) break;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                cin >> Map[i][j];
            }
         }
     Solve();
    }
}
int main(){
    InputData();

    return 0;
}
/*baekjoon 4963 섬의개수*/

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

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다.

출력

첫째 줄에 N!을 출력한다.

예제 입력 1 
10

예제 출력 1 
3628800

예제 입력 2 
0

예제 출력 2 
1

풀이 

N!은 N=3일 경우 3*2*1로 표시된다. 

예를 들어서 N=3일 경우 어떻게 진행되는지 확인 해 보자.

factorial 함수에 n=3이 전달 되면 아래와 같이 값들이 입력이 될 것이다. 

3*factorial(3-1)

n-1이므로 n=2가 전달되어서 아래와 같이 되고 

3*2*factorial(2-1)

마지막으로 n=1이 전달되면 더이상 factorial함수가 재귀로 호출되지 않고 return 1이 호출되어서 아래 값이 계산되어서 return됨.

3*2*1

최종 출력값은 6이다. 

[소스 코드]

/*baekjoon 10872 팩토리얼*/
#include <bits/stdc++.h>
using namespace std;
int N;
int factorial(int n)
{
    if(n > 1)
        return n*factorial(n-1);
    else
        return 1;
}
void InputData(){
    cin >> N;
}
int main()
{
    InputData();
    cout <<  factorial(N) ;
    return 0;
}
/*baekjoon 10872 팩토리얼*/

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이

-오름차순 정렬

-이진 탐색

-Lowerbound

-Upperbound 

/*10816 숫자카드2*/
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)5e5+10) 
int N; 
int A[MAXN]; 
int M; 
int B[MAXN]; 
int Temp[MAXN];

void InputData() { 
    cin >> N;
    for(int i=0; i<N; i++) { 
        cin >> A[i]; 
    } 
    cin >> M;
    for(int i=0; i<M; i++) { 
        cin >> B[i]; 
    } 
} 
int BinarySearchLower(int s, int e, int d){
   int m, sol = -1;
    while( s <= e) {
        m = (s+e)/2;
        if( A[m] == d){
            sol = m;
            e = m -1;
        }
        else if (A[m] > d) e = m -1;
        else s = m+1;
    }
    return sol;
}

int BinarySearchUpper(int s, int e, int d){
    int m, sol = -1;
    while( s <= e) {
        m = (s+e) /2;
        if( A[m] == d){
            sol = m;
            s = m +1;
        }
        else if (A[m] > d) e = m -1;
        else s = m + 1;
    }
    return sol;
}

void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++) { 
        int lower = BinarySearchLower(0, N-1, B[i] );
        if( lower != -1 ){
            int upper = BinarySearchUpper(0, N-1, B[i] );
            cout <<  upper - lower + 1 << ' '; 
        }else{
            cout <<  0 << ' '; 
        }
    } 
}
int main() { 
    InputData(); 
    Solve();
    return 0; 
} 
/*10816 숫자카드2*/

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 
1
1
0
0
1

풀이

-오름차순 정렬

1 2 3 4 5

-숫자 1개씩 이진 탐색으로 검색 

중간 값을 구하기 위한 s,e값은 A[] array의 순서이다. 

if s = 0, e = N-1, d=1 부터 시작하면 

m = (s + e)/2; 

m = (0 + 4)/2=2;

A[2] =3이므로 

if(A[m] >d) 이므로 e=m-1로 값을 변경후 다시 찾는다.

s=0, e=1로 값 설정

m=(0+1)/2=0;

if(A[0]==d)에 부합하므로 값을 찾아서 return 1을 전달해 준다. 

/*[1920]수찾기*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)1e6)
int N;
int A[MAXN +10];
int M;
int X[MAXN+10];

void InputData(){
    cin >> N;
    for(int i =0; i<N; i++){
        cin >> A[i];
    }
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> X[i];
    }
}
bool BinarySearch(int s, int e, int d){
    int m;
    while(s<=e){
        m=(s+e)/2;
        if(A[m]==d) return 1;
        else if(A[m]>d) e=m-1;
        else s = m+1;
    }
    return 0;
}
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++){
        printf("%d\n", BinarySearch(0, N-1, X[i]));
    }
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*[1920]수찾기*/

libray를 이용해서 풀이하면 아래와 같이 간단히 할 수 있다.

http://www.cplusplus.com/reference/algorithm/binary_search/

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)1e6+10)
int N,M;
int A[MAXN],X[MAXN];
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++)
        cout<<binary_search(A, A+N, X[i])<<"\n";
}
void InputData(){
    cin >> N;
    for(int i =0; i<N; i++)
        cin >> A[i];
    cin >> M;
    for(int i=0; i<M; i++)
        cin >> X[i];
}
int main(){
    InputData();
    Solve();
    return 0;
}

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

풀이

- data 입력 받기 : N 숫자 개수 

- 먼저 입력된 값을 정렬 한다.그래야 중앙값, 범위를 간단히 계산 해 낼 수 있다. 

- 산술평균, 중앙값,범위는 정렬후 간단히 계산이 가능한데, 중앙값은 좀 더 작업이 필요하다. 

-

/*baekjoon 2108 통계학*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define MAXN  ((int)5e5)

int	N;
int Data[MAXN+10]; 
struct MaxData{
	int cnt,val;
};
int A[MAXN+10];
MaxData C[8000+10];
void OutputData(){
	cout << "Frequency : " << endl;
    for(int i = 0; i < 8010; i++){
		if( C[i].cnt >0){
    		cout << C[i].cnt << " " << C[i].val << endl;
		}
    }
}
void InputData(){
    cin >> N;
    for(int i = 0; i < N; i++){
    	cin >> Data[i];
    }
}
bool comp(struct MaxData a, struct MaxData b)
{ 
	if( a.cnt == b.cnt ){
		return a.val < b.val;
	}else{
		return a.cnt > b.cnt;
	}
}
int SortSecond(){
	int maxvalue=0, j=0;
	for(int i=0; i< 8010; i++){
		if(A[i] >0 ){
			if(i<=4000){
				C[j].val=i;
			}
			else{
				C[j].val=4000-i;
			}
			C[j].cnt=A[i];
			j++;
		}
	}
	sort(C, C+8010,comp);
	if(C[0].cnt == C[1].cnt){
		maxvalue= C[1].val;
	}else{
		maxvalue=C[0].val;
	}

	return maxvalue ;
}
void Solve()
{
	double sum=0;
	sort(Data, Data+N);
    for( int i=0; i<N; i++){
		sum += Data[i];
		if( Data[i] >=0){
			A[Data[i]]++;
		} else{
			A[4000-Data[i]]++;
		}
    }
	cout << round(sum/N) << endl;
	cout << Data[N/2] << endl;
	cout << SortSecond() << endl;
	cout << abs(Data[0] - Data[N-1]) << endl;
}
int main()
{
	InputData();
	Solve();
	return 0;
}
/*baekjoon 2108 통계학*/

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

풀이

/*baekjoon 11651 좌표 정렬하기*/
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 100001

struct ST{
	int x, y;
};

int	N;
struct ST XYdata[MAX];

void InputData(){
	//input data size
    scanf("%d", &N);
	//input data
    for( int i=0; i<N; i++ ){
    scanf("%d %d", &XYdata[i].x, &XYdata[i].y );
    }
}

void OutputData(){
	for( int i=0; i<N; i++){
		printf("%d %d", XYdata[i].x, XYdata[i].y);
	printf("\n");
	}
}

bool comp(struct ST i, struct ST j){ 
	if (i.y < j.y) 
		return true;
	else if (i.y == j.y)
		return (i.x < j.x); 
	else 
		return false;
}

int main()
{
	InputData();
	sort( XYdata, XYdata+N, comp );
	OutputData();

	return 0;
}
/*baekjoon 11651 좌표 정렬하기*/

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

풀이