1. 다항식 롤링 해시란?다항식 롤링 해시는 문자열의 각 문자를 일정한 베이스(예: 131, 257 등) 를 이용해 하나의 정수로 변환하는 방식입니다.예를 들어, 문자열 s에 대해 해시값을 아래와 같이 계산할 수 있습니다.하지만 실제 구현에서는 오버플로우와 연산 효율을 고려하여 보통 누적 방식으로 계산합니다.코드로 살펴보기const int TABLE_SIZE = 100003; // 큰 소수를 사용하는 것이 좋습니다.int getHash(const string &s) { unsigned long long hash_val = 0; for (char c : s) { hash_val = hash_val * 131 + c; // 131은 베이스로 자주 사용되는 소수입니다. } ..
C++ 템플릿과 STL: 핵심 개념 정리📌 템플릿(Template)이란?템플릿은 C++에서 일반화 프로그래밍을 구현하는 핵심 도구입니다.함수나 클래스를 데이터 타입에 독립적으로 설계할 수 있게 해주며,동일한 로직을 다양한 타입에 재사용할 수 있게 합니다.🛠 템플릿의 핵심 특징타입 추상화: typename T로 타입을 매개변수화하여 코드 재사용성 ↑컴파일 시 인스턴스화: 실제 사용 시점에 구체적인 타입으로 생성됨📝 템플릿 예시1. 함수 템플릿#include using namespace std;template T myMax(T a, T b) { return (a > b) ? a : b;}int main() { cout 동작 원리: 호출 시 전달된 인자의 타입에 따라 T가 int, double..
중복 부분 문제 (Overlapping Subproblems):동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.최적 부분 구조 (Optimal Substructure):최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전..
#동적 계획법(DP)이란? DP의 두 가지 핵심 특성중복되는 부분 문제(Overlapping Subproblems):동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.최적 부분 구조(Optimal Substructure):최적 ..
1) substr 함수substr 함수는 문자열의 특정 부분을 잘라내는 데 사용됩니다.기본 사용법cpp #include #include using namespace std;int main() { string s = "0123456789"; string subs1 = s.substr(2, 5); // subs1 = "23456" cout 시작 위치와 길이를 지정하여 문자열을 자릅니다.시작 위치만 지정하면 해당 위치부터 끝까지 문자열을 자릅니다.아무 것도 지정하지 않으면 문자열 전체를 복사합니다.find 함수와 함께 사용하기#include #include using namespace std;int main() { string s = "0123456789"; string subs1 ..
https://www.acmicpc.net/problem/10951 cin.eof() 를 사용 주요 사항입력 시도 후에 확인 가능: cin.eof()는 입력 시도가 실패한 후에만 의미가 있습니다. 즉, cin >> variable과 같은 입력 시도가 먼저 이루어져야 합니다. 만약 입력 시도가 실패하고 그 이유가 파일의 끝에 도달했기 때문이라면, 그때 cin.eof()는 참이 됩니다.eof 플래그: cin.eof()가 참이라는 것은 스트림이 파일의 끝에 도달했음을 의미합니다. 하지만 파일 끝에 도달했다고 해서 바로 cin.eof()가 참이 되지는 않습니다. 먼저 입력 시도가 이루어져야 하고, 그 시도가 파일 끝에 도달했음을 감지해야 합니다. #include #include using namespace s..
