합병 정렬 (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^..
"알고리즘은 문제를 해결하는 단계적 절차 or 방법이다." 알고리즘의 특성 정확성 주어진 입력에 대한 올바른 해를 반환해야한다. 수행성 컴퓨터가 수행이 가능한 알고리즘이어야 한다. 유한성 일정한 시간 내에 종료되어야한다. 효율성 효율적일수록 그 가치가 높다. 알고리즘 표현 1. 의사 코드 (Pseudo Code) 의사코드는 긴 코드를 간략하게 표현한 프로그래밍 언어와 유사한 언어이다. 2. 플로우 차트 (Flow Chart) 의사 코드로도 표현하기 힘든 복잡하고 긴 알고리즘이 있다면 플로우 차트 형태로 표현하기도 한다. 알고리즘의 분류 분할 정복 (Divide-and-Conquer) 그리디 (Greedy) 동적 계획 (Dynamic Programming) 근사 (Approximation) 백트래킹 (Ba..
- Total
- Today
- Yesterday
- 명령어
- 인터럽트
- 구조
- thread
- 초기화
- 입출력
- 포인터
- 메모리
- 스레드
- const
- 수학
- static_cast
- 할당
- 클래스
- CPU
- 운영체제
- 함수
- 레지스터
- malloc
- New
- c++
- 컴파일
- 프로세스
- 멀티스레드
- 게임수학
- dynamic_cast
- 상속
- 알고리즘
- 크기
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |