C++
[골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
[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