반응형 C++19 이진 탐색(Binary Search) 이진 탐색(Binary Search) 어떤 decision problem의 답이 단조성(monotonicity)를 띌 때, 정답을 포함하는 구간의 크기를 절반씩 줄여가며 query 횟수를 최대 O(logN)회로 제한할 수 있다. mid보다 찾으려는 수가 작다면 mid의 오른쪽 원소들을 볼 필요가 없을 것이고, mid보다 찾으려는 수가 크다면 mid의 왼쪽 원소들도 볼 필요가 없을 것이다. divide-and-conquer 방식으로 접근해보자. Devide arr[1..N]가 arr[1..mid]와 arr[mid..N]으로 divide. Conquer A[mid] = x : return mid A[mid] < x : select A[mid + 1..N] for the next iteration. A[mid.. 2024. 3. 26. 문자열 압축 문제 문자열 압축 문제 #include #include #include using namespace std; void InsertionSort(char* arr, int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) // = 1); cout 2024. 3. 26. 6-6. 메모리 동적 할당 (Dynamic Memory Allocation) 프로그램에 메모리가 할당되는 것은 세가지 종류로 나뉜다. 정적 메모리 할당 :한번 만들면 프로그램이 끝날 때까지 계속 메모리를 갖고 있는 것들. 자동 메모리 할당 :변수를 선언하거나 정적 배열을 선언했을 때 블럭 밖으로 나가면 사라지고 다시 메모리가 할당되는것. 동적 메모리 할당 : 메모리의 낭비를 최소화하기 위해서 프로그램의 실행중(runtime)에 사용할 메모리 공간을 할당하는 것. #include using namespace std; int main() { int arr[10000000]; return 0; } [1] 53110 segmentation fault "/Users/sunho/Desktop/C++workspaces/TBCppStudy/"main 1000만개의 정수형 배열을 생성하고 실행하.. 2024. 2. 20. 6-5. 문자열 스타일의 심볼릭 상수 (기호적 상수) 기호적 상수 (Symbolic Constat) 기호적 상수란 특정 상수에 변수처럼 이름을 부여한 것이다. 프로그래밍의 편의성과 소스 코드의 가독성을 높이는 역할을 한다. #include using namespace std; const char *getHello() // return type으로도 사용 가능. { return "Hello"; } int main() { const char *name = "Olivia"; const char *name2 = "Olivia"; const char *name3 = getHello(); cout 2024. 2. 20. 6-4. 포인터 연산, 배열 인덱싱 포인터 연산 #include using namespace std; int main() { int value = 7; int *ptr = &value; cout 2024. 2. 20. 6-3. 포인터와 정적 배열 포인터와 정적 배열의 관계 포인터와 정적 배열의 관계를 이해하는 것은 이후 메모리 동적할당, 동적배열 등을 이해할 때 중요한 기본이 된다. 배열은 포인터로 다 접근할 수 있고 포인터와 배열은 같다. #include using namespace std; int main() { int arr[5] = { 4, 3, 1, 5, 6 }; cout 2024. 2. 18. 이전 1 2 3 4 다음 반응형
