합병 정렬 (Merge Sort) 입력값을 $1/2$로 분할하여 부분문제 크기를 감소시키는 분할 정복 알고리즘이다. N개의 숫자의 배열을 N/2개씩 분할하고 재귀적 합병 정렬 후, 2개의 정렬된 부분을 합병하여 정렬한다. 즉, 합병 과정이 문제를 정복하는 것이다. 시간복잡도 합병 정렬은 분할 후 합병이 일어난다. 먼저 분할은 배열을 더이상 나눌서 없을때까지 2개의 배열로 나누는 재귀함수를 호출하는 것으로 O(1)의 시간이 걸린다. 이후 합병으로 넘어가면 2개의 정렬된 배열 A(크기 m개)와 B(크기n개)를 받으면 최대 비교 횟수는 (m+n-1)번이다. 합병시 두개의 숫자를 한번씩 비교할때, 더 작은 수가 결과 배열인 C에 저장된다. 따라서 배열 C는 A와 B의 모든 수(m+n)의 숫자들이 저장되나, 가장..
분할 정복 알고리즘 (Divide-and-Conquer Algorithm) 주어진 문제의 입력을 분할하여 부분문제(subproblem)로 만들어 해결하는 방식 대부분 분할 정복 알고리즘은 단순 분할이 아닌, 분할된 부분문제들로 부분해를 찾아야 한다. 예시 문제로 크기가 n인 입력값이 있다고 가정하고 n을 3개로 분할한다 할때 각 부분문제의 크기가 $$n/2$$라고 하면 각 입력 크기의 반은 n/2라고 할수있다. 이제 입력 크기가 1이 되어 더 이상 분할할 수 없는 k번째까지 분할을 한다면, $$n$$$$n/2$$$$n/2^2 (n/4)$$$$n/2^3 (n/8)$$$$n/n^4 (n/16)$$$$...$$$$n/2^k$$ 위와 같은 순서가 성립된다. 이때, 입력크기가 1이되는 총 횟수를 k는 $$n/2^..
유클리드(Euclid) 알고리즘 최대공약수 최대 공약수는 2개 이상의 자연수의 공약수 중에 가장 큰 수를 말한다. 이 알고리즘은 '2개의 자연수 중 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.' 는 성질을 이용하여 최대공약수를 찾는 것이다. 예제) 24와 14의 최대공약수 24, 14 24 - 14, 14 = 10, 14 14 - 10, 10 = 4, 10 10 - 4, 4 = 6, 4 6 - 4, 4 = 2, 4 4 - 2, 2 = 2, 2 2 - 2, 2 = 0, 2 = 최대공약수 2 위 예제와 같이 최대공약수는 주어진 두개의 수에서 큰 수를 작은수로 계속 뺄셈을 하며 남은 수가 존재하지 않을때까지 진행한다. 이는 다음과 같은 코드로 변경 가능하다. private int GCD(in..
보호되어 있는 글입니다.
알고리즘의 효율성을 알아내기 위해 알고리즘을 측정하는 방법 종류 시간 복잡도 공간 복잡도 1. 공간 복잡도 (Space Complexity) 프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정하는 방법 공간복잡도는 시간 복잡도와 반비례하는 경우가 많다. 컴퓨터의 발전으로 대용량 지원이 많이되며 시간 복잡도보다 덜 중요시되는 경우가 많다. 1-1. 공간 복잡도 계산법 공간 복잡도는 알고리즘에 사용되는 저장 공간을 계산하면된다. 빅 오 표기법으로 표현할 수 있어야한다. int Factoria(int _fac){ int _return = 1; for (int n = 2; n < (_fac + 1); n++) _return *= n; return _return; } 위 팩토리얼 함수는 _fac, _re..
- Total
- Today
- Yesterday
- 백준
- 포인터
- 멀티스레드
- 크기
- c++
- 입출력
- 메모리
- 게임수학
- 구조
- 초기화
- 할당
- 상속
- dynamic_cast
- 운영체제
- New
- 스레드
- malloc
- 컴파일
- 함수
- 알고리즘
- 명령어
- 수학
- thread
- 인터럽트
- static_cast
- const
- 프로세스
- CPU
- 레지스터
- 클래스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |