본문 바로가기

전체 글

[C++] Header File 헤더파일에 들어갈 내용 1. 전역변수, extern keyword사용 2. 함수 프로토타입 3. define을 통한 식별자 및 매크로 4. 클래스 선언(함수 프로토타입 포함) 다른 C파일에 바디를 정의! 더보기
[Algorithm] Greedy Algorithm 욕심쟁이 기법 단계별로 연속된 선택을 함으로써 문제에 대한 해 백터(solution vector)를 구해나간다. 또한 각 단계별 선택은 전체적으로 최적인(Globally optimal) 선택을 하는 것이 아니라, 정해진 어떠한 선택 기준에 의해 그 단계에서 가장 최선인 선택, 즉 국지적으로 최적인(Locally optimal) 선택을 하는 것이다. 동전 교환 문제 단순 반복문 사용하여 동전의 개수를 최소화 하는 문제 가장 액수가 큰 동전을 차감하는 반복문을 사용한다. 테이프 장치 최적 공간 배정 문제 모든 프로그램에 대한 평균 검색 시간을 최소화하는 프로그램의 저장 순서를 결정하는 문제 가장 용량이 작은 프로그램을 순차적으로 할당한다. 분수 배낭 문제 각 물건의 무게를 Xi라고 할 때, Xi의 값이 0또.. 더보기
[Data Structure] Union-Find 유니온 파인드 그래프 알고리즘의 일종으로, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 이는 다른 말로 서로소 집합 혹은 Disjoint-Set이라 부른다. 즉, 유니온 파인드 연산은 그래프에서 특정 두 노드가 서로 연결되어 있는지 아니면 연결되지 않았는지 판별하기 위한 알고리즘이다. 유니온 알고리즘은 기본적으로 배열을 이용한다. 각각의 노드들은 배열에 자기 자신의 값을 가지고 있다. 이상태에서 노드는 단절된 상태이다. 만일, 123과 67을 연결하는 간선을 추가하고 싶다면, 2번 배열은 1번에 연결되므로 값을 1로 변경, 3번 배열은 값 2번 배열에 연결되므로 값을 2로 변경한다. 6과 7도 마찬가지로 이를 시행한다. 위 처럼 여러 노드를 연결하여 그래프를 구성하는 방법도 위와 동일하다. .. 더보기
[Algorithm] Divide & Conquer 분할정복 주어진 문제를 크기가 작은 여러개의 부분문제로 분할(Divide)하여 부분 문제를 정복(Conquer)한 후에 그 해들을 결합(Combine), 원래 문제에 대한 해를 구하는 재귀방식의 알고리즘 주로 재귀적인 특성을 갖춘 경우가 많다. 알고리즘이 재귀 호출에 의한 경우 그 알고리즘의 수행 시간은 순환 방정식에 의해 표현 가능하다. 가령, T(n)을 입력 크기가 n인 문제에 대한 시간 복잡도 함수라 가정하자. 만일, 문제 크기가 1일 때, 직접 해를 구할 수 있다면, 그때의 시간 복잡도 함수는 C(상수)로 표현이 가능할 것이다. 또한 어떤 문제가 크기 n/b인 a개의 부분문제들로 분할된다고 가정하자. 만약 문제를 분할하는데 d(n)의 시간이 걸리고, 부분 문제들의 해를 결합하여 원래의 문제의 해를.. 더보기
[C++] Exception 예외처리 if를 사용하면 쉽겠지만, C++에는 별도의 예외처리 메커니즘이 존재한다. try: 예외를 발견 catch: 예외를 잡기 throw: 예외를 던지기 try 블록은 예외발생에 대한 검사의 범위를 지정할 때 사용한다. 즉, try 블럭 내에서 예외가 발생하면 C++의 예외처리 메커니즘에 의해 처리된다. catch 블록은 try에서 발생한 예외를 처리하는 코드가 담기는 영역으로, 형태가 반환형이 없는 함수와 유사하다. catch 블록은 try블록 뒤에 이어서 등장하며, try에서 발생한 예외는 이곳 catch에서 처리된다. 즉, try와 catch는 하나의 문장이다. 만일 catch의 매개변수로 catch(...)을 한다면 전달되는 모든 예외를 받겠다는 뜻이다. throw는 예외 발생 시 발생을 알린.. 더보기
[C++] Template T T는 자료형을 결정짓지 않는담는 뜻이다. template ; template ; 둘 이상의 형에 대해 템플릿 선언을 위해서는 다음과 같이 하면 된다. template ; 템플릿 함수 간에는 오버로딩 또한 가능하며, 일반함수와 템플릿 함수간의 오버로딩도 가능하다. 함수 템플릿의 특수화(Specialization) 상황에 따라 템플릿 함수의 구성방법에 예외를 두는 경우를 말한다. 즉, 특정 매개변수에 대해서는 별도처리가 필요한 경우 사용한다. 템플릿 함수의 경우, 명시적 특수화만이 존재한다. template T max(T a, T b){ return (a > b ? a : b); } template double max(double a, double b) { return (a > b ? a : b); } .. 더보기
[C++] Operator Overloading part.2 유도 클래스의 대입 연산자에는 아무런 명시를 하지 않으면, 기초 클래스의 대입 연산자가 호출되지 않는다. 유도 클래스의 대입 연산자 정의에서, 명시적으로 기초 클래스의 대입 연산자 호출문을 삽입하지 않으면, 기초 클래스의 대입 연산자는 호출되지 않아서, 기초 클래스의 멤버변수는 멤버 대 멤버의 복사 대상에서 제외된다. class First { private: int num1, num2; public: ... First& operator=(const First& ref) { num1 = ref.num1; num2 = ref.num2; return *this; } ... } class Second : public First { private: int num3, num4; Second& operator=(co.. 더보기
Old... 더보기

티스토리툴바