기말 고사 Chapter 3 분할 정복 알고리즘 - 선택 문제 -> 안 나올 것 같음. 손코딩으로 나올 수는 있지만.. 알고리즘 문제로는 안 나온다. - 최근접 점의 쌍 찾기 -> 프로그래밍으로 나올 것 같음. 손코딩 유력 Chapter 4 그리디 알고리즘 (그리디 알고리즘으로는 결과를 보이기. 그림 그리기 등으로 나올 것 같음.) - 동전 거스름돈 -> 다이나믹과의 차이는? - 부분 배낭 문제 - 집합 커버 문제 - 작업 스케줄링 -> 작업들을 주고, (빠른 시간 순으로) 머신이 몇 개 사용? 각 머신은 어떤 작업을 수행하는지 그 리스트는? - 허프만 압축 -> 허프만 압축을 위한 허프만 트리를 그리시오. 혹은 문자의 빈도수 주고, 각 문자의 허프만 코드 쓰기. Chapter 5 동적 계획 알고리즘 (..
Behavioral Design Patterns 특정 동작에 관련된 디자인 패턴이다. Chain of responsibility 요청을 받을 수 있는 종류가 한 가지가 아닐 경우에, A 요청 B 요청을 한 명이 다 처리하는 게 아니라 각각의 요청에 대해서 처리 담당이 있다면 쉬워질 것이다. 내가 처리할 수 있으면 처리하고, 처리할 수 없으면 다른 담당자에게 돌려주기. 그 담당자도 안 되면 그 다음 담당자에게 넘기기.(체인 구조) 온라인 쇼핑몰 사이트에서, 주문 전 구매자 정보를 검사할 필요가 있다. (고객의 정보가 다양할 뿐더러 그런 정보를 검사하려는데 검사를 한 번에 주어져서 한 번에 핸들링하려 하면 실수하게될 가능성이 있다.) 또한, 추가적인 정보의 종류가 늘어날 경우에는? 하나의 로직에서 검사하고 ..
Advanced Template and STL Template parameter 값에 디폴트 값을 주고 싶다! (주로 크기가 3인데 계속 인자로 3을 넣어주기 귀찮다!) Default template argument로 아무 인자도 안 주었을 때 default 값을 specialized 하게 된다. 주의할 점 : Type은 항상 일정하고, Size(정수를 담는 변수)만 변화할거야! 이럴 때 생기는 문제점. 인자를 넘기는 것을 생각할 때 인자의 위치를 가지고 생각하게 된다. 위치, 순서를 인식하여 파라미터와 인자가 매핑되는 것에서 오류가 생길 수 있다. 따라서, Default parameter는 뒤에 넣어지게 된다. Default parameter가 하나 있을 때, 그 인자 뒤로는 모두 Default인 것이..
DP Algorithm(동적 계획 알고리즘) Dynamic Programming 입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결한다. 분할 정복 알고리즘과 DP 전형적인 부분 문제들 사이의 관계 DP는 부분 문제들 사이에 의존적 관계가 존재한다. 작은 부분 문제의 해가 보다 큰 부분 문제를 해결하는데 사용하는 관계가 있다. 분할 정복 알고리즘은 부분 문제의 해를 중복 사용하지 않는다. 막대 자르기 문제 막대 길이는 n(양의 정수)이다. 막대는 길이가 양의 정수로 자를 수 있다. (n-1을 초과할 수는 없다.) 길이가 i인 막대의 판매 가격은 pi 이다. 길이가 n인 막대를 여러 개의 조각으로 잘라서 판매할 ..
Introduction to Template compile time : run time polymorphism 컴파일 타임과 런타임 폴리모피즘에 대하여 Generic Programming using template 템플릿을 이용하면 제네릭 프로그래밍을 사용할 수 있다. Function overloading 도 컴파일 타임 폴리모피즘이다. 두 함수를 정의한 상태에서 컴파일 타임 폴리모피즘으로 구체화되면 컴파일러가 해당 함수가 어떤 함수인지 Linking을 해준다. Resolution rule에 의해서 결정된다. 컴파일러에 의해서 결정. 템플릿도 마찬가지로 compile time polymorphism이다. 함수를 템플릿으로 정의했을 때, 타입 네임을 T로 사용할 수 있다. 재료들을 가지고 함수를 만들게 된..
STL: Standard Template Library 4가지로 분류가 된다. containers Functions Iterator Algorithms Sequence containers Container adapters Associative containers Sequence containers : Array 어레이는 길이가 고정되어 있다. C와는 다르게 자신의 길이를 알고 있다. C에서는 함수에 배열을 인자로 받게 될 때, 배열의 길이도 인자로 줬어야 했다. 하지만 C++은 그렇지 않다. 버퍼 오버플로우 : 배열 길이는 3인데 인덱스 3이나 4를 원할 때, 메모리 접근 오류 STL의 Array를 사용하면 안전하게 사용할 수 있다. Sequence containers : Vector 어레이는 길이가 고..
디자인 패턴이란? 디자인 패턴의 3가지 분류 싱글톤 이 객체가 딱 한 번만 생성하게 하고 싶을 때 하는 디자인 패턴. Ex) 게임을 총괄하는 매니저, 게임 보드라는 게 하나만 있으면 좋겠다 할 때, 항상 이미 만들어진 객체를 주고, 새롭게 만들지 않음. 이 클래스의 인스턴스가 하나만 만들어지도록 보장해야함. -> 클래스의 생성자를 private으로 만든다. 객체가 아무곳에서나 생성되게 하지 않는다. 그래도 아예 막아버리면 안 되고, 생성은 해야한다. 글로벌 액세스 포인트를 만들어서 객체 생성을 제어한다. Static 키워드를 이용한 멤버필드, 멤버펑션으로 생성자를 만든다. 생성자를 만들거나, 이미 있는 객체를 반환하거나 한다. java는 복사를 명시적으로 해야하지만, C++은 단순히 선언만 해도 복사가 ..
