컴퓨터 환경 OS : Ubuntu22 LTS (64-bit) HW(CPU/GPU) : Intel Core i9-9980XE / NVIDIA GeForce GTX 1080 Ti CUDA : 11.4

DROID-SLAM 을 설치하는 도중 컴파일 오류가 발생함.

[1/3] /usr/local/cuda-11.4/bin/nvcc -I/home/username/droid-slam/thirdparty/eigen -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/torch/csrc/api/include -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/TH -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/THC -I/usr/local/cuda-11.4/include -I/home/username/anaconda3/envs/droid_env/include/python3.7m -c -c /home/username/droid-slam/src/correlation_kernels.cu -o /home/username/droid-slam/build/temp.linux-x86_64-cpython-37/src/correlation_kernels.o -D__CUDA_NO_HALF_OPERATORS__ -D__CUDA_NO_HALF_CONVERSIONS__ -D__CUDA_NO_BFLOAT16_CONVERSIONS__ -D__CUDA_NO_HALF2_OPERATORS__ --expt-relaxed-constexpr --compiler-options ''"'"'-fPIC'"'"'' -O3 -gencode=arch=compute_60,code=sm_60 -gencode=arch=compute_61,code=sm_61 -gencode=arch=compute_70,code=sm_70 -gencode=arch=compute_75,code=sm_75 -gencode=arch=compute_80,code=sm_80 -gencode=arch=compute_86,code=sm_86 -DTORCH_API_INCLUDE_EXTENSION_H '-DPYBIND11_COMPILER_TYPE="gcc"' '-DPYBIND11_STDLIB="libstdcpp"' '-DPYBIND11_BUILD_ABI="cxxabi1011"' -DTORCH_EXTENSION_NAME=droid_backends -D_GLIBCXX_USE_CXX11_ABI=0 -std=c++14
FAILED: /home/username/droid-slam/build/temp.linux-x86_64-cpython-37/src/correlation_kernels.o
/usr/local/cuda-11.4/bin/nvcc -I/home/username/droid-slam/thirdparty/eigen -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/torch/csrc/api/include -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/TH -I/home/username/anaconda3/envs/droid_env/lib/python3.7/site-packages/torch/include/THC -I/usr/local/cuda-11.4/include -I/home/username/anaconda3/envs/droid_env/include/python3.7m -c -c /home/username/droid-slam/src/correlation_kernels.cu -o /home/username/droid-slam/build/temp.linux-x86_64-cpython-37/src/correlation_kernels.o -D__CUDA_NO_HALF_OPERATORS -D__CUDA_NO_HALF_CONVERSIONS_ -D__CUDA_NO_BFLOAT16_CONVERSIONS__ -D__CUDA_NO_HALF2_OPERATORS__ --expt-relaxed-constexpr --compiler-options ''"'"'-fPIC'"'"'' -O3 -gencode=arch=compute_60,code=sm_60 -gencode=arch=compute_61,code=sm_61 -gencode=arch=compute_70,code=sm_70 -gencode=arch=compute_75,code=sm_75 -gencode=arch=compute_80,code=sm_80 -gencode=arch=compute_86,code=sm_86 -DTORCH_API_INCLUDE_EXTENSION_H '-DPYBIND11_COMPILER_TYPE="_gcc"' '-DPYBIND11_STDLIB="_libstdcpp"' '-DPYBIND11_BUILD_ABI="_cxxabi1011"' -DTORCH_EXTENSION_NAME=droid_backends -D_GLIBCXX_USE_CXX11_ABI=0 -std=c++14
/usr/include/stdio.h(189): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(201): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(223): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(260): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(285): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(294): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(303): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(309): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(315): error: attribute "malloc" does not take arguments

/usr/include/stdio.h(830): error: attribute "malloc" does not take arguments

/usr/include/stdlib.h(566): error: attribute "malloc" does not take arguments

/usr/include/stdlib.h(570): error: attribute "malloc" does not take arguments

/usr/include/stdlib.h(799): error: attribute "malloc" does not take arguments

/usr/include/wchar.h(155): error: attribute "malloc" does not take arguments

/usr/include/wchar.h(582): error: attribute "malloc" does not take arguments

15 errors detected in the compilation of "/home/username/droid-slam/src/correlation_kernels.cu".

-> 결론은 "malloc 이렇게 쓰면 안됨" 인데 다른 연구원 선배님 컴퓨터(18.04) 에서는 잘 돌아가길래 gcc 버전만 7. 으로 낮춰주었다.

해결방법:

1. 현재 GCC 버전 확인:

   gcc --version

   현재 시스템에서 사용 중인 GCC 버전을 확인합니다.

2. GCC 버전 다운그레이드:

   호환되는 GCC 버전을 설치하기 위해 GCC를 다운그레이드합니다. GCC 7 버전으로 다운그레이드하는 경우. 뒤에 붙는 숫자는 priority.

   sudo apt-get install gcc-7 g++-7
   sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-7 700 
   sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-7 700

3. gcc 설정 확인 및 버전 확인

   sudo update-alternatives --config gcc
   gcc --version # 바뀌면 된거다!

4. 프로젝트 재설치: 변경된 환경에서 프로젝트를 다시 설치합니다.

   python setup.py install

가상환경은 파이썬 프로젝트가 독립된 환경에서 실행될 수 있도록 도와주는 도구이다. virtualenv 는 가상환경 생성 도구이다. 위와 같은 옵션을 추가하면 시스템 패키지를 가상환경으로 가져오지 않도록 할 수 있는데 global site 패키지에 액세스하지 못하는 것이 기본 동작이 되어 DEPRECATED 상태이다.

옵션 없이 해도 됨.

→ 언제 호출되는 지에 대해서 알아야함! 성능, 오류와 관련되어 있기 때문에 잘 알아두어야 함!

복사생성자

객체의 복사본을 생성할 때 호출되는 생성자

“새롭게 생성되는 객체가 원본 객체와 내용이 같으면서도 완전한 독립성을 가진다”

클래스 이름(const 클래스이름 &rhs)
//const는 r-value reference 를 쓸 때 원칙처럼 사용! - 원본손상 예방
//EMC++인가 Google Style Guide에 나왔는데 기억 안남...

#include <iostream>
using namespace std;

class CMyData{
public:
    CMyData(){
        cout<<"CMydata()"<<endl;
    }

    CMyData(const CMyData &rhs){
        this->m_nData = rhs.m_nData;
                //생성되는 객체를 명시하고자 l-value에
                //의도적으로 this->() 표현
        cout<<"CMyDATA(const CMydata &)"<<endl;
    }

    int GetData(void) const {return m_nData;}
    void SetData(int nParam) {m_nData = nParam;}

private:
    int m_nData = 0;

};

int main(){
    CMyData a; //선언&디폴트
    a.SetData(10);

    CMyData b(a); //복사 생성자 선언 및 정의
    cout<<b.GetData()<<endl;

    a.SetData(20);

    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;

    return 0;
}

/* 출력결과
CMydata()
CMyDATA(const CMydata &)
10
20
10
*/

함수 호출과 복사 생성자

함수가 호출될 때 매개변수 param은 caller의 a를 복사해서 사용함

→ 두 개 만들고 복사까지 해야됨 → 성능ㅠㅠ

해결방법

1. 복사 생성자를 삭제해버림 - 클래스 생성자에서 r-value reference를 통한 생성을 아예 없애버림

    CTestData(const CTestDate &rhs) = delete;

1. 참조자를 사용함

    #include <iostream>
    using namespace std;
   
    class CTestData{
    public:
        CTestData(int nParam):m_nData(nParam){
            cout<<"CTestData(int)"<<endl;
            cout<<this->m_nData<<endl;
        }
   
        CTestData(const CTestData &rhs) : m_nData(rhs.m_nData){
            cout<<"CTestData(CTestData &)"<<endl;
        }
   
        int GetData(void) const {return m_nData;}
        void SetData(int nParam) {
            m_nData = nParam;
            cout<<this->m_nData<<endl;
        }
   
    private:
        int m_nData = 0;
    };
   
    void TestFunc(const CTestData &param){
        //a 객체를 복사생성하므로 param을 참조자로 불러옴.
        //대신 원본 훼손을 막기 위해 const를 붙여주는 게 원칙.
        // 그러면 SetData()가 안먹힘!!!
        cout<<"TestFunc()"<<endl;
        //param.SetData(20);
        cout<<param.GetData()<<endl;
    }
   
    int main(){
        cout<<"*****Begin*****"<<endl;
        CTestData a(10);
        TestFunc(a);
   
        cout<<"a : "<<a.GetData()<<endl;
        cout<<"*****End*****"<<endl;
   
        return 0;
    }
   
    /* 출력결과
    *****Begin*****
    CTestData(int)
    10
    TestFunc()
    10
    a : 10
    *****End*****
    */

깊은 복사와 얕은 복사

복사를 잘 사용하자…

#include <iostream>
using namespace std;

class CMyData{
public:
    CMyData(int nParam){
        m_pData = new int;
        *m_pData = nParam;
    }

    CMyData(const CMyData &rhs){ //복사 생성자를 선언하여 deep copy를 만들어줌!
        cout<<"CMyData(const CMydata &)"<<endl;
        m_pData = new int;
        *m_pData = *rhs.m_pData;
    }

    ~CMyData(){
        delete m_pData;
    }

    int GetData(){
        if(m_pData != NULL){
            return *m_pData;
        }
        return 0;
    }

    void SetData(int nParam) {*m_pData = nParam;}

private:
    int *m_pData = nullptr;
};

int main(){
    CMyData a(10);
    CMyData b(a);
    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;

    a.SetData(20);
    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;
}

/* 출력 결과
CMyData(const CMydata &)
10
10
20
10
*/

대입연산자

단순 대입(=)을 사용하면 shallow copy가 일어남.

따라서 연산자 다중정의(overload)를 통해서 deep copy를 해주어야 함.

operater= 를 통해서 ‘=’ 기본 연산자를 재정의할 수 있음!

#include <iostream>
using namespace std;

class CMyData{
public:
    CMyData(int nParam){
        m_pData = new int;
        *m_pData = nParam;
    }

    CMyData(const CMyData &rhs){
        cout<<"CMyData(const CMydata &)"<<endl;
        m_pData = new int;
        *m_pData = *rhs.m_pData;
    }

    ~CMyData(){
        delete m_pData;
    }

    CMyData& operator=(const CMyData &rhs){
        *m_pData = *rhs.m_pData;
        return *this;
    }

    int GetData(){
        if(m_pData != NULL){
            return *m_pData;
        }
        return 0;
    }

    void SetData(int nParam) {*m_pData = nParam;}

private:
    int *m_pData = nullptr;
};

int main(){
    CMyData a(10);
    CMyData b(20);
    CMyData c(30);
    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;
    cout<<c.GetData()<<endl;

    b=a;
    c.operator=(a);

    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;
    cout<<c.GetData()<<endl;

    a.SetData(100);

    cout<<a.GetData()<<endl;
    cout<<b.GetData()<<endl;
    cout<<c.GetData()<<endl;
}

/* 출력 결과
10
20
30
10
10
10
100
10
10
*/

묵시적 변환

변환 생성자(Conversion Constructor) :

생성자의 매개변수가 하나이고 해당 매개변수의 형을 출력하는 클래스의 경우, 매개변수 형식과 매우 높은 호환성을 가지므로 모호성이 발생함(int 1개를 생성자 매개변수로 하고, 멤버변수도 int 하나일 경우, int와 클래스가 헷갈릴 수 있음)

→ 불필요한 임시 객체를 만들어냄으로써 프로그램의 효율을 갉아먹음.

#include <iostream>
using namespace std;

class CTestData{
public:
    CTestData(int nParam):m_nData(nParam){
        cout<<"CTestData(int)"<<endl;
    }

    CTestData(const CTestData &rhs) : m_nData(rhs.m_nData){
        cout<<"CTestData(const CTestData &)";
    }

    ~CTestData(){
        cout<<"~CTestData()"<<endl;
    }

    int GetData() const {
        return m_nData;
    }

    void SetData(int nParam){
        m_nData = nParam;
    }

private :
    int m_nData = 0;
};

void TestFunct(CTestData param){
    cout<<" TestFunct() : "<<param.GetData()<<endl;
}

void TestFunct_r(const CTestData &param){
    cout<<" TestFunct(&) : "<<param.GetData()<<endl;
}
int main(){
    TestFunct(5);
    TestFunct_r(5);
    return 0;
}

/* 출력 결과
CTestData(int)
 TestFunct() : 5
~CTestData()
CTestData(int)
 TestFunct(&) : 5
~CTestData()
*/

void TestFunct() 함수 : CTestData 클래스가 int자료형에 대한 변환 생성자를 제공함 → param(5) 형태로 임시 객체가 생성됨

void TestFunct_r() 함수 : 컴파일러가 알아서 임시 객체를 생성한 후 임시객체에 대한 참조가 TestFunct_r()로 전달됨 → TestFunct_r(CTestData(5))

$\therefore$ 클래스를 매개변수로 사용하고자 한다면 참조형식으로 사용 + 변환 생성자 앞에 explicit 예약어 사용

→ 효율성을 중시, 사용자 코드에서 헷갈리지 않음

CTestData(int nParam) 앞에 ‘explicit’을 붙여주면 컴파일러가 임시객체를 생성하지 않음!

허용되는 변환

클래스가 변환 생성자를 지원하면 두 형식 사이에 호환성이 생김! → 그러나 반쪽짜리 변환…

클래스형은 int(혹은 다른 것)형으로 변환 불가

형변환 연산자로 변환 가능!!!

#include <iostream>
using namespace std;

class CTestData{
public:
    explicit CTestData(int nParam):m_nData(nParam){
        cout<<"CTestData(int)"<<endl;
    }

    operator int(void){
        return m_nData;
    }

    int GetData() const {
        return m_nData;
    }

    void SetData(int nParam){
        m_nData = nParam;
    }

private :
    int m_nData = 0;
};

int main(){
    CTestData a(10);
    cout<<a.GetData()<<endl;
    cout<<a<<endl; //10번줄 형변환 연산자
    cout<<(int)a<<endl; //C++에서 추천하지X, C언어 스타일
    cout<<static_cast<int>(a)<<endl; //C++스타일 형변환 연산자

    return 0;
}
/* 출력 결과
CTestData(int)
10
10
10
10
*/

• static_cast 형변환 연사자를 사용하면 제약이 있음 - ‘형변환 가능한 것들'만 해줌. 사용자의 실수를 막아줌.
• const_cast, static_cast , dynamic_cast, reinterpret_cast 형변환 연산자가 존재함. → 7장!
• 형변환 연산자에서 explicit 예약어 적용하면 묵시적 변환이 일어나지 않음! (위 코드 10번째줄)
  
  

임시 객체와 이동 시맨틱

이름없는 임시 객체

• 임시객체 : 연산 시에 컴파일러가 알아서 만들어주는데, 데이터형식에 따라서 필요한 용량이 개커질 수 있음…

• 생성자

  • Default : 클래스이름();

  • 변환 생성자 : 매개변수가 1개, explicit 선언해주어야함.

    클래스이름(param);

  • 다중 정의 생성자 : 매개변수 n개

  • 복사 생성자 : 클래스이름(const 클래스이름 &rhs)

• 이동 생성자 : 클래스이름(const 클래스이름 &&rhs) → r-value reference

  복사생성자와 대입연산자에 r-value reference를 조합해서 새로운 생성&대입을 한 것

  곧 사라질 r-value에 대하여 복사생성하지 않고 shallow copy 한 다음 원본 포인터가 소멸하는 방식으로 성능을 높여버림!

(스바…C++17 이라서 예제랑 결과가 안맞음…컴파일러 잘 골라서 돌리도록 하자…)

#include <iostream>
using namespace std;

class CTestData{
public :
    CTestData() {
        cout<<"CTestData()"<<endl;
    }

    ~CTestData(){
        cout<<"~CTestData() : "<<endl;
    }

    CTestData(CTestData &rhs)
    : m_nData(rhs.m_nData)
    {
        cout<<"CTestData(CTestData &)"<<endl;
    }

    CTestData(CTestData &&rhs)
    : m_nData(rhs.m_nData)
    {
        cout<<"CTestData(CTestData &&)"<<endl;
    }

    CTestData& operator=(const CTestData &) = default;

   int GetData() const {return m_nData;}
   void SetData(int nParam){m_nData = nParam;}

private :
    int m_nData = 0;
};

CTestData TestFunc(int nParam){
    cout<<"***TestFunc() Begin***"<<endl;
    CTestData a;
    a.SetData(nParam);
    cout<<"***TestFunc() End***"<<endl;
    return a;
}

int main(){
    CTestData b;
    cout<<"*****Before*****"<<endl;

    b = TestFunc(20); **//TestFunc의 임시결과를 저장할 때 이동생성자 호출됨**
    cout<<"*****After*****"<<endl;
    CTestData c(b);

    return 0;
}

+) 관련하여 읽어볼 자료 < Effective Modern Cpp > Item17. Special Memeber Function 자동 작성 조건을 숙지하라 -> 복사 생성자, 복사대입연산자, 이동 생성자, 이동대입연산자 에 대해서 나옴.

First Order System 을 base로 open-loop vs closed loop 제어성능 비교!

전체적으로 예시를 가지고 설명!

Open-Loop Control

DC모터 Inertia J. output x(t) 는 샤프트 각속도(rad/sec), input u(t)는 volage(V). 단, eletro-mechanical System의 도메인 특성을 다음과 같이 설정하여 가정함.

1) 전기적인 신호는 굉장히 빠름 → step response 2) Voltage v(t)는 모터토크에 바로 반영됨! Ku(t) = Torque … shaft에서! 3) shaft bearing에는 마찰이 존재함. - cx(t)

$J\dot{x} = Ku(t) - cx(t)$

$Assum = \begin{cases} J = 2kg \cdot m^2 \ K = 4 \frac{N\cdot m}{v} \ c = 10N \cdot m \cdot sec \end{cases}$

$⇒ 2\dot{x} + 10x = 4u\ x(0) = 0$

Step Normalize

$\begin{cases} \dot{x} + 5x = 2u \ x(0) = x_0 \end{cases}$

⇒ a = 5 > 0 → system is stable!

Design Objective

• “r” 을 “desired reference command” 라고 한다. → 여기서는 샤프트 속도!
• voltage u(t)를 입력하였을 때 실제 모터 샤프트 속도가 desired speed r에 수렴하는 지 확인해야함
• desired speed x(t)는 r에 수렴할 것임. r은 상수이다!

Step Response

$x(t) = \frac{b}{a}(1-e^{-at})u_0$

$\therefore x(t) = \frac{2}{5}(1-e^{-5t})u_0$

이 시스템이 Steady-State 에 도달한다고 할 때($t→\infin$), $\dot{x} = 0$이다.

$⇒ x_{ss} = \frac{b}{a}u_0 = \frac{2}{5}u_0$

Conclusion

Step Response에서 $x(t) → \frac{b}{a}u_0 = \frac{2}{5}u_0$ 에 수렴함. Design Object는 x(t)→r 하기 위한 V(t)를 찾아내는 것이다!

$\therefore u_0 = \frac{5}{2}r$ 해당하는 다이어그램은 다음과 같다.

각각 r=1,2,3일 때의 그래프이다. 같은 비율로 수렴하는 이유는 r만 다르고 T는 같기 때문이다. 3T에 95% 성능을 달성한다.

Open-Loop Disturbance Rejection

Real World 에서는 Wind Gust, Road Slope, Additional Load Torque 등의 disturbance가 있음.

Disturbance를 고려함으로써 설계한 제어기가 외란의 영향을 최소화할 수 있음.

Simple Disturbance 모델은 다음과 같다.

$\dot{x} + Ax = B(u+d)$

$d(t) = \bar{d} \ \ \ \ \forall t≥0$ 이고 system이 stable 하여 steady-state에 수렴한다고 할 때, steady-state value x(t)는 다음과 같이 쓸 수 있다(예제 연결)

$\dot{x} + 5x_{ss} = 2(u + \bar{d}) \ \therefore x_{ss} = r + \frac{2}{5}\bar{d}$

r = 1 로 고정하고 $\bar{d}$=0,1,2라고 할 때 그래프는 다음과 같이 그려짐

$\bar{x} = 1$ 일 때 $x_{ss} = 1.4 → steady-state error e_{ss} = x_{ss}-r = 0.4$

Proportional Control

간단한 closed-loop control strategy는 다음과 같이 input을 설정할 수 있음!

$u(t) = K_p(r-x(t))$

output x가 e에 영향을 줌 → e가 input u에 영향을 줌 → input u가 output x에 영향을 줌 → 반복…

⇒ Closed-Loop Control!

(예제 연결 적용)

$\dot{x} + 5x_{ss} = 2u \ u = K_p(r-x(t)) \ \therefore \dot{x} + 5x = 2Kp(r-x)$

⇒ $\dot{x} + (5 + 2K_p)x = 2K_pr$

System Things Check

Time-Constant T

$T = \frac{1}{a} = \frac{1}{5+2K_p}$

→ $K_p$ 값으로 응답성을 바꿀 수 있으며, $K_p$를 올리면 응답성이 올라가서 빠르게 r에 수렴함

Steady-State Value$x_{ss}$

$(5 + 2K_p)x_{ss} = 2K_pr$

$\therefore x_{ss} = \frac{2K_p}{(5 + 2K_p)}r = \frac{1}{1+\frac{5}{2K_p}}r \ e_{ss} = r-x_{ss} = r-\frac{1}{1+\frac{5}{2K_p}}r = \frac{2K_p}{2K_p+5}r$

→ $K_p$를 적당히 올림으로써 $e_{ss}$를 줄일 수 있음!

Open-Loop 와 비교

