전체 글

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,..

페이지 교체 알고리즘

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 backing store에서 메모리로 적재를 하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올린다고 하더라도 메모리가 나중에는 가득 차게 되고 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다. 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 page-out을 해야 하고 그 빈 공간에 필요한 페이지가 page-in을 해야 한다. 여기서 어떤 페이지를 backing store로 page-out을 시킬 것인지에 대해서 고민을 하게 된다. page-out이 되는 페이지를 victim page라고 부르는데 기왕이면 수정이 되지 않는 페이지를 선택하려고 한다. 만약 수정이 된다면 메인 메모리에서 내보낼 ..

세그멘테이션 (Segmentation) 오류

운영 체제(OS)에서 세그멘테이션 오류는 프로그램이 올바르지 않은 메모리 영역에 접근하려고 할 때 발생하는 예외다. 예외 발생 시 운영 체제는 프로세스를 종료시키고 종종 코어 덤프를 생성한다. C/C++에서는 메모리 관리를 개발자가 수동으로 해야 하는 특성을 가지고 있기 때문에 주로 C/C++ 코드에서 자주 발생한다 . 발생하는 상황들 1. 함수 포인터를 초기화하지 않고 호출 void (*func_ptr)(); // 초기화되지 않은 함수 포인터 func_ptr(); // 초기화되지 않은 함수 포인터 호출로 인한 세그멘테이션 위반 발생 2. 배열 범위를 넘어서는 인덱스 사용 int arr[10]; arr[100] = 42; // 범위를 벗어난 인덱스 사용 3. 동적 메모리 할당 후 해제한 메모리에 접근 i..

세그멘테이션(Segmentation)이란? 세그멘테이션 vs 페이징

세그멘테이션이란? 페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하는 것을 의미한다. 반면, 세그멘테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하는 것을 의미한다. 세그멘테이션은 프로세스를 세그먼트(segment)의 집합으로 표현한다. 이때 세그먼트는 논리 단위로 아래와 같은 것들이 해당된다. main program procedure function method object stack local variable global variable etc... 프로세스를 code영역, data영역, stack영역 등으로 나누는 것 또한 세그멘테이션이라고 할 수 있다. 세그멘테이션 계산 세그멘테이션도 페이징과 비슷하게 세그먼트 테이블을 가지고 있다. 페이징과 비슷하게 논리주소가 ..

[C++] 문자열 입력 istream::getline()과 string의 getline()

1. std::istream::getline - cin.getline() 인자: s - C 형식 문자열을 저장할 배열을 가리키는 포인터 n - 저장할 문자의 최대 개수 (끝의 종료 널 문자를 포함한 값). 만약 입력 스트림의 최대 크기에 도달하여 입력이 중단되면 failbit 플래그가 설정된다. delim - 제한자로 이 문자에 도달시 추출이 중단다. 이 때 이 문자는 s에 기록되지는 않지만 스트림에서 사라지게 된다. 즉 istream을 상속받는 클래스에서 getline()함수를 사용할 수 있다. 콘솔에서 문자열을 입력받으려면 cin.getline()을, 파일으로부터 문자열을 가져오려면 파일입력스트림인 ifstream의 인스턴스에서 getline()을 호출하면 된다. #include #include //..

[실2] 2512 - 예산

#include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ using namespace std; int main() { FAST_IO(); int n, m; cin >> n; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); cin >> m; int s = 0, e = v[n - 1]; int res = 0; while (s = sum) { res = mid; s = mid + 1; } else e = mid - 1; } cout