728x90 반응형 2019/0518 동전 교환(거스름돈) 알고리즘 최소 갯수로 동전 교환하는 방법 전체 금액보다 작은 동전중에서 가장 큰 동전부터 차례차례 채워 나간다. 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드므로 그 전의 거스름돈에 1을 더하면 된다. dp[j] = min(dp[j],dp[j-coin[i]]+1); 이미 구해진 거스름돈이 더 적은 값을 가지고 있다면 현재의 값을 유지하면 된다. for i 2019. 5. 6. 최대 연속 부분수열의 합 연속된 원소를 더한 부분 수열의 최댓값을 구하는 문제 수의 합을 반복적으로 구한다. 이 때 합이 음수이면 그 다음 수부터 다시 시작한다. 합의 최댓값을 도출한다. -3 3 5 -3 -7 9 -2 10 -5 -2 -3 경우 음수이므로 반영안한다. 현재 합 : 0 합의 최댓값 : 0 3 경우 현재 합 : 3 합의 최댓값 : 3 5 경우 현재 합 : 8 합의 최댓값 : 8 -3 경우 현재 합 : 5 합의 최댓값 : 8 -7 경우 현재 합 : -2 -> 0 음수이므로 0으로 갱신 합의 최댓값 : 8 9 경우 현재 합 : 9 합의 최댓값 : 9 -2 경우 현재 합 : 7 합의 최댓값 : 9 10 경우 현재 합 : 17 합의 최댓값 : 17 -5 경우 현재 합 : 12 합의 최댓값 : 17 -2 경우 현재 합 : .. 2019. 5. 5. 최장 공통 부분 수열 최장 공통 부분 수열은 LCS라고 부른다. 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다. 수도코드 lcs(m,n) for i 2019. 5. 5. C++ 일반화 프로그래밍(generic programming) C++이 가지는 프로그래밍 언어로서의 특징 중 하나로 일반화 프로그래밍을 들 수 있다. 일반화 프로그래밍은 데이터를 중시하는 객체 지향 프로그래밍과는 달리 프로그램의 알고리즘에 그 중점을 둔다. 이러한 일반화 프로그래밍을 지원하는 C++의 대표적인 기능 중 하나가 템플릿이다. 템플릿(template) 매개변수의 타입에 따라 함수나 클래스를 생성하는 매커니즘 타입이 매개변수에 의해 표현되므로, 매개변수화 타입이라고도 불린다. 템플릿을 사용하면 타입마다 별도의 함수나 클래스를 만들지 않고, 여러 타입에서 동작할 수 있는 단 하나의 함수나 클래스를 작성하는 것이 가능하다. 함수 템플릿(function template) 함수의 일반화된 선언을 의미한다. 함.. 2019. 5. 5. 최장 증가 부분 수열 최장 증가 부분 수열(LIS) 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. O(n^2) 방법 for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } } } 매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값 +1을 업데이트하는 방식으로 처리를 한다면, N번을 확인하.. 2019. 5. 5. C++ 소멸자(desturctor) c++에서 생성자는 객체 멤버의 초기화뿐만 아니라, 객체를 사용하기 위한 외부 환경까지도 초기화하는 역할을 한다. 이러한 역할을 하는 멤버 함수를 소멸자(destructor)라고 한다. 소멸자는 객체의 수명이 끝나면 컴파일러에 의해 자동으로 호출되며, 사용이 끝난 객체를 정리해 준다. 상속(inheritance) 상속은 추상화, 캡슐화와 더불어 객체 지향 프로그래밍을 구성하는 중요한 특징 중 하나이다. 상속은 사용자에게 높은 수준의 코드 재활용성을 제공하며, 클래스 간의 계층적 관계를 구성함으로써 다형성의 문법적 토대를 마련한다. 클래스 상속(class inheritance) C++에서 클래스 상속이란 기존에 정의되어 있는 클래스의 모든 멤버 변수와 멤버 함수를 물려받아, 새.. 2019. 5. 4. C++ 생성자 멤버 변수의 초기화 클래스를 가지고 객체를 생성하면, 해당 객체는 메모리에 즉시 생성된다. 이 객체는 모든 멤버 변수를 초기화하기 전에는 사용할 수 없다. 객체의 멤버 변수는 사용자나 프로그램이 일반적인 초기화 방식으로 초기화 할 수 없다. 그 이유는, 객체의 멤버 중에는 private 멤버도 있으므로, 이러한 private 멤버에 직접 접근할 수 없기 때문이다. 따라서 private 멤버에 접근 할 수 있는 초기화만을 위한 public 함수가 필요하다. 이러한 초기화 함수는 객체가 생성된 후부터 사용되기 전까지 반드시 멤버의 초기화를 위해 호출되어야 한다. 객체의 생성과 동시에 멤버 변수를 초기화해주는 생성자(constructor)라는 멤버 함수를 제공한다. 클래스 생성자의 이름은 해당 클래스의.. 2019. 5. 4. 이전 1 2 3 다음 728x90 반응형
