본문 바로가기

내일배움캠프 안드로이드 3기

[TIL] 24.03.05 알고리즘, 2주차 개인과제

1. 알고리즘 문제 해결

 

퇴사 2(백준 15486):

 이번 문제도 DP 문제이다. 입력으로 들어오는 n이 1,500,000개까지 주어질 수 있기 때문에, 문제를 보자마자 떠올릴 수 있는 O(n^2)의 방법으로는 해결할 수 없다. DP로 풀게 되면 O(n)이 될 것 같아서, 그렇게 접근해봤는데 선뜻 점화식이 명확하게 떠오르지 않았다. 1일차 상담 일정부터 탐색하게 되면 기간에 따른 제약사항을 반영하기 까다로웠다.

 그래서 역방향인 N일차부터 계산하는 방법을 썼다. 만약 일정표의 걸리는 기간을 탐색 중인 일자 i에 더했을 때, N 이하라면 할 수 있는 상담이라는 의미이다. 그렇다면 dp[i+걸리는 기간] 값에 이 상담으로 얻을 수 있는 수익을 더한 값과 dp[i+1] 값을 비교해 더 큰 값을 dp[i] 값으로 채택할 수 있다. 이를 N일차부터 1일차까지 탐색하며 DP 배열을 완성하면 배열의 가장 앞에는 N일동안 얻을 수 있는 최대 수익이 담겨있게 된다.

 

 타임라인의 끝을 확인해서 이용가능 하다면, 해당 타임라인을 넣을 수 있는 상태를 찾아 집어넣고 수익값을 비교해보는 매커니즘인데, 줄글로만 쓰려니 표현이 쉽지가 않다. 마우스로 그림이라도 그리자니 알아보기도 힘들고.. 그래도 코드를 본다면 조금 더 이해가 쉬울 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<pair<int, int> > schedule(n);

    for(int i=0; i<n; i++) {
        cin >> schedule[i].first >> schedule[i].second;
    }

    vector<int> dp(n+1, 0);

    for(int i=n-1; i>=0; i--) {
        if(i+schedule[i].first<=n) {
            dp[i] = max(dp[i+1], schedule[i].second+dp[i+schedule[i].first]);
        }else {
            dp[i] = dp[i+1];
        }
    }

    cout << dp[0];
}

 

 

 

2. 2주차 개인과제

 

 프로그래밍 기본기 주차 개인과제가 나왔다, 계산기를 구현하는 것인데 코틀린에 익숙해지기 위한 주간이라 앱을 만드는 것이 아닌 콘솔 상에서 동작하는 프로그래밍을 만들어야 한다.

 

 

 

 전반적으로, 학부생 저학년 때 한번쯤 거쳐가는 계산기 과제와 유사하다. 엄청 복잡한건 아니지만, 학부생 저학년때와 달리 지금쯤 와서 보니 신경쓰기 시작하면 신경 써야할 부분이 참 많은 것 같다.

 인풋과 아웃풋에 대한 안내가 없어서, 입맛대로 제한들을 두고 작성하는 방법도 있지만 그런 방법으로 작성하면 성장이 없을 것 같아서 조금 고민을 했다. 

 

 ' 식을 어떻게 입력 받을 것인지, 하나의 완성된 문자열 식으로 입력 받는다면 파싱이랑 분할은 어떻게 할지, ZeroDivision 같은 Exception들은 어느 시점에 처리할지, 인풋으로 입력받는 수는 정수만 받을 지 실수 모두를 받을지, 연산자는 하나만 받을지 여러개를 받을지, 또 오버플로우는 어떻게 처리할지... '

 

 Lv??의 구현이야 자료구조랑 알고리즘 공부하다 보면 한번쯤 공부하는 문제이고, 오히려 위의 저런 의도되지 않은 동작과 데이터 전후처리가 더 골치 아픈 것 같다. 아무래도 인풋과 아웃풋이 전혀 정해지지 않아서 그런 것 같다. 그리고 추상 클래스를 이용하게 하는 의도는 좋지만, 사실 청사진을 머리 속에 그려봤을 땐 조금 굳이 싶은 구조이긴 하다. 물론 작성하다 보면 또 달라질 수 있는 부분이지만..
 일단 그래도 적절한 선에서 열심히 작성해봐야겠다.