알고리즘: 기초정리(1)

알고리즘: 기초정리(1)

알고리즘: 기초정리(2)

00. 상식 

1. 알고리즘이란? ① 정의 알고리즘이란 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합이다. - C로 배우는 알고리즘, 27쪽 -

② 어떤 알고리즘을 써야 하는가? - 알고리즘의 종류는 많다. 하지만 만병통치약같은 알고리즘은 없다. 그렇기 때문에 해결하고자 하는 문제에 적합한 알고리즘을 선택해야 한다. 또한 알고리즘의 속도/메모리 소요를 고려해야한다. - 문제를 해결할수 있는 알고리즘중 단순한 알고리즘을 쓰는것이 좋다. 하지만 속도와 자료처리량에 따라서 타협이 필요하다.

2. 알고리즘 분석

① 경험적/수학적 분석 - 경험적 분석 : Empirical analysis. 프로그램 언어로 구현해서 실행시간을 비교하는 분석법. - 수학적 분석 : Mathematical analysis. 수학적 분석만으로 알고리즘의 실행시간을 분석.

② 최악/최선의 경우(시간소요량 기준) - 최악의 경우란 알고리즘이 실행되는데 걸리는 최대의 시간을 말한다.  즉, 늦어도 이정도 시간까지는 문제해결이 된다. - 알고리즘이 실행되는게 걸리는 최소의 시간.

③ 알고리즘 분석의 단계(3단계) - 입력자료 결정 : 여러종류의 자료를 입력하면 실행시간의 범위가 유추된다. 이 과정에서 평균 수행시간을 구할수도 있다. - 수행시간 계산 : 알고리즘의 동작을 분해해서 계산. - 수학적인 분석 : 최악의 경우를 이용해서 수행시간의 상한선등을 결정할수 있다.

3. 알고리즘의 유형 * N = 입력되는 자료의 수 * 어떤 알고리즘이라도 변형에 따라 수행시간 유형이 달라진다.(=프로그래머 재량에 좌우....)
1	입력 자료와 무관한 실행시간  명령들을 1번만 실행하거나 몇번만 실행
log N	성능이 좋은 검색 알고리즘은 대부분 이 정도 실행시간을 가진다.
N	자료량에 비례되는 실행시간.  이 정도가 되어도 쓸만한 실행시간이라고 한다.
N log N	규모가 큰 문제를 작은단위로 쪼개서 각각을 해결한 후에 통합하는 경우(Top down - Integration???)
N²	이중루프에서 자료를 처리할때 발생.  자료량이 많을때는 비권장.
N³	자료량이 많은 문제에는 부적합
2ⁿ	처음 개발된 알고리즘에 간혹 나타남.

01. 간단한 알고리즘

