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