• response time이 빨라짐! → $K_p$
• $e_{ss}$를 줄일 수는 있지만 항상 존재함.

Proportional Control Disturbance Rejection

Open-Loop & Closed-Loop 의 Disturbance Rejection을 비교해보자!

$\dot{x} + 5x = 2(u + d) \ u = K_p(r-x(t))$

$\therefore \dot{x} + 5x = 2d + 2K_p(r-x) \ \dot{x} + (5 + 2K_p)x = 2K_pr + 2d$

disturbance $d(t)=\bar{d} \ \ \ \ \forall t≥0$ 일 때 steady-state value와 그 그래프는 다음과 같다.

$x_{ss} = \frac{2K_p}{5+2K_p}r + \frac{2}{5 + 2K_p}\bar{d}$

→ $K_p$를 높임으로써 disturbance 영향을 줄일 수 있음!

FeedForward Control

Open-loop와 P Control 을 접목시킨 제어방법.

(예제 연결하여 설명)

$\dot{x} + 5x = 2u \ u = K_p(r-x(t)) + K_fr \ \therefore \dot{x} + 5x = 2K_p(r-x) + 2K_fr \ \dot{x} + (5+2K_p)x = 2(K_p+K_f)r$

Time-Constant T

$T = \frac{1}{5+2K_p}$

Steady-State Error$E_{ss}$

$(5+2K_p)x_{ss} = 2(K_p+K_f)r$

$x_{ss} = \frac{2(K_p + K_f)}{5+2K_p}r$

$e_{ss} = r-x_{ss} = \frac{2-2K_f}{5+2K_p}r$

→설계자가 선택한 $K_p$, $K_f$로 $x_{ss}$ 설정 가능함.

$K_p$는 $T$, $K_f$는 $e_{ss}$ 와 연관성이 높음

단, FeedForward Control은 Disturbance Rejection과 연관성은 적음.

Introduction & General Solution

→ 이번 챕터에서는 1차 선형시스템과 General Solution, Free Response, Step Response만 다룸.

Impulse, Sinusoidal Response 는 진동학에서 다룸.

Input의 타입에 따라 솔루션을 설명할 수 있다.

Background Concept

• Stability : 안정성
• Time Constant : 시스템의 응답이 얼마나 따른지를 나타내는 척도
• Steady-State Value\

General Solution

초기 상태 $x(0) = x_0$ 와 임의의 input function u(t) 가 t≥0 에 대하여 주어질 때 1차 ODE를 다음과 같이 쓰고 솔루션을 구할 수 있다.

$\begin{cases} \dot{x} + ax = bu \ x(0) = x_0 \end{cases}$ (*1)

$x(t) = e^{-at}x_0 + \int_0^t e^{-a(t-\tau)}bu(\tau)d\tau$ (*2)

앞부분은 Free Response(=I.C Response), 뒤에 적분 부분은 Forced Response

Free Response & Time Constant

(=Inital Condition Response)

1차 ODE에서 $u(t) = 0 \ \ (\forall t≥0)$ 일때 forced response가 없으므로 다음과 같이 솔루션을 쓸 수 있음.

$x(t) = e^{-at}x_0$

이 때 solution의 특성은 a에 의하여 결정됨.

time constant T = $\frac{1}{a}$

이론적으로 3T(sec)에서 시스템의 95% 성능을 달성함.

• a > 0 : Free response는 stable함
• a = 0 : Free Response는 marginally stable함
• a < 0 : Free Response는 unstable함 → 논리적으로, 시스템이 음수sec에 시스템의 95%를 달성할 수 없음!

Step Response

step input은 다음과 같은 성격을 가진다.

$u(t) =\begin{cases} 0 (t<0) \ u_0 (t≥0) \end{cases}$

이 때 $u_0$는 상수이다. general solution을 이용하여 퍼포먼스를 보여줄 수 있다.

$x(t) = e^{-at}x_0 + \int_0^t e^{-a(t-\tau)}bu(\tau)d\tau$

$a>0$일 때 솔루션은 다음과 같이 일반화할 수 있다.

$x(t) = e^{-at}x_0 + \frac{b}{a}(1-e^{-at})u_0$

$a>0$일 때 $t→\infin$하면(steady-state) $x(t) → \frac{b}{a}u_0$ 이다. 이 때 time constant $T = \frac{1}{a}$ 이며, 3T(sec)일 때 시스템의 95% 성능을 낼 수 있다!

+) a = 0 case

이 때 만약 a=0 이면 $x(t) = x_0 + bu_0\cdot t$ 이다. 이때 $t→\infin$ 하면(steady-state) x(t)값은 무한대로 증가하므로 stable할 수 없다.

+) a < 0 case

이 때 만약 a<0이면 $x(t)→-\frac{b}{a}e^{-at}$ 이고 $t→\infin$ 하면 x(t)값이 무한대로 exponentially 무한대로 증가하므로 stable 할 수 없다.

Concept : BIBO

Bounded Input-Bounded Output : stable을 구분하는 척도 (time constant는 반응성의 척도임)

Bounded : 어떤 신호 x(t)가 정해진 A보다 작음

$|x(t)| < A <\infin \ \ \ \ (\forall$ $t≥0)$

만약 어떤 input u(t)가 bounded 하다고 할 때 다음을 만족함.

• 어떤 수 N에 대하여 $|u(t)| < N \ \ \ \ (\forall t≥0)$
• 어떤 수 M에 대하여 $|x(t)| < M \ \ \ \ (\forall t≥0)$

→ input u(t), output x(t) 모두 bounded 하다.

⇒ $a≤0, x(t) →\infin$ 일때 1차 선형시스템은 not BIBO stable하다. $a>0, x(t) → X_{ss}$일 때 BIBO stable 하다.

State-Space Model

• State Variables : Dynamic System 에서 상태변수는 최대한 적은 변수로 상태를 정의하는 것이다.
• State Space Model : 1차 미분방정식들의 모임으로 표현되는 n차 linear ODE

State Space Model 예시

$y^{[3]} + 8\ddot{y} + 9\dot{y} + 7y = u$

Define

$x_1 = y\x_2 = \dot{y} \ x_3 = \ddot{y}$

Initial Condition

$y(0) = y_0\ \dot{y}(0) = \dot{y_0} \ \ddot{y}(0) = \ddot{y_0}$

$\dot{x_1} = x_2 \ \dot{x_2} = x_3 \ \dot{x_3} = -8x_3 - 9x_2 - 7x_1 + u$

행렬로 변환

$\begin{bmatrix}\dot{x_1}\ \dot{x_2} \ \dot{x_3} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0\ 0 & 0 & 1 \ -7 & -9 & -8 \end{bmatrix} \begin{bmatrix}x_1\ x_2 \ x_3 \end{bmatrix} + \begin{bmatrix}0\ 0 \ 1 \end{bmatrix} u$

x 앞의 상수 행렬은 A행렬, u앞의 상수 행렬은 B행렬

$y = \begin{bmatrix} 1 & 0 & 1\end{bmatrix}\begin{bmatrix}x_1\ x_2 \ x_3 \end{bmatrix}$

x앞에 붙은 행렬은 C행렬

따라서 First-Order Differential Equation 은 다음과 같이 표현할 수 있다.

$\dot{x} = Ax + Bu\y = Cx$

x(0)는 벡터 혹은 single valued 일 수 있다.

Generic nth-order ODE 는 다음과 같은 형태로 표현할 수 있다.

$\dot{x}(t) = Ax(t) + Bu(t)\y(t) = Cx(t) + Du(t) \ IC : x(0) = x_0$

1. y(t) : 미래 output을 예상한 것 : 추정값
2. x(t) : time = t 에서의 상태. input이 걸리는 동안의 모든 정보를 포함

→ State-Space Model 은 n차 미분방정식으로 표현 가능. n개의 서로 연결된 1차 미분방정식 집합체가 벡터로 표현 가능함.

State Space Model for RLC Circuit 예시

$LC\frac{d^2V_c}{dt^2} + RC\frac{dV_c}{dt} + V_c = V_i$

$\frac{d^2V_c}{dt^2} + \frac{R}{L}\frac{dV_c}{dt} + \frac{1}{LC}V_c = \frac{1}{LC}V_i$

$I.C = \begin{cases}V_c(0) =V_{c,0}\\dot{V_c}(0) =\frac{i_0}{c}\end{cases}$

Define

$x_1 = V_c \ x_2 = \dot{V_c}$

$\dot{x_1} = x_2 \ \dot{x_2} = \ddot{V_c} = -\frac{R}{L}x_2 - \frac{1}{LC}x_1 + \frac{1}{LC}V_i$

$\therefore \dot{x} = \begin{bmatrix}\dot{x_1}\ \dot{x_2}\end{bmatrix} = \begin{bmatrix}0 & 1\ -\frac{1}{LC} & -\frac{R}{L}\end{bmatrix}\begin{bmatrix}x_1\ x_2\end{bmatrix} + \begin{bmatrix}0\ \frac{1}{LC}\end{bmatrix}V_i\y = \begin{bmatrix}1 & 0\end{bmatrix}\begin{bmatrix}x_1\ x_2\end{bmatrix}$

Nonlinear Mathematical Models

선형 ODE 모델로 만들 수 있는 비선형 모델을 배움. 대부분의 모델은 비선형 term을 가지고 있고, linearizing 또는 trimming 하여 단순화함.

single input을 가지는 n차 미분방정식의 state-space 모델을 다음과 같이 표현한다.

$\dot{x} = f(x, u)\y = h(x, u) \ (i.c) \ \ \ \ x(0) = x_0$

Equilibrium Points

모든 상태 변수에 대하여 변화량이 없는 평형상태를 “Equilibrium Point”라고 한다.

$f(\bar{x}, \bar{u}) = 0$

1. $x(0) = \bar{x}$ : system initialization
2. $u(t) = \bar{u} \ \ \ \ \ \ \ \forall t≥0$

이때 solution x(t)는 다음을 만족하며 $\bar{x}$상태를 유지한다.

$x(t) = \bar{x}\ \ \ \ \ \ \ \forall t≥0$

Linearization

Non-linear System이 Equilibrium Point에 근접하게 작동한다면 선형 미분 방정식으로 예측이 가능하다! 이 과정에서 Jacobian Linearization 이 필요함.

Taylor Series Expansion

함수 f가 R→R 일 때, $\bar{x}$에 대하여 다음과 같이 표현할 수 있다.

$f(x) \approx f(\bar{x}) + \frac{df}{dx}(\bar{x})\cdot(x-\bar{x}) + Higher Order Tems$

상태변수가 1개인 비선형 시스템은 다음과 같이 표현할 수 있다.

$\dot{x} = f(x, u)$ (*1)

Assumption $(\bar{x}, \bar{u})$ 는 equilibrium point 이다 : $f(\bar{x}, \bar{u}) = 0$

