okayoki

#문제

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

#작성 코드

##

visit 배열은 (1,1)에서 출발해서 몇 번째만에 해당 칸에 도착했는지를 저장하는 배열이다.

bfs를 이용해 연결되어있는 모든 1을 탐색하면서 그 칸까지 몇 번째만에 도착했는지를 세서, (N, M)에 얼마가 저장되어있는지를 출력하면 된다.

이전에 풀었던 2667 단지번호붙이기, 1012 유기농배추 문제와 거의 똑같이 풀었다.

차이점은 visit 배열.

#191206 REVIEW

void input()  으로 입력받는다.

bool isIn()    지도 범위 내에 좌표가 존재하는지 체크

void solve(int i, int j){

      1. 시작지점에 방문. map[i][j]=9, visit[i][j]=1 저장. visit배열에는 시작지점과 도착지점을 포함해서 여기까지 오는데 몇 칸 걸렸는지를 저장하는 배열이다.

      2. 시작지점을 큐에 넣는다.

      3. 큐가 빌 때까지 반복한다.

            1. q.push({nx, ny});

            2. visit[nx][ny] = visit[x][y]+1;      nx,ny는 x,y에서 상하좌우위치에 있으므로 1칸 차이난다. x,y에 온 칸 수 + 1칸을 저장한다.

            3. map[nx][ny] =9; 저장해서 다시 방문하지 않도록 한다.

                  1. 현재 위치를 x, y,에 저장하고, q.pop()실행.

                  2. 현재 위치의 상, 하, 좌, 우를 체크한다. 미로의 범위 내에 존재하고, 길이라면 방문한다.

            4. visit[N][M]을 출력한다. (N,M은 도착지점임)

}

#문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

#작성 코드

##

우선순위 큐는 최대 힙 구조이기 때문에 pq.top() 연산을 하면 정렬 기준에서 가장 큰 값이 리턴된다.

따라서 거리가 가장 짧은 것이 제일 먼저 나오게 하려면 시작정점~현재정점 거리를 음수화해서 저쟝해야한다.

#191206 REVIEW

void dijkstra(int K){

    1. 최단거리 s[i]를 무한대로 초기화한다.

    2. s[K] = 0저장.

    3. 우선순위 큐를 선언하고, {0, K}를 PUSH

    4. while(!pq.empty()) 반복한다.

          1) 현재정점위치 = pq.top().second; 시작~현재정점거리 = -pq.top().first; pq.pop()실행.

          2) s[현재정점] < 현재정점거리 => continue로 패스한다.

          3) 현재정점에 연결되어있는곳들 차례로 방문한다. i=0~node[현재정점].size

                ① 다음정점위치 = node[현재정점][i].second

                ② 시작~다음정점거리 = node[현재정점][i].first + 현재정점거리;

                ③ if( s[다음정점] > 시작~다음정점거리 )

                       a. s[다음정점] = 시작~다음정점거리

                       b. 큐에 {-시작~다음정점거리, 다음정점} PUSH

}

#문제

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

#작성 코드

##

#191206 REVIEW

solve()

    // 지도 돌면서 배추 찾으면 cnt 1 증가시키고 그 좌표를 매개변수로 넘겨서 worm 함수 실행

worm()

    //해당 좌표 방문처리한다(area[i][j] = cnt+1)

    // 해당 좌표를 i*N+j로 압축해서 큐에 넣는다.

    // 큐가 빌때까지 반복하며, 큐의 맨 앞에 있는 원소를 압축 풀어서 해당 좌표 상하좌우 비교하고

    // 상하좌우가 배추밭 내에 있고, 배추가 존재하면 큐에 넣고, 해당좌표 방문처리(cnt+1을 저장)한다.

    // 이 부분에서 방문처리 하는 것이 중요!!!! 큐에 넣으면서 방문처리해야 다음에 다른 곳에서 중복 방문하지 않는다.

    // 큐가 비어서 while문을 빠져나오면 cnt를 출력한다.

# 191205 QUESTION

초반 코드를 몇 번이나 고쳐도 메모리 초과 오류가 발생했다.

상하좌우의 배추를 체크하면서 큐에 넣고, 어차피 while문을 돌면서 pop하기 전에 cnt+1으로 체크하게 될테니까 큐에 push하면서 cnt+1으로 체크하지 않았더니 오류가 발생했다. 왜그럴까???

=> 큐에 푸시하면서 체크해야 한번 큐에 넣었던 배추를 그 다음번에 다시 방문하지 않으니까!

#문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

#작성 코드

#include <iostream>
using namespace std;

int N;
int A[1001];	// N최대값 1000이므로. 인덱스 1~1000 사용

// 수열 A의 i번째 수까지 증가하는 부분 수열의 원소 개수
int d[1001]; 

int solve(){
	int result=0;
	
	for(int i=1; i<=N; i++){
		// i번째 수 이전의 수들 중에서 A[i]보다 작은 수에 대해 조사. 
		for(int j=1; j<i; j++){
			if( A[i] > A[j] ){
				// i번째 수까지의 증가 수열의 길이
				// = i이전에 A[i]보다 작은 수까지의 증가 수열의 길이 + 1 (i를포함시킨다.) 
				d[i] = max( d[i], d[j]+1 );
			}
		}
		// d[i]를 갱신하면서, result에 가장 큰 d[i]를 갱신한다. 
		result = max(result, d[i]);
	}
	return result;	// 가장 긴 증가수열의 길이를 리턴. 
}

int main(){
	// 수열의 원소 개수 입력. 
	cin>>N;
	// N개의 원소 입력. 
	for(int i=1; i<=N; i++){
		cin>>A[i];
	}	
    // d[1001] 전역배열의 원소를 모두 1로 초기화한다.
	fill_n(d, 1001, 1);
    
	cout<<solve()<<"\n";
	return 0;
} 

##

전역배열을 모두 1로 초기화하려고  int d[1001] = {1, }; 코드를 사용하였는데, 이것때문에 틀렸음을 알았다

위의 코드는 배열의 첫 번째 원소만 1로 초기화하고 나머지는 모두 0으로 초기화되기 때문에 원하는 결과를 얻을 수 없었다.

https://shjz.tistory.com/38 에서 배열을 초기화 하는 방법을 찾았다.

int d[1001]; 으로 전역 배열을 선언하고,

std::fill_n(d, 1001, 1); 으로 main 함수 내에서 초기화하는 방법을 사용해야겠다.

#문제

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

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. 단지의 개수, 각 단지의 집 수를 오름차순으로 출력한다.