C++

[골5] 1759 - 암호 만들기

#include #include #include using namespace std; using ll = long long; #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ vector v; int l, c; void DFS(int now, string str = "", int consonant = 0, int vowel = 0) { char ch = v[now]; str.push_back(ch); if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') vowel++; else consonant++; if (str.length(..

KMP (문자열 중 특정 패턴을 찾아내는 탐색) 알고리즘 C++ 구현

개념 KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트 포스 : Brute Force) "ABCDABCE"라는 문자열에서 "ABCE"라는 패턴을 찾는다고 해보자. 모든 문자열을 일일이 비교한 경우엔 아래와 같이 탐색을 진행할 것이다. 이처럼 모든 문자열을 비교하는 브루트 포스(Brute Force) 방식은 텍스트의 길이를 N, 찾고자 하는 패턴의 길이를 M이라고 했을 때 시간 복잡도가 O(NM)이다. 이는 매우 비효율적이다...

[C++] tuple (튜플) 사용법 & 예제

#1 튜플 초기화 tuple은 헤더에 정의되어 있다. 튜플의 선언 방식은 다음과 같다. tuple 키워드를 사용해 꺽쇠 안에 하나로 묶을 데이터타입을 나열한다. 데이터 타입을 나열한 꺽쇠를 닫아준 뒤 튜플의 이름을 작성하고 소괄호() 안에 tuple의 원소들을 데이터타입에 맞게 초기화한다. #include tuple t1(21, "Nov", 'M'); 혹은 make_tuple 함수를 이용해 선언과 초기화를 분리하는 방법도 있다. tuple t1; t1 = make_tuple(21, "Nov", 'M'); #2 튜플 원소 접근 tuple은 get함수를 사용해 원소에 접근한다. 꺽쇠 안에 접근할 원소의 인덱스를 넣어준뒤, () 소괄호 안에 접근할 튜플의 이름을 적어준다. #include #include #i..

[골3] 2473 - 세 용액

#include #include #include #include using namespace std; using ll = long long; #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ int main() { FAST_IO(); int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); ll tmp = ll(30e9); tuple res; for (int i = 0; i < n; i++) { int l = i + 1; int r = n - 1; while (l < r) { l..

[골3] 2623 - 음악프로그램

순서는 상관없으므로 예시 출력이랑 일치 안해도 된다. #include #include #include #include using namespace std; #define MAX 1001 vector graph; vector res; int degree[MAX]; int n, m; #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ void BFS() { queue q; for (int i = 1; i > n >> m; while (m--) { int cnt, cur; cin >> cnt >> cur; for (int i = 1; i > nxt; ..

[골4] 1647 - 도시 분할 계획

#include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ using namespace std; using IntPair = pair; using NodePair = pair; vector graph; int parent[100001]; int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a), b = Find(b); parent[a] = b; } bool IsCycle(int a,..

[실3] 10158 - 개미

#include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define x first #define y second int main() { FAST_IO(); int w, h, p, q, t; cin >> w >> h >> p >> q >> t; p += t; q += t; p %= (2 * w); q %= (2 * h); if (p > w) p = 2 * w - p; if (q > h) q = 2 * h - q; cout

[골3] 1005 - ACM Craft

#include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define MAX 1002 int main() { FAST_IO(); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; int time[MAX]; for (int i = 1; i > time[i]; vector adj[MAX]; queue q; int degree[MAX]{ 0 }; int res[MAX]{ 0 }; while (k-..

[C++] 문자열 찾기: string.find()

size_t find(const string& str, size_T pos = 0) const; str : 찾고자 하는 문자(열) pos: 찾기 시작하는 주솟값 ​ string.find 함수는 헤더 파일에 정의되어 있으며, 찾고자 하는 문자(열) str을 찾아준다. 그리고 str을 찾으면 해당 문자(열)이 위치한 주솟값을 반환하며, 찾지 못하면 string::npos를 반환한다. 예1. 찾는 문자(열)가 있으면 "Found"를 출력하고, 없으면 "Not found"를 출력한다. #include #include int main(void) { std::string word = "sweet new, sweet new"; std::string str; std::cout > str; int pos = 0; if ..

[C++] 파스칼의 삼각형 (Pascal's triangle)

수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것 위의 삼각형을 조합으로 그리면 아래와 같은 형태가 됨 #include using namespace std; int main() { int rows; cout > rows; cout