• 이 시스템이 $x(0) = \bar{x}$ 에서 시작하고
• input $u(t) = \bar{u} \ \ \ \ \ \ \forall$ $t≥0$ $\cdots$ (input이 바뀌지 X)
• (*1)의 솔루션은 $x(t) = \bar{x} \ \ \ \ \ \forall t≥0$ 이다 $\cdots$ (초기조건에 머묾)

Question 만약 $x(0)$이 $\bar{x}$ 에 근접하게 접근하고, 입력 $u(t)$가 $\bar{u}$에 근접하게 접근한다면?

sol1) (*1)을 그냥 풂 → 비선형 시스템이라 복잡함ㅠㅠ

sol2) 선형미분방정식을 유도한다! → 비선형 미분방정식 (*1)의 근사치를 제공함!!!

Conclusion

$(\bar{x}, \bar{u})$ 에 근접한 어떤 점에서 다변수(multi-variabl) 테일러급수를 통해 비선형함수의 근사치를 계산할 수 있다.

$f(x, u) \approx f(\bar{x}, \bar{u}) + \frac{df}{dx}(\bar{x})\cdot(x-\bar{x})+\frac{df}{du}(\bar{u})\cdot(u-\bar{u})$

(뒤의 Higher Order Terms들은 복잡하므로 다 날림. 그럼에도 불구하고 근사치를 계산할 수 있다)

이 때, $(\bar{x}, \bar{u})$ 는 Equilibrium point 이므로 $f(\bar{x}, \bar{u})$=0이다.

$\therefore f(x, u) = \frac{df}{dx}(\bar{x})\cdot(x-\bar{x})+\frac{df}{du}(\bar{u})\cdot(u-\bar{u})$

$\therefore \dot{x} = [\frac{df}{dx}(\bar{x}, \bar{u})]\cdot(x-\bar{x})+[\frac{df}{du}(\bar{x}, \bar{u})]\cdot(u-\bar{u})$ (*2)

따라서 (*)식을 다음과 같이 단순화시킬 수 있다.

$A = \frac{df}{dx}(\bar{x}, \bar{u}) \ B = \frac{df}{du}(\bar{x}, \bar{u})$

$\delta_{x}(t) = x(t) - \bar{x} \ \delta_{u}(t) = u(t) - \bar{u}$

$\frac{d}{dt}(\delta_{x}(t)) = \dot{\delta}_{x}(t) = \frac{d}{dt}(x(t)-\bar{x})= \dot{x}(t) \ \ \ \ \cdots$ (*2) 에서 확장!

$\dot{\delta}_{x}(t) = \dot{x}(t) = A\delta_x(t) + B\delta_u(t)$ (*3)

→ Linear State-Space Model : 선형 상태공간 모델

3은 비선형 방정식 (1)을 근사 예측할 수 있게 한다. 단, $(\bar{x}, \bar{u})$에 근접해야한다는 조건이 있음

x(t)는 x(0)에서 시작되고 input(u)를 가지는 비선형모델 (*1)의 솔루션이다.

$\delta_{x}(t)$는 $\delta_{x}(0) = x(0) - \bar{x}$에서 시작하고 input $\delta_{u}(t) = u(t)-\bar{u}$를 가지는 선형모델인 (*3)의 솔루션이다.

Linear Solution은 Non-Linear Solution을 근사화해준다. 단, Equilibrium point 의 작은 오차범위에서 유효하다. $x(t) \approx \bar{x} + \delta_x(t)$

Generalization

n-state System일 때 Linear State Model을 얻기 위해 일반화함!

output equation을 다음과 같이 쓸 때 output 또한 linearization 가능함.

$\dot{x} = f(x, u) \ y = h(x, u)$

$\bar{y} = h(\bar{x}, \bar{u})$ 일때 $\delta_y(t) = y(t)-\bar{y}$ 이라고 하면, equilibrium output은 다음과 같이 근사화된다.

$\delta_y(t) \approx [\bigtriangledown_xh(\bar{x}, \bar{u})]\delta_x(t) + [\bigtriangledown_uh(\bar{x}, \bar{u})]\delta_u(t)$

$C = [\bigtriangledown_xh(\bar{x}, \bar{u})] \ D = [\bigtriangledown_uh(\bar{x}, \bar{u})]$

$\therefore \dot{\delta}{x}(t) = A\delta_x(t) + B\delta_u(t) \ \ \ \ \ \delta{y}(t) = C\delta_x(t) + D\delta_u(t$)

Transfer Function

n차 선형미분방정식을 Laplace Transform 을 이용하여 표현할 수 있다.

전달함수 G(s)는 선형미분방정식과 관련된 전달함수이며 미분방정식을 다르게 표현한 것이다.

예시) $6\ddot{y} + 9\dot{y} + 2y = 4\dot{u} + 8u$

$G(s) = \frac{4s + 8}{6s^2 + 9s + 2}$

Summary

Nonlinear ODE —(Jacobian : Linearization) —> Linear ODE —(Laplace Transform) —> Transfer Function

• Nonlinear ODE 는 Equilibrium Point 에 근접할 때 선형미분방정식으로 근사치를 예상할 수 있다.

What is Control and “Why it Matters”?

Control Domains

-Flight Control

• 양력 : 비행기의 무게와 반대되는 힘. 중력보다 커야 비행 가능
• 항력 : 비행기가 앞으로 나아가지 못하게 하는 힘. 추력과 반대되며 추력보다 작아야함. (ex : 유도항력, 마찰항력)
• 추력 : 앞으로 나아가는 힘. 비행기가 움직이게 하는 원동력. 높은 추력으로 속도를 높이고 날개에 빠른 공기유동력을 가진다.
• 중력 : 지구가 비행기를 끌어당기는 힘. 무게 자체와 연관되어 있음.

Take - off

• 에어포일 상부와 하부의 압력차에 의한 양력이 발생함.
• 날개에 흘러들어오는 공기와 에어포일 사이의 각을 받음각이라 하며, 압력차로 인해 양력이 발생함.
• 받으각을 너무 크게 하면 항력이 더 커질 수 있으며 공기는 날개 단면을 따라 흐르지 못하고 분리되어 흘러 실속(속도를 잃어버림)할 수 있음.
• 방향타와 승강타를 이용해 꼬리의 수직력을 조절함

→ 이륙 필수 조건 : 양력, 높은 받음각, Flap&Slap 사용

Landing : Spolier로 공기저항을 높임

-Autonomous Vehicle Control

• 승차감을 위한 샤시 컨트롤
• Handling Safety

-UAV(Uninhabited Aerial Systems) & Drones

Control Basics

Block Diagrams

• 시스템의 input, output을 블록으로 설명함.
• 블록에는 플랜트의 동역학을 포함하지만 구체적으로 표현하지는 않음.

OpenLoop

• desired 결과값을 계산함.
• uncertain 값(오르막, 바람 등) 에 대하여 피드백 불가
• 복잡한 시스템에서는 정확한 값을 가져올 수 없음.
• 예시 :

Close Loop/Feedback

• 현재 측정값을 반영하여 command 값을 계산해냄
• 그러나 trade off가 있음 : stability, speed of response, sensor noise rejection...
• 예시

Cruise Control System Block Diagram

Control Design

→ 공학에서 Design은 미적인 디자인보다는 ‘설계’ 의 의미를 훨씬 더 강하게 내포하고 있음.

Design Process

1. Model the System : using Differential Equations
2. Design the Control Algorithm : PID 등
3. Analyze and Simulate : 이론, 시뮬레이터 사용
4. Implement the controller and experiment
5. Iterate

• Model은 단지 “approximation”일 뿐 현실에서 시스템을 검증해야함.

  → Model은 incorrecties를 가지며 control system 설계를 위해서는 simplest model(essential dynamics)를 정의해야함

Primary Method for Constructing Dynamic Models

1. First Principles : 물리법칙(뉴턴의 운동 제 2법칙 F=ma)
2. Black Box : Experimental input/output data와 연관
3. Grey Box : 1+2, 모델 파라미터를 구하기 위해 1,2방법을 모두 사용

• Modeling 은 “domain-specific”한 과정이다. 도메인에 따라서 모델링 스텝이 다름. 그러나 최종적인 model, equation 형태는 비슷함!
  
  

Modeling Practice

Mechanical System

→ Dynamics of Mechanical System은 대부분 뉴턴의 법칙을 따른다.

1. Moving Mass

$F = ma =$ 추력 - 항력X속도

$m \dot{v}(t) = u(t) - bv(t)$

$\dot{v}(t) + \frac{b}{m}v(t) = u(t)$ : First Order ODE

→ 수학적으로 설명하기 좋은 형태로 변형함

• Linear Differencial Equation (Ordinary Differential Equation : ODE)

  : 시간에 따라 달라짐. v(t), u(t)에 대한 선형적인 의존성을 가짐.

• 시간 t에 대한 v(t)fmf dPcmrgkrl dnlgotjsms

  1) t=0에 대한 v가 정해져야 한다 → Inital Condition

  2) t=0~t=t 까지의 input을 알아야한다.

2. Mass-Spring-Damper

1) Linear(Hookean) Spring

2) Viscous Dampler

$F = k \cdot x$ (k = spring coefficient)

$F = c \dot x$ (c = damper coefficient)

3) Free Body Diagram for Mass & Block Diagram

$m \ddot{x} = -kx -c \dot x + u$

$\therefore \ddot{x} + \frac{c}{x}\dot x + \frac{k}{m}x = \frac{1}{m}u$ : 2nd Order ODE

$I.C = \begin{cases}x(0) = x_0\\dot{x}(0) = v_0\end{cases}$

(오른쪽 블록 다이어그램)

Electircal System

→ Passive Electrical Components : Resister, Capacitor, Inductor

1. Kirchoff’s Current Law : KCL

   임의의 접점에서 모든 전류의 합은 0이다.

   Positive(+) : 노드를 나가는 전류 : $i_3$

   Negative(-) : 노드로 들어오는 전류 : $i_1, i_2$

   $\therefore i_3-i_1-i_2 = 0$

2. Kirchoff’s Voltage Law (KVL)

   폐회로에서 모든 전압의 합은 0이다.

   Positive : voltage drop : $v_3$

   Negative : voltage rise : $v_1, v_2$

   $\therefore v_3-v_1-v_2 = 0$

1. RLC Circuit

   *단, 모든 요소가 이상적이라고 가정

$V_R = iR \ C \dot{V_c} = i \ L\frac{di}{dt} = V_L$

$i = C \frac{dV_c}{dt}\ V_R = R \cdot C\frac{dV_c}{dt}\ V_L = LC$

$\therefore LC \frac{d^2V_c}{dt^2} + RC\frac{dV_c}{dt} + V_c = V_i$

$I.C = \begin{cases}V_c(0) =V_{c,0}\\dot{V_c}(0) =\frac{i_0}{c}\end{cases}$

Aerodynamic Systems

→ 강체 뉴턴법칙(? Newton’s laws for the rigid body Dynamics)와 유체역학을 적용한다.

1. Lanchester Model for the Phugoid Dynamics

Assumption