1. 유클리드 알고리즘(Euclid's Algorithm) -> 최대공약수(Greatest Common Divisor)를 구하는 알고리즘이다.
① 성질      GCD(u, v) = GCD(u-v, v) [u에 u-v를 저장.]      GCD(u, v) = GCD(v, u)    [좌, u < 우, v일때 교환.]      GCD(u, 0) = u                 [u = 0, 2로 돌아간다 / u != 0, v가 최대 공약수]  최대 공약수의 성질을 이용해서 뺄셈/두 값의 교환을 사용해서 최대 공약수를 구한다.
② 구현 [*.cpp]
//Gcd.h #pragma once class Gcd { public: Gcd(void); //생성자 ~Gcd(void); //소멸자 private: int _u; int _v; public: void set_gcd(int u, int v); void get_gcd(); void print(int incoming); };	//Gcd.cpp #include <iostream> #include "Gcd.h" void Gcd::set_gcd(int u, int v) { _u = u; _v = v; } void Gcd::get_gcd() { printf("GCD(%d, %d)\n", _u, _v); int tmp = 0; int result = 0; while( _u ) { if( (_u < _v) || (_u == 0) )//기본 처리법 { tmp = _u; _u = _v; _v = tmp; } _u -= _v; printf("= GCD(%d, %d)\n", _u, _v); } tmp = _u; _u = _v; _v = tmp; result = _u; print(result); } void Gcd::print(int incoming) { printf("최대공약수 = %d\n", incoming); }
#include <iostream> #include "Gcd.h" using namespace std; int main() { Gcd gcd; //객체 선언 int u, v; char quit; cout << "C가 보이는 알고리즘, CH01-01_유클리드" << endl; cout << "양의 정수1 : "; cin >> u; cout << "양의 정수2 : "; cin >> v; gcd.set_gcd(u, v); gcd.get_gcd(); cout << "press to char key?!"; cin >> quit; return 0; }
③ 나머지 연산(%)을 이용한 개선      GCD(u, v) = GCD(u%v, v) [u에 u%v를 저장후 새로운 u와 v의 위치를 맞교환] -> 조금 풀어 보면 기존것은 순차적으로 뺼셈을 여러번 했는데, 그 뺄셈을 묶으면 v의 배수가 되니깐 나머지 연산을 시켜서 0이면 v가 최대공약수가 되는거다. void Gcd::get_gcd() { ... ... ... _u %= _v; // _u = _u % _v; while( _u ) { if( (_u < _v) || (_u == 0) ) //기본적인 처리법 { tmp = _u; _u = _v; _v = tmp; } _u -= _v; printf(" = GCD(%d, %d)\n", _u, _v); } ... ... ... print(result); }
④ 루프횟수 비교
	-> 나머지 연산값이 0이라서 while문을 돌지 않고 완료되었다.

2. 소수를 구하기 알고리즘(1)
① 성질      1과 자기자신만으로 나누어 떨어지는 양의 정수 ->소수인지를 판별하는데 적합하다.
② 구현 [*.cpp]
//Prime.h #include <string> #pragma once class Prime { public: Prime(void); ~Prime(void); void set_prime(int div); int get_prime(); private: int prime; int not_prime; int _max; };	//Prime.cpp #include <iostream> #include "Prime.h" Prime::Prime(void) { prime = 1; not_prime = 0; _max = 0; } Prime::~Prime(void) { } //사용자 정의 함수---------- void Prime::set_prime(int limit) { _max = limit; } int Prime::get_prime() { if( (_max == 0) || (_max == 1)) return not_prime; if( _max == 2) return prime; for(int k = 2; k < _max; k++) { if(_max%k == 0) return not_prime; return prime; } }
//main_prime.cpp #include <iostream> #include "Prime.h" using namespace std; int main() { Prime prime; int limit = 0; int result = 0; int quit = 0; printf("C가 보이는 알고리즘, CH01-02_소수\n"); printf("2이상의 양의 정수를 입력하세요: "); scanf("%d", &limit); prime.set_prime(limit); result = prime.get_prime(); cout << "[소수: 1 / 아니면 0] -> " << result; cin >> quit; return 0; }
③ 제곱근 sqrt()를 이용한 개선시도 -> 하지만 코드상 간결해진다 하더라도 sqrt()함수는 실수형 데이터라서 이를 캐스팅 시키고 하면 전체수행시간이 더뎌지는 단점이 있다. -> 하지만 입력값에 의한 속력차가 없다고 한다. (즉, 입력값이 클떄 유용)

3. 소수를 구하기 알고리즘(2)
① 성질      입력된 N의 크기만큼 배열을 생성한다.      for(int k; k < N; k++)           arr[k] != 0이면 i++로 재실행           for(j= i+i; j <= N; j+=i)           arr[j] = 1;      for(int k; k < N; k++) ->특정 숫자보다 작은 소수를 구하는데 유용
② 구현 [*.cpp]
//Eratosthenes.h #pragma once class Eratosthenes { public: Eratosthenes(void); ~Eratosthenes(void); void set_Eratosthenes(int max); void get_Eratosthenes(); private: int _max; int arr[]; };	//Eratosthenes.cpp
//main.cpp

02. 주요 개념들

1. 최적화 기법

① 문제에 맞는 좋은 알고리즘을 선택한다. ② 함수를 사용하면 함수호출등으로 속도가 느려지거나 오버헤드가 발생할수도 있으나, 적절히 사용하면 컴파일후 실행파일의 크기가 작아진다. ③ 실수형 연산 사용을 줄여라. ④ 반복문내를 최대한 간결하게 하라. ⑤ 재귀호출 형태는 가급적 피하자.

2. 데이터 추상화

-> 구조체처럼 공통된 정보를 가진 정보집합을 대표명을 가진 묶음으로 만든것이다.

3. 포인터
① 포인터와 변수 int n; int *myPointer; myPointer = &n;   //-> 특정변수의 주소값을 저장하는 변수		②포인터의 포인터 ->연결된 링크참조
③ void 포인터 -> 주소만 저장하는 포인터로 사용하는데 약간 주의해야 한다. -> 포인터가 가르키는곳의 내용물을 읽는 역참조 사용불가. -> 데이터형이 없으므로 연산처리불가. void *v_pt; int a, b; a = *(int*)v_pt; b = *((int*)v_pt + 1);		④ 포인터와 구조체 struct box { int width; int height; } struct box b1, *b2; b2 = &b1; ... ... ... b1.width = 100; b1.height = 200; ... ... ... b2->width = 2000; b2->height = 12;
⑤ 함수 포인터 -> 세부사항은 연결된 링크 참조

4. OOP

① 캡슐화(=은닉) ② 다형성 ③ 상속