[C언어 백준 풀이][Silver II] 1012번 : 유기농 배추 / 11053번 : 가장 긴 증가하는 부분 수열 / 1931번 : 회의실 배정 (그리디 알고리즘)

프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 SIlver II에 해당하는 문제인 1012번 유기농 배추, 11053번 가장 긴 증가하는 부분 수열, 1931번 회의실 배정 문제를 풀이해보도록 하겠습니다.

 

 

1012번 : 유기농 배추

 

문제가 길지만 요약해보면 1이 상하좌우로 이어진 몇 개의 그룹으로 나누어져 있는지 찾는 문제입니다.

1을 찾아서 연결된 부분들을 모두 찾는 문제이므로, 탐색(DFS 또는 BFS) 문제임을 알 수 있습니다.

BFS보다는 DFS의 구현이 비교적 간단하기 때문에 DFS를 이용하여 문제를 해결해보도록 하겠습니다.

 

#include<stdio.h>

int field[51][51], visit[51][51], M, N, K, count;

void DFS(int x, int y) {
    visit[x][y] = 1;
    if(field[x+1][y] && !visit[x+1][y]) DFS(x+1, y);
    if(field[x-1][y] && !visit[x-1][y]) DFS(x-1, y);
    if(field[x][y+1] && !visit[x][y+1]) DFS(x, y+1);
    if(field[x][y-1] && !visit[x][y-1]) DFS(x, y-1);
}

int main() {
    int T, x, y;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        count = 0;
        scanf("%d %d %d", &M, &N, &K);
        for(int j=0; j<=M; j++)
            for(int k=0; k<N; k++) {
                field[j][k] = 0;
                visit[j][k] = 0;
            }
        for(int j=0; j<K; j++) {
            scanf("%d %d", &x, &y);
            field[x][y] = 1;
        }
        for(int j=0; j<M; j++)
            for(int k=0; k<N; k++)
                if(field[j][k] && !visit[j][k]) {
                    DFS(j, k);
                    count++;
                }
        printf("%d\n", count);
    }
}

 

우선 테스트케이스에 해당하는 T라는 변수가 있기 때문에, 바깥 루프를 만들어줘야 합니다.

그 다음 각각의 케이스에 대해 field와 visit을 초기화해줘야 하므로 맨 앞에 초기화 반복문을 만들어줍니다.

field에 배추의 좌표를 저장하고 DFS를 구현하는데, for문으로 밭을 스캔하면서 배추가 있는 좌표가 있고 해당 좌표를 아직 방문하지 않았다면 DFS 탐색을 시작합니다.

DFS는 visit을 체크하고 그 좌표에서 상하좌우로 배추가 인접되어 있는 동시에 아직 방문하지 않은 경우 재귀적으로 방문을 시작합니다.

방문이 끝나면 인접한 배추들은 모두 visit이 체크되어 있으므로 count를 1 늘려주고 다시 다른 배추를 탐색을 시작합니다.

 

 

11053번 : 가장 긴 증가하는 부분 수열

 

주어진 배열에 있는 수들을 순서를 고려하여 부분 수열을 만들 때, 오름차순이 되는 부분 수열들 중에서 가장 길이가 긴 수열의 길이를 구하는 문제입니다.

동적 프로그래밍으로 해결할 수 있는 유명한 문제들 중 하나입니다.

 

#include<stdio.h>

int main() {
    int N, A[1005] = {0, }, D[1005] = {0, 1}, subSeq[1005] = {0, }, subLen = 1;
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);
    subSeq[1] = A[1];
    for(int i=2; i<=N; i++) {
        for(int j=0; j<=subLen; j++)
            if(A[i] > subSeq[j]) {
                if(j == subLen) {
                    subSeq[++subLen] = A[i];
                    D[i] = subLen;
                    break;
                }
                else if(A[i] < subSeq[j+1]) {
                    subSeq[j+1] = A[i];
                    D[i] = j+1;
                    break;
                }
            }
    }
    printf("%d", subLen);
}

 

D라는 배열을 만들어서 해당 번째 숫자가 사용된다면 최대 몇 번째에 위치할 수 있는지 기록합니다.