1. 모든 에너지는 보존된다. (The Energy is Constant)

   $\frac{1}{2}m v_0^2 = \frac{1}{2}mv^2 + mgh$

   (inital kinetic E = kinetic E duing oscillation + potential E)

2. 양력은 $v^2$에 비례한다.(The lift force is proportional to $v^2$)

   $L = kv^2$

   k = standard aero notation

   $k = \frac{1}{2} \rho J C_l$ ($\rho$=공기밀도, J=단면적, $C_l$ = lift coefficient)

뉴턴의 제 2법칙에 의하여

$M\ddot{h} = L \cdot cos\theta - Mg$ (*)

1. 에 의하여 다음과 같이 쓸 수 있음

$v^2 = v_0^2 - 2gh$

ii. i. 에 의하여 다음과 같이 쓸 수 있음

$L = k v^2 = kv_0^2 - 2kgh$

Steady Flight 에서

L_0 = kv_0^2 = mg

$\therefore L=mg-2kgh$

*에 대입하면 다음과 같이 정의할 수 있다.

$M\ddot{h} = (Mg-2kgh)cos\theta - Mg$

+Assumption

pitch $\theta$ 는 매우 작음. ($cos\theta \approx 1$)

따라서 Lanchester Model로 Phugoid Motion 을 유발함.

$\ddot{h} = \frac{2kg}{M}h = 0$

→ Autonomous Model : 식의 우항이 0일 때(=input 이 0이다)

$I.C = \begin{cases}h(0) =h_0\\dot{h}(0) =r_0\end{cases}$

($r_0$ = reference speed)

+) Phugoid 모드는 낮은 frequency 로 약하게 진동하는 것을 뜻하며 이 때 속도 u, pitch attitude $\theta$, 높이 h를 가진다.

비행기가 진동주기의 상점에 있을 때 속도가 느려지고, 하점에 있을 때 속도가 빠르다. (에너지보존법칙)

Summary

시스템은 Linear ODE로 표현 가능하다.

일반적인 n차 ODE는 다음과 같은 형태이다.

일반화를 위한 Assumption

1. $a_n \neq0, b_n \neq 0$

2. m ≤ n

   m : input term이 가진 항의 개수

   n : 미분 term이 가지고 있는 좌측 항의 개수

Initial Condition(I.C)

$I.C = \begin{cases}y(0) =y_0^{[0]}\y^{[1]}(0) =y_0^{[1]}\ \vdots\ y^{[n-1]}(0) =y_0^{[n-1]}\ \end{cases}$

→ $y^{[k]} =$ y의 k번째 미분 term → $y^{k}(t) = \frac{d^ky}{dt}(t)$

• 다수의 사용자를 배려하는 코드를 작성해야함

  사용자의 편의성을 극대화해야함! 사용자의 실수 가능성을 제작자가 차단!

클래스 기본 문법

• 선언

    class 클래스이름
    {
    접근제어지시자:
        멤버변수;
        멤버함수 선언 및 정의
    };

• 생성자 : 사용자가 객체를 선언하면 자동으로 호출됨. 반환 자료형이 없고 호출 시기는 자동

    #include <iostream>
    using namespace std;
  
    class CTest{
    public :
        CTest(){//생성자
            m_nData = 10;
        }
  
        int m_nData;
  
        void PrintData(void){
            cout<<m_nData<<endl;
        }
    };
  
    int main(){
        CTest t; //생성자 호출
        t.PrintData();
  
        return 0;
    }
  
    /* 출력결과
    10
    */

     #include <iostream>
    using namespace std;
  
    class CTest{
    public :
        CTest(){//생성자
            cout<<"CTest() : 생성자 호출"<<endl;
            m_nData = 10;
        }
  
        int m_nData;
  
        void PrintData(void);
    };
  
    void CTest::PrintData(void){ //함수 선언, 정의 분리 가능
        cout<<m_nData<<endl;
    }
  
    int main(){
        cout<<"main() 시작"<<endl;
        CTest t;
        t.PrintData();
        cout<<"main() 끝"<<endl;
        return 0;
    }
    /* 출력결과
    main() 시작
    CTest() : 생성자 호출
    10
    main() 끝
    */

    #include <iostream>
    using namespace std;
  
    class CTest{
    public :
        CTest()
            : m_nData1(10), m_nData2(20)//초기화목록
        {
                    //초기화 목록에는 = 안됨
                    //멤버 변수가 참조자 형식이면 반드시 초기화목록 사용
        }
  
        int m_nData1;
        int m_nData2;
  
        void PrintData(void){
            cout<<m_nData1<<endl;
            cout<<m_nData2<<endl;
        }
    };
  
    int main(){
        CTest t;
        t.PrintData();
        return 0;
    }

• 접근제어 지시자

  • public : 모든 외부 접근 가능

  • protected : 차단. 단, 상속 관계-파생 클래스에서의 접근 허용

  • private : 차단. 클래스 선언 시 별도 기술하지 않으면 private으로 간주

    주의 : 생성자에 접근제어 지시자를 기술하지 않으면 컴파일 오류가 남. 일부러 private으로 선언하는 경우도 있긴 함

생성자와 소멸자

• 생성자 : constructor, 소멸자 : destructor

• 클래스와 이름이 같고 소멸자에는 앞에 ~이 붙음

• 생성자는 다중정의 가능, 소멸자는 안됨. 생성자 위임 지원(아래에 있음!)

• 디폴트생성자 : 클래스 제작자가 만들지 않아도 컴파일러가 알아서 만듦.(=default 붙여주기)

• 선언된 블록 범위가 끝나면 자동 소멸

    #include <iostream>
    using namespace std;
  
    class CTest{
    public:
        CTest(){
            cout<<"CTest::CTest()"<<endl;
        }
  
        ~CTest(){
            cout<<"CTest::~CTest()"<<endl;
        }
    };
  
    CTest outmain;
  
    int main(){
        cout<<"main begin"<<endl;
        CTest a;
        cout<<"main end"<<endl;
        return 0;
    }
    /* 출력결과
    CTest::CTest() - outmain
    main begin
    CTest::CTest() - a
    main end
    CTest::~CTest() - a
    CTest::~CTest() - outmain
    */

• 동적 객체의 생성과 소멸 : new, delete 로 가능. 생성 및 소멸 시점을 명시할 수 있음.

  단, 배열로 생성한 객체들은 반드시 배열로 삭제! delete [] (변수이름); → 메모리 릭 버그...

    #include <iostream>
    using namespace std;
  
    class CTest{
  
        int m_nData;
  
    public:
        CTest(){
            cout<<"CTest::CTest()"<<endl;
        }
  
        ~CTest(){
            cout<<"CTest::~CTest()"<<endl;
        }
    };
  
    int main(){
        cout<<"main begin"<<endl;
        CTest* pData = new CTest;
        cout<<"Test"<<endl;
        delete pData;
        cout<<"main end"<<endl;
        return 0;
    }

• 참조형식 멤버 초기화 : 참조자는 반드시 선언과 동시에 초기화! → 초기화 목록 이용

  주의. 참조형식이 아니라 매개변수 대입연산으로 초기화하게 되면 함수 내부의 자동 변수와 같으므로 함수가 반환될 때 매개변수가 소멸되어 이상한 값이 출력됨!

    #include <iostream>
    using namespace std;
  
    class CRefTest{
    public:
        CRefTest(int &rParam) : m_nData(rParam){};
        int GetData(void){return m_nData;};
  
    private:
        int &m_nData;
  
    };
  
    int main(){
        int a = 10;
        CRefTest t(a);
        cout<<t.GetData()<<endl;
  
        a = 20;
        cout<<t.GetData()<<endl;
  
        return 0;
    }
    /* 출력 결과
    10
    20
    */

• 생성자 다중정의 - 생성자 위임

    #include <iostream>
    using namespace std;
  
    class CMyPoint{
    public:
        CMyPoint(int x){
            cout<<"CMyPoint(int)"<<endl;
  
            if(x>100){
                x = 100;
            }
            m_x = 100;
        }
  
        CMyPoint(int x, int y)
        : CMyPoint(x) //CMypoint(int) call
        {
            cout<<"CMyPoint(int, int)"<<endl;
            cout<<x<<endl;
  
            if(y>200){
                y = 200;
            }
            m_y = 200;
        }
  
        void Print(){
            cout<<"X : "<<m_x<<endl;
            cout<<"Y : "<<m_y<<endl;
        }
  
    private:
        int m_x = 0;
        int m_y = 0;
    };
  
    int main(){
        CMyPoint ptBegin(110);
        ptBegin.Print();
  
        CMyPoint ptEnd(50, 250);
        ptEnd.Print();
    }
    /*출력결과
    CMyPoint(int)
    X : 100
    Y : 0
    CMyPoint(int)
    CMyPoint(int, int)
    50
    X : 100
    Y : 200
    */

메서드

메서드 : 클래스의 멤버 함수(메서드를 통해 멤버변수를 제어할 수 있으므로 ‘인터페이스 함수'라고도 불림)

static 반환자료형 클래스이름::함수이름(매개변수) const;
//static, const 생략 가능

• 정적 메서드는 this 포인터 접근이 불가능함.

• this 포인터 : 작성 중인 클래스의 실제 인스턴스에 대한 주소! : 명시를 통해 사용자 실수를 줄임

정적 멤버

• 전역함수는 불필요한 의존 관계를 만듦 → 정적 멤버!
• 정적 멤버 : 전역 멤버와 같으나 클래스 멤버로 들어와있어 소속이 확실함!
• 인스턴스 선언 없이 정적 멤버 함수 호출 가능하지만 this포인터는 사용할 수 없음.
• 정적 멤버 변수는 반드시 선언과 정의를 분리해야함.

#include <iostream>
using namespace std;

class CTest{
public:
    CTest(int nParam)
    :m_nData(nParam){
        m_nCount++;
    }
    int GetData(){
        return m_nData;
    };
    void ResetCount(){
        m_nCount = 0;
    };
    static int Getcount(){
        return m_nCount;
    };

private:
    int m_nData;
    static int m_nCount;    
};

int CTest::m_nCount = 0;

int main(){
    CTest a(5), b(10);
    cout<<a.Getcount()<<endl;
    b.ResetCount();

    cout<<CTest::Getcount()<<endl;
    return 0;
}
/*출력결과 : 전역변수처럼 사용됨.
2
0
*/

칙령

플로이드 와샬은 알고리즘만 잘 외우고 있거나 혹은 행렬을 그려보면 쉽다. 플로이드 와샬 알고리즘을 돌려서 제일 멀리 연결된 엣지수*d 를 하면 될 것 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, d;
const int MAX = 50;
int map[51][51] = {0, };

int main(){
    cin>>n;
    cin>>d;

    for(int i = 0; i<51; i++){
        for(int j = 0; j<51; j++){
            if(i!=j){
                map[i][j] = MAX;
            }
        }
    }

    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            char c;
            cin>>c;
            if(c == 'Y'){
                map[i][j] = 1;
            }
        }
    }

    for(int k = 1; k<=n; k++){
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=n; j++){
                if(map[i][j] > map[i][k] + map[k][j]){
                    map[i][j] = map[i][k] + map[k][j];
                }
            }
        }
    }

    int max_edge = 0;
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++){
            max_edge = max(max_edge, map[i][j]);
        }
    }

    if(max_edge == MAX){
        cout<<-1<<endl;
    }
    else{
        cout<<max_edge*d<<endl;
    }
}

