C++

[C++] STL container 시간 복잡도 및 특징 비교

※용어 설명※ amortized : 분할 상환하다는 뜻을 가지고 있는 이 단어는, 쉽게 설명하자면 최악의 경우는 더 높은 값의 시간 복잡도를 가질 수 있지만, 대체적으로는~ 으로 생각하면 될 것 같다. 점근적 분석(Asymptotic analysis)으로 보면 O(n)이 나오는 경우에, 분할상환분석(Amortized Analysis)으로 보면 O(1)이 나오는 경우도 있기 때문이다. ​ red-black tree: 레드블랙트리. Balanced Binary-Search Tree로 이루어진 구조. [출처] C++ STL container 시간 복잡도 및 특징 비교.|작성자 Chan

[C++] Dynamic Programming (동적계획법) / Top-Down (탑다운)과 Bottom-Up (바텀업) 방식

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 조건을 만족해야 사용할 수 있다. 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결 중복 부분 문제 - 동일..

[C++] 이분 탐색 (Binary Search)

이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스 int h..

C++ MST 크루스칼 + 프림 알고리즘 코드

이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com) 정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음. 입력 데이터 From 1 To 2 Value 2 Edge형 구조체에 담음, int from, to, val; 9 1 2 2 1 4 1 1 5 4 2 4 3 2 3 3 2 6 7 3 6 8 4 3 5 5 4 9 0 0 0 크루스칼 알고리즘 핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결. #include #include #include using namespace std;..

[C++] 문자열 (string) 함수 모음

length() 메소드와 size() 메소드 length() 메소드는 문자열의 길이를 반환하는 메소드다. size() 메소드도 length() 메소드와 언제나 같은 값을 반환하지만, 그 의미는 약간 다르다. length() 메소드는 문자열의 길이를 나타내지만, size() 메소드는 해당 string 객체가 메모리에서 실제 사용하고 있는 크기를 나타낸다. string str1; string str2 = "C++ Programming"; cout

[C++] Buffer Overflow (버퍼 오버플로우) 예시

String Buffer Overflow 20byte의 buf를 할당하고 std::cin 함수를 통해 문자열을 입력받는다. 하지만 여기서도 입력한 문자열의 길이를 검사하는 부분이 없어서 20byte 이상의 문자열을 입력한다면 버퍼오버플로우가 발생할 수 있다. #include using namespace std; int main() { char buf[20]; cin >> buf; // string 제외 입력에 따라 자동 할당됨. } Container Overflow f 함수 부분이다. vector v를 src 매개변수로 받는다. std::vector dest(5) 7행에서 기본값(0)으로 초기화 된 5개의 원소를 가지는 vector dest를 생성한다. std::copy(src.begin(), src.e..

[C++] 디버그 모드에서 변수의 메모리 차지 공간

int64의 크기는 8바이트이고 로컬변수 선언시 스택 메모리에 8바이트씩 차지하게 된다. 8바이트 크기의 변수 3개를 선언 후 메모리 주소를 확인해보자. int64 n1 = 1; int64 n2 = 2; int64 n3 = 3; cout

[C/C++] 메모리 오류에 대하여

1. C/C++에서 메모리 오류의 종류 일단 메모리 공간에 따라 크게 Heap Memory 에러와 Stack (local variables) Memory 에러가 있다. Heap 메모리 영역에서 발생가능한 에러는 이미 해제된 메모리 다시 해제 할때 할당된적도 없는 메모리 해제 할라고 할때 이미 해제된 메모리 영역에 뭔가 데이터를 쓰려고 할때 할당된 적이 없는 메모리에 뭔가 데이터를 쓰려고 할때 메모리 할당 에러 동적으로 할당된 메모리 배열에서 초과된 index의 위치를 읽거나 쓰려고 할때 1,2 번과 3,4번을 묶어서 볼 수 있는데 해제시에 발생하는 문제 vs 데이터 입력시 발생하는 문제로 볼 수 있다. 스택 메모리 영역에서 발생가능한 에러들로는 정적 배열에서 초과된 index의 위치를 읽거나 쓰려고 할때..

[C++] cout 소수점 n자리까지 표시하기

일반적으로 아무 설정 없이 소수점을 표시하면 #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); double x = 3.333333333; cout

[골5] 2166 - 다각형의 면적

#include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #define x first #define y second using namespace std; using dp = pair; double Calculate(double x1, double x2, double x3, double y1, double y2, double y3) { double res = x1 * y2 + x2 * y3 + x3 * y1; res -= x2 * y1 + x3 * y2 + x1 * y3; return res / 2; } int main() { FAST_IO(); int ..