[2023 하계 모각코] "아는 형님의 아는 사람의 아는 동생의 아는 코딩이요" [6회차] 계획 및 결과

6회차 목표 : C++ 공부 및 DFS 알고리즘 공부.

-C++ 공부 및 DP(다이나믹 프로그래밍) 알고리즘 공부.

일정 : 8/4 16:00~19:00

 

6회차 공부 내용 :

-C++ 공부

TCP School의 내용을 토대로 공부하였다.

C++은 C와 마찬가지로 구조체를 만들 수 있는데 C와는 달리 함수까지도 멤버 변수로 가져갈 수 있다!

C++의 구조체는 객체 지향 프로그래밍의 Class의 기초가 된다.

 

 클래스는 클래스의 멤버 변수를 프로퍼티(property), 멤버 함수를 메소드(method)라고도 한다.

객체 지향프로그래밍은 모든 데이터를 객체로 보며, 객체가 프로그래밍의 중심이 되게 하는 것이고, 객체를 만들어내기 위한 틀이 바로 클래스이다.

 

추상화, 캡슐화, 정보은닉, 상속성, 다형성과 같은 특징을 객체 지향 프로그패밍이 가진다.

 C++에서 클래스는 구조체와 마찬가지로 사용자가 정의할 수 있는 타입이다. 따라서 클래스를 사용하려면, 해당 클래스 타입의 객체를 선언해야한다. 선언된 해당 클래스 타입의 객체를 인스턴스(Instance)라고 한다.

Class book
{
private:
	int current_page_;
    	void set_percent();
public:
	int total_page_;
    	...
    
};

클래스를 만들고,

Book book1;
Book book2;
Book booooo;

인스턴스

 

이와 같이 자바에서 익숙하게 만들었듯이 비슷하게 만들 수 있다.

클래스의 접근 제어는 public, private, protected로 할 수 있다.

기본 접근 제어는 private이고, 구조체 및 공용체는 public이다.

 

다음에는 OOP[객체 지향 프로그래밍]의 특징에 대해서 계속해서 공부해나갈 것이다.

 

-DP(다이나믹 프로그래밍) 알고리즘 공부

동적 계획법에 대하여 공부하였다.

코드트리 : NOVICE HIGH의 자료구조 알고리즘의 내용을 토대로 공부하였다.

 

동적 계획법 : 큰 문제를 풀기 위해서 작은 문제를 해결하고, 작은 문제들을 해결한 결과를 기억하여 큰 문제를 해결하도록 하는 방법.

점화식, 초기 조건을 작성하고 이것들을 토대로 문제를 해결하도록 한다. 점화식을 기반으로 하는 것이 큰 특징이다.

 

다이나믹 프로그래밍: 동적계획법 : DP라고 하자!

 

DP 문제를 해결하는 방법은 재귀함수가 있다. 대표적으로 피보나치이다.

피보나치는 보통 재귀함수로만 익히 알고있는 방법으로 풀면 이미 연산한 과정의 결과를 이미 구해도 계속 연산을 다시 반복하는 경우가 생긴다. 그래서 시간이 되게 오래걸리게 되는데 이걸 해결하는 것이 DP의 Memoization이다.

 

fibo(10)을 했을 때, fibo(3)을 여러 번 수행하는데 그 fibo(N)의 결과를 기억하는 배열을 만들어서 fibo(N)의 결과를 Arr[N]에 저장하도록 하고, 나중에 fibo(N)을 수행하라 하면, Arr[N]을 호출하도록 한다.

 

DP의 Tabulation은 for문을 이용한 방법으로 순서대로 배열에 값에 저장하는 것이 특징이다. 즉, fibo(1)을 구해서 Arr에 넣고, fibo(2)도 구해서 Arr에 넣고 차근 차근 넣어서 값을 만드는 것이 특징이다.

 

그래서 Memoization과 Tabulation의 차이는 전자는 N부터 시작해서 작은 수로 내려가는 Top-Down 방식, 후자는 제일 낮은 것부터 시작해서 구하는 마지막 차례까지 올라가는 Bottom-Up 방식이다.

 

이렇게 DP의 방식을 배웠지만, 점화식을 이용해서 만든다는 것은 동일하다. 이후 코드 트리의 문제를 풀어보았다.

코드 트리 Intermediate low 에서 DP 2의 문제를 풀었다.

 

https://www.codetree.ai/missions/2/problems/select-proper-clothes?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

#include <bits/stdc++.h>
using namespace std;

//#include <iostream> 사용하는 헤더파일 정리하자~
//#include <vector>
//#include <algorithm>

int dpdp(const vector<vector<int>>& nums, int N, int M) {
    int n = nums.size();
    if (n == 0) return 0;

    // dp[i]는 i번째 원소를 끝으로 하는 최대 연속 부분 수열의 합을 저장.
    vector<int> v3(N+1,0);
    vector<vector<int>> dp(M+1,v3);
    
    dp.push_back(v3);

    //dp에 0이 들어간 경우도 생각해야한다. nums에 0이 있는 것과는 달라.
    //nums에서 0을 만났을 때는 못 입는 거야. dp에서 0을 만난 거는 그 옷을 입지 않았단 것.
    int maxSum = 0;

    for (int i = 2; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (nums[i][j] != 0&&nums[i-1][k]!=0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(nums[i][j] - nums[i-1][k]));
                }
                
            }
            //dp에서 i일에 j번째 옷을 입었을 때 갖게 되는 연속되는 [화려함의 차이]의 합을 뜻해.
            //그래서 dp[i][j]는 k번째 옷에서 j번째 옷으로 선택했을 때 그 차이를 확인하는 거지.
            //못 입는 옷은 해당 dp 인덱스에 0이 자리 잡게 돼(처음 초기화 값 0 ) 값이 변경되지 않았으니까.
            
        }
        //cout << endl;
    }
    
    for (int j = 1; j <= N; j++) {
        //cout << dp[M][j]<<" ";
        maxSum = max(maxSum, dp[M][j]);
    }

    return maxSum;
}

int main() {
    int N,M;
    cin >> N;
    cin >> M;
    //2차원 벡터 만드는 법!
    vector<int> v2(N+1,0);
    vector<vector<int>> nums(M+1,v2);
    //v2를 먼저 선언해줘야지 안 그러면 vector range 이상하게 한다고 오류 뜬다.
    
    
    //날짜를 인덱스로 박고, N개의 옷이 있으니까 행렬은 N이 열로, M는 행의 갯수로. 거꾸로네
    
    nums.push_back(v2);
    
    int s, e, v; //[입을 수 있는 첫 날짜],[입을 수 있는 마지막 날짜],[화려함~]
    for (int i = 1; i <= N; i++) {
        cin >> s;
        cin >> e;
        cin >> v;
        for (s; s <= e; s++) {
            nums[s][i] = v;
        }
    }
    /*
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cout << nums[i][j]<<" ";
        }
        cout << endl;
    }
    cout << endl;
    */


    int result = dpdp(nums,N,M);
    cout <<  result << endl;
    
    return 0;
}