본문 바로가기

전체 글

 (308)
[알고리즘] 동적 계획법(DP) - LIS(Longest Increasing Subsequence) 부분 수열은 일부(0개 이상) 숫자를 지우고 남은 수열이다. 즉 순서를 유지해야 한다. 순 증가 부분 수열(LIS)은 부분 수열 중 오름 차순의 형태를 띄는 수열이다. LIS의 최대 길이를 구해보자. int LIS(int pos) { //기저 사항 if(seq.size()-1==pos) return 1; //캐시 확인 if(cache[pos] != -1) return cache[pos]; ... LIS는 int를 반환한다. 이것은 순 증가 부분 수열의 길이다. 매개변수로 int pos를 받는데 LIS의 첫번째 원소의 위치다. seq는 대상이 되는 수열이고 pos가 seq의 마지막 원소일 경우 LIS의 길이는 1이기 때문에 이것을 기저 사항으로 둔다. 그리고 cache에 값이 저장되어 있으면 그 값을 반환..
[알고리즘] 동적 계획법(DP) - 조합 DP 문제를 풀기 시작하면서 막 시작하니 감이 잘 안 와서 루키스 알고리즘 강의를 보면서 DP 문제를 푸는 법을 정리해보려고 한다. n개중에 r개를 뽑는 경우의 수를 nCr이라고 할 때 nCr = n-1Cr-1 + n-1Cr 이다. 예시를 들어보겠다. 5개 중에 2개의 공을 뽑는다고 하자. 그리고 무작위 공 하나를 선택하면 공 4개가 남는다. 선택한 공을 뽑는다면 나머지 공 4개중 하나를 뽑을 것이고 선택한 공을 뽑지 않는다면 나머지 공 4개중 두 개를 뽑을 것이다. 그러므로 5C2 = 4C1 + 4C2이다. 이것을 이제 코드로 표현해보자. int combination(int n, int r) { if(r==0 || n==r) return 1; return combination(n-1,r-1) + com..
23.02.21 - 함수 객체, 임시 객체, 템플릿 함수 객체 class CPlus { public: int operator()(int a, int b) { return a + b; } }; int main() { CPlus plus; cout
23.02.20 - 캐스팅 연산자, 인라인 함수, 연산자 오버로딩 캐스팅 연산자 const_cast intiNumber = 10; const int*p = &iNumber; int*pTemp = const_cast(p); *pTemp = 20; cout
[알고리즘] 벨만 포드 알고리즘 다익스트라 알고리즘은 그래프에 음수 가중치가 있을 때 올바른 결과를 보장할 수 없다. 왜냐하면 항상 현재까지 가장 짧은 거리를 갖는 노드를 선택하는 그리디 알고리즘이기 때문이다. 게다가 음수 사이클이 존재할 경우 가중치가 계속 내려가기 때문에 무한히 사이클을 순환할 수 있다. 이를 보완하기 위해 시간복잡도는 조금 크지만 사용하는 것이 벨만 포드 알고리즘이다. https://yabmoons.tistory.com/365 [ 벨만포드 알고리즘 ] 개념과 구현방법 (C++) 이번 글에서는 벨만포드 알고리즘에 대해서 알아보자. 1. 벨만포드 알고리즘 ?? 그래프 알고리즘에서 '최소비용'을 구하는 대표적인 알고리즘으로는 '다익스트라 알고리즘', '벨만포드 알고리즘' yabmoons.tistory.com 벨만포드 알..
23.02.17 - 순수 가상 함수, 가상 소멸자, 캐스팅 연산자 순수 가상 함수 class CObj { public: virtual void Render() = 0; }; class CPlayer : public CObj { public: virtual void Render() { cout Intro(); } 자식은 부모 객체의 모든 것을 cppking.tistory.com 상속관계를 가진 클래스의 경우 부모 클래스의 소멸자에 virtual을 붙여주는게 좋다. 부모 타입의 포인터 변수에 자식 객체를 동적 할당하고 delete하면 부모 클래스의 소멸자만 호출된다. 이 때 부모 클래스의 소멸자를 virtual로 선언하면 자식 클래스의 소멸자가 호출된 후 부모 클래스의 소멸자가 호출된다. 캐스팅 연산자 C는 너무 친절해서 별 뚱딴지 같은 캐스팅도 다 해준다. 이러면 문제가..
23.02.16 - 정적 바인딩과 동적 바인딩, 가상 함수 정적 바인딩과 동적 바인딩은 OOP에서 사용하는 메소드 호출 방식이다. 정적 바인딩 컴파일 시간에 메서드 호출 대상 객체의 타입이 결정된다. 변수의 값에 따라 호출 대상이 달라지지 않고 빠르고 효율적이다. 동적 바인딩 실행 시간에 메서드 호출 대상 객체의 타입이 결정된다. 메서드 호출 시점에 변수에 할당된 객체의 실제 타입을 검사해 호출대상을 결정한다. 실행시간에 호출 대상이 변경될 수 있으므로 느리고 비효율적이다. 가상 함수 가상함수는 부모 클래스에서 정의되고 자식 클래스에서 재정의 될 수 있는 멤버 함수이다. 부모 클래스에서 virtual 키워드를 통해 정의 할 수 있으며 자식 클래스에서 재정의할 때 virtual 키워드는 선택이다. 이렇게 자식 클래스가 부모 클래스의 가상 함수를 재정의 하는 것을 ..
23.02.15 - extern, friend, 상속성 extern 외부 파일 어딘가에 전역 변수로 선언되어 있다는 뜻을 가진 키워드이다. //fileA.cpp int i = 42; // declaration and definition //fileB.cpp extern int i; // declaration only. same as i in FileA //fileC.cpp extern int i; // declaration only. same as i in FileA //fileD.cpp int i = 43; // LNK2005! 'i' already has a definition. extern int i = 43; // same error (extern is ignored on definitions) fileA에 전역변수 i가 선언되었으므로 다른 파일에서 ..

티스토리툴바