알고리즘 문제 풀이 51번 : 영지(territory)선택:(large)

 

목차

---

• 문항 분석

• Code

• 결과 및 분석

---

문항 분석

기존의 방법의 문제를 개선했다. 

같은 문항 50번 문항에서 2차원 배열 내 일부 배열의 합을 구하기 위해서 4중 for문을 사용했다.

위 방법으로 문제를 풀 수 있지만, for문의 반복 횟수가 너무 많아지는 문제가 발생했다.

실제로 2차원 배열의 크기를 키울수록 반복횟수는 훨씬 많이 증가하는 문제를 보였다.

 

소위 Dynamic Programming 라고 부르는 방법을 for문의 반복 횟수를 줄이기 위한 전략으로 채택함.

Code

 

//
//  51_territory(large).cpp
//  Algorithm
//
//  Created by WANKI KIM on 2021/01/14.
//
// TODO: 사각형 격자로 이뤄진 땅에서 가장 많은 오렌지 나무가 심겨진 지역 찾기.
//
// MARK: 강의 보며 해결하였음. 직접 문제를 다시 풀어볼 필요 있음. 복습 필요.
//
// Dynamic Programming : 2중 for 문을 사용해서 문제 접근.
//
// 가로.세로의 길이가 최대 700
//
#include <iostream>
using namespace std;

int a[701][701], dy[701][701];
int main()
{
    int h,w;
    cin >> h >>w;
    int i,j;
    for(i=1;i<=h;i++){
        for(j=1;j<=w;j++){
            cin >> a[i][j];
            dy[i][j] = dy[i-1][j] + dy[i][j-1] -dy[i-1][j-1] + a[i][j];
        }
    }
    int miniH,miniW;
    int result = INT_MIN;
    int temp;
    cin >> miniH >> miniW;
    for(i=miniH;i<=h;i++){
        for(j=miniW;j<=w;j++){
            temp = dy[i][j] - dy[i-miniH][j] - dy[i][j-miniW] + dy[i-miniH][j-miniW];
            if(temp>result) result = temp;
        }
        
    }
    cout << result;
    return 0;
}

결과 및 분석

실행시간 뿐만 아니라 코드 또한 오히려 짧아졌다.

공부해야할 내용. 
brute force와 dynamic programming  (공부할 거 캐많음.. 어쩌지)

 

 

해당 글은 'it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코테 대비' 강의를 수강하며, 개인적으로 정리하기 위해 업로드하였습니다.

강좌 : https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#