만약에 범위 내에서 계속 탐색했는데 MAX값만 나온다면 그것은 모두가 연결되지 않았다는 뜻이므로 무한대를 뜻하는 -1 을 출력해주자. 오늘도 화이팅><

서강그라운드

각 정점에서 얻을 수 있는 아이템 개수에 대한 배열은 따로 만들어두고, 플로이드 와샬 알고리즘을 이용해 각 정점에 대한 최단 수색 거리를 구합니다. 그 다음, 모든 노드에서 시작하여 최대로 모을 수 있는 아이템의 수를 비교해서 출력해줍니다. 예제입력 1에 대한 배열은 다음 그림과 같습니다.

조심해야할 점은 착지하는 정점의 아이템도 먹어야하기 때문에 i=j 인 배열을 0으로 초기화해주어서 맨 아래 for문에서 착지지점 아이템도 셀 수 있도록 해주어야합니다!

#include <iostream>
#include <algorithm>
#define MAX 12345;
using namespace std;

int n, m, r;
int t[101] = {0, };
int map[101][101] = {0, };

int main(){
    cin>>n>>m>>r;

    for(int i = 0; i<101; i++){
        for(int j = 0; j<101; j++){
            if(i!=j){
                map[i][j] = MAX;
            }
        }
    }

    for(int i = 1; i<=n; i++){
        cin>>t[i];
    }

    for(int i = 0; i<r; i++){
        int a, b, l;
        cin>>a>>b>>l;
        map[a][b] = l;
        map[b][a] = l;
    }

    for(int k = 1; k<=n; k++){
        for(int i = 1; i<= n; i++){
            for(int j = 1; j<=n; j++){
                if(map[i][j] > map[i][k] + map[k][j]){
                    map[i][j] = map[i][k] + map[k][j];
                }
            }
        }
    }
    int max_item = 0;
    for(int i = 1; i<=n; i++){
        int temp = 0;
        for(int j = 1; j<=n; j++){
            if(map[i][j]<= m){
                temp = temp + t[j];
            }
        }
        max_item = max(max_item, temp);

    }
    cout<<max_item;
}

그럼 오늘도 화이팅><

Coursera 자율주행 전문화코스 첫번째 강좌 Introduction to self-driving cars 의 마지막 주차이자 수료 과제인 CARLA 프로그래밍을 위해 윈도우에 Carla를 설치해보겠습니다.

원래는 우분투에 설치해야되는데 저의 할아버지 우분투 노트북(중3~대3 까지 쓴ㅠㅠ)에서는 돌아가지 않을 것 같고 맥에서는 안된다길래 학교 실습실 윈도우에 깔아보려고 합니다. 알고보니 우리학교 실습실에는 리눅스가 센토스만 있고 우분투 깔아도 되냐고 물어보니까 안된다고 하더라고요...

그래서 시작한 윈도우에 CARLA설치하기!(그리고 수료하기!)

*구체적인 것은 CARLA setup for Windows 공식 문서를 참고해주세요!

준비하기

1. HW : 여러가지 스펙 요구사항이 있었지만 저에겐 어차피 실습실 컴퓨터밖에 답이 없었기 때문에 그냥 했습니다.

2. Software : CARLA 시뮬레이터 다운로드 받아서 압출 풀고 시작함

   • 윈도우7 64bit 이상

   • 2000~2002 방화벽 포트 접근 가능

   • OpenGL 3.3 이상, DirectX10 이상 → CARLA 바이너리 불러올 때 알아서 됨

   • Python : 3.6.x (***매우중요)

     실습실 컴이라 Python 깔려있는 줄 알고 넘어갔다가 다시 돌아옴...꼭 확인하세요!

       >python —version

       >python -m pip —version

     

    ```powershell
    > python -m pip install -r C:\(위치)\CarlaSimulator\requirements.txt--user
    ```
    ![](https://velog.velcdn.com/images/boing-86/post/ebac9cf6-ce19-4922-afab-3acec7e3dc6a/image.png)

깔아보자!

1. Default Map 으로 시뮬레이터를 로딩하기

    >CarlaUE4.exe -windowed -carla-no-networking

   ‘-windowed’ 는 전체화면모드 해제

   중간에 DirectX 를 깔지 물어보는데 깔아주시면 됩니다.

   

![](https://velog.velcdn.com/images/boing-86/post/74c8e77f-99f8-4bca-bd84-420a2167f18d/image.png)


![](https://velog.velcdn.com/images/boing-86/post/9ee420e3-dcfc-43a6-a3a5-f6a5f2b39ccb/image.png)


완료!

A,S,D,W 로 차량을 움직일 수 있고 Q로 기어 바꿈. P는 파일럿모드

1. Race Track Map 으로 시뮬레이터 로딩하기

Coursera 과제에 사용할 맵으로 로딩해봅시다.

>CarlaUE4.exe /Game/Maps/RaceTrack -windowed -carla-server -benchmark -fps=20

2. 과제 파일 수정하기!

여기서 waypoints 는 이미 txt파일로 만들어져있고 이것이 과제예시파일에서 callback 함수로 구현이 되어있다. 종방향, 횡방향 제어기만 설계하면 된다!

나는 2021년 창작자동차대회 자율주행부문에서 횡방향 제어 알고리즘을 구현했고 2022-1학기에 청강하는 시스템모델링제어에서 PID를 배웠으므로 이 두 개를 구현해보도록 하겠다(Coursera에서도 이론을 배웠다!!!). 스탠리는 차량 앞축을 기준으로, PID는 뒷축을 기준으로 에러값을 계산하며 lookahead distance 없이 가장 가까운 포인트를 기준으로 에러값을 계산하여 에러에 따라 휠을 더 많이 꺾는다. waypoints txt에 포함된 속도값이 22kph 수준이므로 purepursuit 으로도 충분히 정확한 추종이 가능할 것이라고 생각하여 purepursuit&PID 로 구현하였다.

#!/usr/bin/env python3

"""
2D Controller Class to be used for the CARLA waypoint follower demo.
"""

import cutils
import numpy as np
import math

class Controller2D(object):
    def __init__(self, waypoints):
        self.vars                = cutils.CUtils()
        self._current_x          = 0
        self._current_y          = 0
        self._current_yaw        = 0
        self._current_speed      = 0
        self._desired_speed      = 0
        self._current_frame      = 0
        self._current_timestamp  = 0
        self._start_control_loop = False
        self._set_throttle       = 0
        self._set_brake          = 0
        self._set_steer          = 0
        self._waypoints          = waypoints
        self._conv_rad_to_steer  = 180.0 / 70.0 / np.pi
        self._pi                 = np.pi
        self._2pi                = 2.0 * np.pi

    def update_values(self, x, y, yaw, speed, timestamp, frame):
        self._current_x         = x
        self._current_y         = y
        self._current_yaw       = yaw
        self._current_speed     = speed
        self._current_timestamp = timestamp
        self._current_frame     = frame
        if self._current_frame:
            self._start_control_loop = True

    def update_desired_speed(self):
        min_idx       = 0
        min_dist      = float("inf")
        desired_speed = 0
        for i in range(len(self._waypoints)):
            dist = np.linalg.norm(np.array([
                    self._waypoints[i][0] - self._current_x,
                    self._waypoints[i][1] - self._current_y]))
            if dist < min_dist:
                min_dist = dist
                min_idx = i
        if min_idx < len(self._waypoints)-1:
            desired_speed = self._waypoints[min_idx][2]
        else:
            desired_speed = self._waypoints[-1][2]
        self._desired_speed = desired_speed

    def update_waypoints(self, new_waypoints):
        self._waypoints = new_waypoints

    def get_commands(self):
        return self._set_throttle, self._set_steer, self._set_brake

    def set_throttle(self, input_throttle):
        # Clamp the throttle command to valid bounds
        throttle           = np.fmax(np.fmin(input_throttle, 1.0), 0.0)
        self._set_throttle = throttle

    def set_steer(self, input_steer_in_rad):
        # Covnert radians to [-1, 1]
        input_steer = self._conv_rad_to_steer * input_steer_in_rad

        # Clamp the steering command to valid bounds
        steer           = np.fmax(np.fmin(input_steer, 1.0), -1.0)
        self._set_steer = steer

    def set_brake(self, input_brake):
        # Clamp the steering command to valid bounds
        brake           = np.fmax(np.fmin(input_brake, 1.0), 0.0)
        self._set_brake = brake

    def update_controls(self):
        # RETRIEVE SIMULATOR FEEDBACK
        x = self._current_x #meter
        y = self._current_y #meter
        yaw = self._current_yaw #radian
        v = self._current_speed #m/s
        self.update_desired_speed()
        v_desired = self._desired_speed #m/s
        t = self._current_timestamp
        waypoints = self._waypoints #x, y, v
        throttle_output = 0 # 0~1
        steer_output = 0 #-1.22~1.22(rad)
        brake_output = 0 #0~1

        # MODULE 7: DECLARE USAGE VARIABLES HERE
        self.vars.create_var('v_prev', 0.0) #velocity
        self.vars.create_var('t_prev', 0.0) #dt = t_prev-t
        self.vars.create_var('e_prev', 0.0) #Error : v_desired-v
        self.vars.create_var('e_iprev', 0.0) #integral Error
        self.vars.create_var('o_tprev', 0.0) #throttle output
        self.vars.create_var('o_sprev', 0.0) #steer output

        # Skip the first frame to store previous values properly
        if self._start_control_loop:

            # MODULE 7: IMPLEMENTATION OF LONGITUDINAL CONTROLLER HERE
                        # PID Controller

            K_p = 1.0
            K_i = 0.1
            K_d = 0.01

            dt = t-self.vars.t_prev

            throttle_output = 0
            brake_output    = 0

            e_v = v_desired - v
            i_v = self.vars.e_iprev + e_v*dt
            d_v = (e_v - self.vars.e_prev) / dt

            accel = K_p * e_v + K_i*i_v + K_d * d_v

            if(accel >0):
                throttle_output = (np.tanh(accel) + 1)/2

                if(throttle_output - self.vars.o_tprev > 0.1):
                    throttle_output = self.vars.o_tprev + 0.1

            else:
                throttle_output = 0

            # MODULE 7: IMPLEMENTATION OF LATERAL CONTROLLER HERE
                        # PurePursuit

            steer_output = 0
            L = 2.7 #meter - Ford Mustang Wheelbase
            min_ld = 10 #meter
            K_pld = 0.8

            x_desired = x-L*np.cos(yaw)/2
            y_desired = y-L*np.sin(yaw)/2
            l_d = max(min_ld, v*K_pld)

            for i in waypoints:
                dist = np.sqrt((i[0] - x_desired)**2 + (i[1] - y_desired)**2)

                if(dist>l_d):
                    target = i
                    break
                else:
                    target = waypoints[0]

            alpha = math.atan2(target[1] - y_desired, target[0]-x_desired)-yaw
            delta = math.atan2(2*L*np.sin(alpha)/l_d)
            steer_output = delta

            # SET CONTROLS OUTPUT
            self.set_throttle(throttle_output)  # in percent (0 to 1)
            self.set_steer(steer_output)        # in rad (-1.22 to 1.22)
            self.set_brake(brake_output)        # in percent (0 to 1)

        self.vars.v_prev = v  # Store forward speed to be used in next step
        self.vars.t_prev = t
        self.vars.e_prev = v_desired-v
        self.vars.e_iprev = i_v
        self.vars.o_tprev = throttle_output
        self.vars.o_sprev = steer_output

이 코드를 저장하고 시뮬레이터를 실행시킨 다음 cmd창을 하나 더 열어서 module_7.py(waypoint 추종 및 제어 코드 launch) 를 실행시킨다!

3. 약간의 Error Note

• 처음에 StopIteration 을 만난다고 떠서 해당 파일로 들어가보았더니 센서값을 못받아오나 해서 학교 인프라팀에 전화해서 시뮬레이터에서 pygame 어쩌고로 접근하고 싶은데 방화벽 포트 20002002번을 열어달라고 했다. 학교에서는 외부에서 학교 컴퓨터에 접근할 때 말하는 그 방화벽이라 관련이 없다고 말해주셨다. 그래서 알고보니 파이썬 버전문제였다. 꼬옥 3.53.6으로 해야한다.

• 아래와 같은 import 문제(link...?). matplotlib 3.0.0을 깔아주어야 해결된다!

  

결론

상당히 잘 나온다. 속도를 22kph에서 25kph까지 올렸는데도 잘 된다. (잘된다 = 추종한 waypoints 저장하여 비교해보았을 때 100% 일치) 하지만 한 50kph이상 올려버리면 다이나믹모델이 달라지므로 스탠리나 MPC모델로 제어를 해야할 것 같다.

3월부터 시작한 Introductiont to Self-Driving Cars 강의를 수료하였다. 다음주부터는 상태 예측과 위치측위 강좌로 바로 들어간다...와아아아...와ㅏ...행복해... '실무->입문수업' 순서로 진행되었는데,

오히려 좋았다. 왜냐면 배우면서 '그 땐 노가다로 삼중 for문 돌려가면서 튜닝했는데, 역시 이론이 중요하다...'는 것을 깨달았기 때문이다. 그리고 그것에서 멈추지 않고 과제로 코딩하고 시뮬레이터도 돌려보았기 때문에 오히려 좋아...(ㅋㅋㅋ)

다음주부터 상태예측과 위치측위 강좌로 적장의 목을 베고... 돌아오겠다. 내일도 화이팅

디폴트 매개변수

C언어와 다른 점 : 함수 선언 시 디폴트 매개변수를 지정하여 실인수를 경우에 따라 생략 기술할 수 있다.

#include <iostream>
using namespace std;

int TestFunc(int nParam = 10){
    cout<<nParam<<endl;
}

int main(){
    TestFunc();
    TestFunc(20);
}

/*출력결과
10
20
*/

*주의

• 매개변수는 오른쪽부터 디폴트값을 지정해야함. 중간에 빼먹을 수 없음.

• 호출자함수가 피호출자 함수 매개변수의 실인수를 명시할 때 왼쪽부터 짝을 맞추어 적용하며 짝이 맞지 않는 매개변수는 디폴트값이 들어간다.

• 함수 원형을 수정할 때에는 디폴트 매개변수로 기존의 사용(호출)코드에 에러가 생기지 않도록 할 수 있다.

  ex) 아래 코드. 만약 Calc_modified()는 Calc()에 내용을 추가한 것이라고 가정(Calc는 없음!). nType을 디폴트 매개변수로 선언하지 않는다면 기존 코드는 에러가 뜰 것

  ㄴ C++은 객체지향함수이므로 제작자가 함수 사용자를 고려해 코드를 작성해야함.

#include <iostream>
using namespace std;

int Calc(int nWidth, int nHeight){
    return nWidth * nHeight;
}

//위의 함수를 아래와 같이 수정했다고 가정. 오버로딩 표현한 거 아님
int Calc(int nWidth, int nHeight, int nType = MYTYPE_A){
    return nWidth * nHeight + nType;
}

int main(){
    Calc(10,5); //기존 코드
    Calc_modified(10, 5, MYTYPE_A); // 수정 후 코드
}

• 구글 스타일 가이드에서는 사용자가 해당 함수 형태를 추측하기 어려움으로 모호성이 생겨날 가능성이 커서 필수를 제외하고는 디폴트 매개변수 사용을 지양함.
• 다형성을 지원하는 언어에서는 사용(Call) 주의!

함수 다중 정의

Overloading. 이름은 같지만 내용이 다른 것을 여러 개 정의할 수 있음(Name Mangling : 컴파일 단에서 오버로드한 함수 이름을 각각 시그니처 이름으로 바꿔서 컴파일함. 따라서 오버로드 지원가능)

C언어에서는 허용하지 않지만 C++은 다형성을 지원함.

다만 컴파일러에 의해 호출되는 함수가 결정되므로 모호성이 증가(여기에 디폴트 매개변수까지 쓰면 모호성 더 커짐) → 유지보수ㅠㅠ

ex) 주의 : 함수를 만든 제작자는 오류X, 사용자는 오류를 경험

#include <iostream>
using namespace std;

void TestFunc(int a){
    cout<<"TestFunc(int)"<<endl;
}

void TestFunc(int a, int b=10){
    cout<<"TestFunc(int, int)"<<endl;
}

int main(){
    TestFunc(5); //오류
}

따라서 템플릿 사용을 추천!

호출자에 의해서 타입이 정해지므로 모호성은 줄어들고 같은 일을 하는 코드가 여러번 등장X → 안정적!

#include <iostream>
using namespace std;

template <typename T>
T add(T a, T b){
    return a+b;
}

int main(){
    cout<<add(3, 4)<<endl;
    cout<<add(3.3, 5.5)<<endl;
}

/* 출력결과
7
8.8
*/

인라인 함수

매크로 함수와 함수의 장점을 모두 가진 함수

사용시 함수 앞에 ‘inline’을 추가

함수를 사용하면 내부적으로 여러 연산들로 인해 스택 메모리 사용이 증가함. 이를 극복하고자 매크로를 사용하지만 함수가 아니므로 논리적 오류를 발생시키고 매개변수 형식을 지정할 수 없음

다만 코드 길이가 일정 수준 이상이면 인라인 함수를 쓰지 않는 것이 좋음

Visual Studio 에서 최적화>인라인함수 확장>기본값 을 사용하면 인라인 함수로 적합한 함수는 모두 인라인 함수로 만들 수 있음

*강의자 추천 : <독하게 시작하는 C> 16장 전처리기 강의

네임스페이스

C++의 요소들을 한 범주나 소속으로 묶어주는 문법

namespace 예약어{} 로 사용한다.

전역 요소는 전역 네임스페이스 혹은 무소속이라고 생각할 수 있다.

#include <iostream>
using namespace std;

namespace Test{
    int g_nData = 100;

    void TestFunc(void){
        cout<<"Test::TestFunc()"<<endl;
    }
}

using namespace Test;

int main(){
    TestFunc();
    cout<<g_nData<<endl;
}
/* 출력결과
Test::TestFunc()
100
*/

네임스페이스 중첩 가능

같은 이름의 네임스페이스를 using 선언하면 함수가 오버로드 되어 모호해지고 오류가 난다!

식별자 검색 순서

식별자가 선언된 위치를 검색하는 순서

탐욕적 문제 해결 방법 탐욕적 선택을 하더라도 문제의 최적해를 구할 수 있고, 부분 문제의 최적해를 통해 전체 문제의 최적해를 찾을 수 있어야 그리디 알고리즘을 적용할 수 있다.

간단하게 문제를 풀어보자!

20044. Project Teams

문제 난이도 자체는 크지 않다. n개 팀으로 구성하며 인원은 2n명이다. 따라서 2명씩 n개팀으로 나눠주는데, 실력을 정렬해서 가장 못하는(ㅠㅠ)사람과 가장 잘하는 사람으로 팀을 짜주면 된다. 그리디보다는 뭔가 투포인터 느낌이었다. 정렬한 후 맨앞, 맨뒤에서 한칸씩 내려가면서 실력합의 최소를 찾아나간다.

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

using namespace std;

int n = 0;
vector <int> w;

int main(){

    cin>>n;
    int a;

    for(int i = 0; i<2*n; i++){
        cin>>a;
        w.push_back(a);
    }
    sort(w.begin(), w.end());

    a = 123456789;

    for(int i = 0; i<n; i++){
        a = min(a, w[i] + w[2*n-i-1]);
    }

    cout<<a<<endl;

    return 0;
}

신촌연합 알고리즘 학회 수업 과제로 나왔던 문제인데, 그 전까지는 C만 쓰다가 여기서 C++의 편리함을 알고 언어를 갈아타게 되었고 로봇개발까지 가게 되었다. 알고리즘 문제를 잘 풀지는 못해서 초급부터 차근차근 풀어가보려고 한다. 화이팅

사이클이 없는 direct 그래프에서 순서를 찾는 알고리즘은 위상정렬이다. 위상정렬에서는 싸이클이 없어야한다 n번 입력을 받는데 시간, 먼저 지어져야할 건물들, 막줄표시 로 입력이 들어온다. 예를 들어 입력이 10,1,2,3,-1 이라고 한다면 10, {1,2,3}, -1 이라고 보면 된다.

위상정렬을 돌면서 현재 건물과 그 다음 건물의 시간을 더해서 더 큰 수를 저장해주면 된다. 예제입력 1을 그림으로 정리하자면 다음과 같다.

만약 비교를 해서 저장해야 할지 이해가 가지 않는다면 다음 입력을 확인해보자! 2와 4를 이어주었다. 큐에는 2가 먼저 들어오기 때문에 4의 결과시간이 24로 저장된다. 그 다음 3번건물을 계산할 때에도 4와 연결되어 있기 때문에 건물4의 result가 18로 들어온다. 하지만 시작부터 18시간 후에도 건물2번이 지어져있지 않기 때문에 건물4는 완성될 수 없다. 따라서 비교하여 더 큰 결과를 저장해주어야 한다.

*입력해보세요! 예제입력2

5 10 -1 10 1 -1 4 1 -1 4 2 3 1 -1 3 3 -1

예제출력2

10 20 14 24 17

코드는 다음과 같다!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n;
int inDegree[501];
vector <int> v[501];
int btime[501];
int result[501] = {0, };

void topology_Sort(){
    queue <int> q;

    for(int i = 1; i<=n; i++){
        if(inDegree[i] == 0){
            q.push(i);
            result[i] = btime[i];
        }
    }

    for(int i = 1; i<=n; i++){

        if(q.empty()){
            //cycle 이 있음.
            break;
        }

        int x = q.front();
        q.pop();

        for(int i  = 0; i<v[x].size(); i++){
            int y = v[x][i];
            result[y] = max(result[y], result[x] + btime[y]);

            if(--inDegree[y] == 0){
                q.push(y);
            }
        }
    }
}
int main(){
    cin>>n;

    for(int i = 1; i<=n; i++){
        cin>>btime[i];

        while(true){
            int a;
            cin>>a;
            if(a == -1){
                break;
            }
            v[a].push_back(i);
            inDegree[i]++;
        }
    }

    topology_Sort();

    for(int i  = 1; i<=n; i++){
        cout<<result[i]<<endl;
    }
}

휴학생의 특권은 수업 생각 안하고 현장에서 새로운 경험을 할 수 있다는 것이다! 국제인공지능대전이 있다고 하여서 가보았다.

세상이 변하고 있다고 생각했는데 '정말 많이 변했다'는 것을 피부로 느낄 수 있었다. 특히 로우레벨 코딩 or 노코드 단으로 내리는 것이 트렌드인 것을 알았지만 가보니까 정말...레알이더라... 개발자로서 요구사항 분석이나 의사소통 등 대체불가능한 스킬을 많이 키워야겠다는 생각이 들었다. 자세한 자료나 제가 체험한 것을 보고 싶으시다면 AI EXPO 정리 링크를 확인해주세요!

나 : 거 대충 넘어갑시다

컴퓨터(백준) : 응 안돼 돌아가

빙산문제

이 문제는 함수 두 개가 필요하다.

1. 덩어리가 몇 개인지 확인하는 bfs 여기서는 얼음이 있는 구역을 확인하고 덩어리가 0개인지, 1개인지, 2개 이상인지 확인해야하기 때문에 bfs 호출하기 전에 얼음이 있는 구역만 들어가도록 조건문을 걸어줘야한다. 그리고 이 함수가 끝났을 때 i) 덩어리가 아예 없음 -> 한꺼번에 다 없어짐(녹을때까지 분리X) -> 0 출력 ii) 덩어리가 1개 -> 덜녹았구만 -> 계속 녹여! iii) 덩어리가 2개 이상 -> 몇 년 걸렸는지 출력

   다음과 같은 조건을 걸어줘야한다. i)에다가 연도를 출력하게 해가지고 맞왜틀만 한시간 하고 있었다... 만약 아직 ii)처럼 아직 덜녹았다면 다음 2번 bfs를 수행한다.

2. 한 칸에서 4방위를 돌면서 바다와 인접한 면이 몇 개인지 세고 그만큼 줄여주는 bfs 먼저 한 칸당 4방위를 돌면서 인접한 바닷면을 세어서 맵과 같은 크기의 배열에 저장해준다. 이후에 다 돌고 나면 맵에다가 빼주고 0보다 작아지면 0으로 넣어준다. 만약 이거를 나이브하게 생각해서 4방위를 돌면서 바로바로 빼주면 안된다! 마치 nn년 지난 후 처럼 되어버림...

1->2 를 반복하면서 두덩어리 이상 생길 때까지 걸린 시간을 출력해준다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

int n, m;
int years = 0;
int map[301][301] = {0, };
int tmp[301][301] = {0, };
bool visited[301][301] = {false,};
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
queue <pair<int, int>> q;


void bfs(int x, int y){
    q.push({x, y});
    visited[x][y] = true;

    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i<4; i++){
            int nx = cx + prow[i];
            int ny = cy + pcol[i];

            if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny]!=0){
                if(!visited[nx][ny]){
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

void oneyearlater(){

    for (int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            int sides = 0;
            if(map[i][j] != 0){
                for(int k = 0; k<4;k++){
                    int nx = i + prow[k];
                    int ny = j + pcol[k];

                    if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny] == 0){
                        sides++;
                    }
                    tmp[i][j] = sides;
                }
            }
        }
    }

    for (int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            int height = map[i][j] - tmp[i][j];
            if(height > 0){
                map[i][j] = height;
            }
            else{
                map[i][j] = 0;
            }
        }
    }
}

int main() {
    cin>>n>>m;

    for (int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            cin>>map[i][j];
        }
    }

    while(true){
        int cnt = 0;
        for (int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(!visited[i][j] && map[i][j]!=0){
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        if(cnt == 0){
            cout<<0;
            return 0;
        }

        if(cnt >= 2){
            cout<<years;
            return 0;
        }

        years++;
        oneyearlater();
        memset(visited, false, sizeof(visited));
        memset(tmp, 0, sizeof(tmp));
    }

}

Notion은 2021년 10월부터 사용하기 시작했고, 나의 생산성을 지수함수급으로 올려놓았다. 19학번이라 코로나로 인해 후배들이 있는데 없습니다 상태라서 물려줄 사람도 없고 그래서 블로그에 올리려고 한다.

개인적으로 최고의 교수님, 최고의 알고리즘 수업인 것 같다. 교수님 ㄹㅇ천재시고 짱이라고... 무려 java, c++ 실습으로 나눠서 동시에 2분반을 돌리신다고... 난이도가 극악이라고 해도 후배들이 꼭 다 들었으면 좋겠고 다른 학교 학생들에게도 추ㅊ추춫추춫.추축ㅊ추추천 하고 싶다.

아래 정리 노트는 숙명여자대학교 박영훈 교수님 알고리즘(c++) 수업을 정리한 내용입니다.

Chapter1. Start

Chapter2. Operation Cost

Chapter3. Divide and Conquer

Chapter5. Probabilistic Analysis and Randomized Algorithms

Chapter6. Sort

Chapter7. Medians and Order statistics

Chapter8. Hash

Chapter9. Dynamic Programming

한 번 행동에 동서남북으로 각 한 칸씩 이동하는 로봇이 있는데 N번 움직인다고 하자. 동서남북으로 이동할 확률을 입력하여 단순한 경로를 이동할 확률을 알아보자! 첨엔 이해가 잘 안됐는데 그럴 땐 그림을 그려보면 된다!

단순한 경로는 다음처럼 갔던 곳을 다시 가지 않는 경우이다. 어쩌면 그래프보다는 E-W, N-S 를 카운트해보는 것도 좋을 것 같다.

어쨋든 이것을 그래프로 생각하면 깊이우선탐색으로 각각 경로를 찾아서 확률을 누적합으로 구하고 한 번 다 돌았으면 모두 초기화해서 경로를 탐색하는 방법으로 하면 좋을 것 같다.

그림에서의 depth를 코드로는 변수 d 로 설정해주었고, 이동 횟수를 n으로 받았을 때 d는 n보다 작아야하며 같으면 그것이 종료 조건이 된다. 개발자는 코드로 말하는 거니까(from 굣님) 코드로 봅시다

#include <iostream>
#include <algorithm>
using namespace std;

bool visited[30][30] = {false, };
double prob[4];
int prow[4] = { 1, -1, 0, 0 };
int pcol[4] = { 0, 0, 1, -1 };
int n;
double ans = 0.0;

double dfs(int x, int y, int d){

    if(d == n){
        return 1.0;
    }

    double ans_prob = 0.0;

    visited[x][y] = true;

    for(int i = 0; i<4; i++){
        int nx = x + prow[i];
        int ny = y + pcol[i];

        if(!visited[nx][ny]){
            ans_prob += prob[i] * dfs(nx, ny, d+1);
        }
    }
    visited[x][y] = false;
    return ans_prob;
}


int main(void){
    cin>>n;
    for(int i = 0; i<4; i++){
        int num;
        cin>>num;
        prob[i] = num/100.0;
    }

    ans = dfs(15, 15, 0);
    cout.precision(10);
    cout<<fixed<<ans<<endl;

    return 0;
}

dfs 리턴 전에 false로 바꿔주어야지 안그러면 이미 간 곳이라고 생각하고 다른 경로를 탐색할 때 가지 않는다...이걸로 1시간 헤맴 그럼 내일도 화이팅

1012. 유기농배추

밭을 샅샅이 뒤지면서 배추가 심어져있는 좌표 중 방문하지 않은 노드로 dfs를 호출한다. 한 번 돌고 오면 배추가 심어진 동네(?)는 다 돌고 온 것이기 때문에 count++을 해준다.

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

bool visited[51][51];
int field[51][51];
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
int t, n, m, k;

void dfs(int x, int y){
    visited[x][y] = true;

    for(int i = 0; i<4; i++){
        int nx = x + prow[i];
        int ny = y + pcol[i];
        if(nx >= 0 && nx<=m && ny>=0 && ny<=n && field[nx][ny] == 1){
            if(!visited[nx][ny]){
                //cout<<nx<<" "<<ny<<endl;
                dfs(nx, ny);
            }
        }
    }
}

int main(){
    cin>>t;

    while(t--){
        cin>>m>>n>>k;
        int row, col;
        int count = 0;
        for(int i = 0; i<k; i++){
            cin>>row>>col;
            field[row][col] = 1;
        }

        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if((field[i][j] == 1) && !visited[i][j]){
                    count++;
                    dfs(i, j);
                }
                //cout<<"("<<i<<", "<<j<<")"<<endl;
            }
        }

        cout<<count<<endl;
        memset(visited, false, sizeof(visited));
        memset(field, 0, sizeof(field));
    }
}

추가로 예전에 풀었던 bfs 방식도 넣어주자! 이거 보면서 무서웠던 게 그 때나 지금이나 변수 이름 짓거나 시계방향으로 주변 탐색하는 건 그대로다... 비슷한 토마토 문제도 내 풀이 들어가서 봤는데 그때도 여전히 시계방향으로 돌았다. 처음부터 변수 이름 잘 짓는 습관을 들이는 게 좋은 것 같다!

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int field[51][51] = {0, };
bool c[51][51] = {0, };
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
queue <pair<int, int>> q;
int t, n, m, k;

void bfs(int x, int y){
    c[x][y] = 1;
    q.push({x, y});

    while(!q.empty()){
        int x1 = q.front().first;
        int y1 = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x2 = x1 + prow[i];
            int y2 = y1 + pcol[i];

            if (x2 >= 0 && x2 < m && y2 >= 0 && y2 < n && field[x2][y2] == 1 && c[x2][y2] == 0) {
                q.push({ x2, y2 });
                c[x2][y2] = 1;

            }
        }
    }
}

int main() {

  cin>>t;

  while(t--){
      cin>>m>>n>>k;
      int count = 0;
      memset(c,0,sizeof(c));
      memset(field,0,sizeof(field));

      for(int i = 0; i<k; i++){
          int x, y;
          cin>>x>>y;
          field[x][y] = 1;
      }

      for(int i = 0; i<m; i++){
          for(int j = 0; j<n; j++){
              if(field[i][j] == 1 && c[i][j] == 0){
                bfs(i, j);
                  count++;
              }
          }
      }
      cout<<count<<"\n";
  }
}