전체 글

 (163)
일반 마스터 정리(Generalized Master theorem) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 일반 마스터 정리(generalized master theorem)는 고급 마스터 정리(advanced master theorem)와 확장 마스터 정리(extended master theorem)으로도 불린다. ㉠ 일반 마스터 정리는 여러 가지 형태가 있으며, 비교적 이해하기 쉬운 형태를 소개할 것이다. ② 일반 마스터 정리는 마스터 정리에서 발전된 형태로 재귀 문제를 좀 더 포괄적인 방법으로 설명한다. ㉠ 광범위한 분할 정복 알고리즘의 시간 복잡도를 구할 수 있다. ⓐ n은 문제의 크기를 말한다. ⓑ a는 재귀에서 생성되는 하위 문제의 크기다. ⓒ b는 재귀의 매 단계에서의 하위 문제 크기를 의미한다. ⓓ n/b는 문제의 크기에 대한 하위 문제..
마스터 정리(Master Theorem) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 마스터 정리(master theorem)는 복잡한 알고리즘(recursive algorithm)의 시간 복잡도를 구하기 위해 사용한다. ② 마스터 정리로 해결할 수 있는 알고리즘의 구조는 다음과 같은 꼴을 따른다. ㉠ a>=1, b>1 인 상수여야 한다. ㉡ f(n)이 점근적으로 양수 함수값을 가지는 함수여야 한다. ㉢ 설명의 편의를 위해 A항 B항이라고 칭하겠다. ③ A항은 상위 문제를 해결하기 위해 상위 문제(super problem)를 하위 문제(sub problems)로 분할하는 데 소요되는 시간 복잡도이다. ㉠ 상수 a는 재귀 함수가 호출하는 하위 재귀 함수의 숫자이다. ㉡ 하위 재귀 함수는 n/b의 크기로 분할된다. ㉢ 상위 문제의 1..
버블 정렬(Bubble sort)과 교환 정렬(Exchange sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 버블 정렬(bubble sort)과 교환 정렬은 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 중 하나이다. ㉠ 정렬의 가장 이상적인 상황에서의 시간 복잡도는 O(N)이다. ⓐ 모든 항목이 정렬되어 있을 경우 단순 탐색만 진행하면 되기 때문에 O(N)의 시간 복잡도를 갖는다. ㉡ 버블 정렬과 교환 정렬의 최악의 상황에서 시간 복잡도는 O(N^2)이다. ② 버블 정렬과 교환정렬의 기본적인 작동원리는 인접한 두 수를 비교해 위치를 바꾸는 것으로 동일하다. ㉠ 버블 정렬의 작동 원리는 다음과 같다. ⓐ 선택된 배열의 첫 번째 요소와 두 번째 요소를 비교한다. 만약 정렬되어 있지 않다면 둘의 위치를 바꾼다. ⓑ 인접한 다음 쌍으로 이동하고 배열의 끝에..
time_point
ctime
C++ - 라이브러리 chrono를 이용해 실행 시간 측정하기 ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① C++에서 시간을 측정하는 가장 일반적인 방법은 헤더 파일에 있는 함수를 활용하는 것이다. HTML 삽입 미리보기할 수 없는 소스 ㉠ chrono 헤더 파일을 사용하기 위해서는 네임스페이스를 chrono를 이용해야 한다. ② 시간을 측정하는 원리는 간단하다. 나중 시간에서 처음 시간의 차이가 구하고자 하는 시간이다. ㉠ st일 때의 시간과 ed일 때의 현재 시간을 now()를 이용해 측정할 수 있다. ⓐ now() 는 현재 시스템 시간에 대한 정보를 포함하고 있으며, time_point 객체로 반환한다. time_point hemahero.tistory.com ⓑ now()에는 chrono::system_clock:: now()와 high_res..
버퍼(Buffer) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 버퍼(buffer)는 데이터가 한 장소에서 다른 장소로 전송되는 동안 일시적으로 보관하는데 사용하는 임시 저장 공간이다. ㉠ 시스템의 다른 공간으로 데이터를 이동시킬 때 버퍼를 거쳐 감으로써 걸리는 시간을 줄이는 것으로 컴퓨터 성능을 높여준다. ㉡ 버퍼는 수신 장치 또는 응용 프로그램에서 데이터를 처리할 수 있을 때까지 데이터를 저장하는 데 사용된다. ② 버퍼는 다음의 상황에서 사용한다. ㉠ 입출력 버퍼링(Input/Output buffering) : 네트워크 통신이나 파일로부터 데이터가 들어올 때, 프로그램이 처리하기 전 버퍼를 거친다. ㉡ 그래픽 랜더링(graphics rendering) : 애니메이션 프레임을 화면에 출력하기 전에 버퍼를 거..
버퍼 플러시(Buffer flush)

티스토리툴바