subSeq은 현재까지 탐색한 번호 내에서 선택된 최선의 수열을 저장하는 배열입니다.

subLen은 현재까지 탐색한 번호 내에서 선택된 최선의 수열의 길이를 나타내는 변수입니다.

코드를 보면 A 배열의 수를 하나씩 꺼내서 subSeq에 있는 번호들 중에서 어디에 들어갈 수 있는지 기록하여 D[i]에 번호를 매깁니다.

 

 

보충 설명을 위해 출력부만 수정해서 위와 같이 출력해보았습니다.

세 번째 줄에 D[i]가, 네 번째 줄에 D[i]에 해당하는 번호 중 가장 작은 번호가 저장됨을 알 수 있습니다.

여기서 탐색 부분을 이진 탐색으로 수정하면 O(N log N) 알고리즘으로 더욱 간략화시킬 수 있으며, 간략화된 방법으로만 해결이 가능한 문제 풀이 해설을 아래 링크에 걸어두었으니 필요하신 분들은 참고해주세요.

 

[C언어 백준 풀이][Platinum V] 가장 긴 증가하는 부분 수열 1, 2, 3, 4, 5 풀이 (최장 증가 부분 수열 문

 

알고리즘에 대한 추가적인 이해나 설명이 필요하신 분들은 "최장 증가 부분 수열" 키워드를 검색해서 더 많은 내용을 참고해도 좋을 것 같습니다.

저의 경우에는 알고리즘에 대한 추가적인 이해는 나무위키의 "최장 증가 부분 수열" 문서에서 참고하였습니다.

 

 

1931번 : 회의실 배정

 

N개의 회의에 대해 각 회의이 시작 시간과 끝나는 시간이 주어질 때, 진행 시간의 중복 없이 최대로 가능한 회의의 수가 몇 개인지 출력하는 문제입니다.

이 문제 역시 대표적인 그리디 알고리즘 문제이므로 그리디 알고리즘을 최대한 사용하는 쪽으로 아이디어를 고민하면 좋습니다.

 

#include<stdio.h>

int start[100005], end[100005];

void merge(int left, int mid, int right) {
    int startCopy[100005], endCopy[100005], i = left, j = mid+1, k = left;
    while(i<=mid && j<=right) {
        if(end[i] < end[j] || (end[i] == end[j] && start[i] < start[j])) endCopy[k] = end[i], startCopy[k++] = start[i++];
        else endCopy[k] = end[j], startCopy[k++] = start[j++];
    }
    while(i<=mid) endCopy[k] = end[i], startCopy[k++] = start[i++];
    while(j<=right) endCopy[k] = end[j], startCopy[k++] = start[j++];
    for(int a=left; a<=right; a++) end[a] = endCopy[a], start[a] = startCopy[a];
}

void mergeSort(int left, int right) {
    int mid;
    if(left < right) {
        mid = (left+right)/2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        merge(left, mid, right);
    }
}

int main() {
    int N, temp, curTime = 0, count = 0;
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d %d", &start[i], &end[i]);
    mergeSort(0, N-1);
    for(int i=0; i<N; i++) {
        if(start[i] >= curTime) {
            curTime = end[i];
            count++;
        }
    }
    printf("%d", count);
}

 

회의의 시작 시간과 길이에는 관계 없이, 회의가 빨리 끝나야 그 다음에 시작할 수 있는 회의가 많아지므로 반드시 가장 먼저 끝나는 회의부터 배정을 해야 합니다.

따라서 회의가 끝나는 시간 순서대로 배열을 한 뒤 그 다음에 시작할 수 있는 회의들 중에서 가장 빨리 끝나는 회의를 선택하는 과정을 반복하여 배정을 해주면 됩니다.

 

이 때 끝나는 시간으로만 오름차순 배열을 하면 똑같이 끝나는 시간인 회의들 중에서도 더 늦게 시작하는 회의를 먼저 검사하기 때문에, 끝나는 시간이 같은 회의들에 대해서는 시작 시간에 대해 정렬을 해주어야 합니다.

저의 경우에는 C++의 <algorithm.h> 없이 그냥 merge 정렬을 구현하였기 때문에 조건문을 추가하여 쉽게 구현할 수 있었습니다.