알고리즘이란 (feat 유클리드 호제법) | 코딩테스트 전에 알면 좋은 것들

'수'에 대한 '문제를 푸는 방법'

컴퓨어 분야에서는 '공식화된', '단계적'이라는 조건

애매모호하며 언제 끝날지 모르는 절차는 알고리즘으로 부를 수 없다.

 

유클리드 호제법

두 정수의 최대공약수를 구하는 알고리즘

1. 두 정수의 큰 쪽 - 작은 쪽, 양쪽이 같아질 때까지 반복한다.

2. 같아진 값이 최대공약수가 된다.

예) 50과 30의 최대공약수 = 10

30	30	30-20=10	10
50	50-30=20	20	20-10=10

 

cf. 나머지로 최대공약수 구하기

큰 쪽에서 작은 쪽은 나눈 나머지를 계속 구한다. 나머지 값이 0이 되는 몫을 최대공약수라 한다.

예) 50과 15의 최대공약수 = 5

1. 15 < 50 => 50 % 15 = 5 (50 -> 5)

2. 5 < 15 => 15 % 5 = 0

 

최소공배수 알고리즘

두 값 곱하고 최대공약수 나눠주기

예) 50과 30의 최소공배수 = 50 * 30 / 10 = 150

30	30*2=60	60	30*3=90	30*4=120	120	30*5=150
50	50	50*2=100	100	100	50*3=150	150

 

#include <stdio.h>

int main(void) {
	int a, b;

	scanf_s("%d %d", &a, &b);

	while (a != b) {
		if (a > b) {
			a -= b;
		}
		else {
			b -= a;
		}
	}

	printf("%d\n", a);

	return 0;
}

---

🟩 코딩테스트 전에 알면 좋은 것들

🌟 STL

ps(program solving)을 공부하기 전 익혀야 하는 이유 : 알고리즘을 빠르게 구현 가능

문제를 푸는 시간의 대부분은 생각해낸 알고리즘을 '구현'하는 시간, 프로그램 실행 시간은 미미하다.

STL = container(자료구조), iterator, algorithm, functor

각 자료구조마다 다른 특징을 가지고 있지만, 선언법은 매우 유사하다.

👉 컨테이너명 <자료형> 변수명;

pair <int, int> myPair;
vector<double> myVector;
queue<pair<int,int>> myQueue;
stack<char> myStack;

 

🌟 전역변수

전역변수를 적극 활용하자 👉 시간 절약, 일이 쉬워진다.

만약, 전역변수보다 함수의 파라미터로 변수를 넘겨주는 것이 더 의미가 명확한 경우, c++의 참조자(reference)를 이용하여 넘겨주면, 값을 복사해오는 쓸데없는 시간을 없앨 수 있다.

함수의 동작과 의미상 별로 관련이 없는 변수 👉 전역변수

함수의 동작과 의미상 관련이 있는 변수 👉 파라미터로 넘겨주되, 참조자로!

int sumOfArray(int s, int e, int arr[]) {
	int ret = 0;
    for(int i = s; i <= e; ++i) {
    	ret += arr[i];
    }
    
    return ret;
} // before

int s, e, arr[1000];
int sumOfArray(vector<int>& arr) {
	int ret = 0;
    for(int i =s; i<= e; ++i) {
    	ret += arr[i];
    }
    
    return ret;
} // after

 

🌟 동적 할당

배열의 크기를 입력받아 정하고 싶은 경우, malloc을 동적 할당을 통해 구현하게 된다. 하지만 ps를 할 때 동적할당을 이용하면 시간 초과가 날 수 있다.

 

따라서 ps를 할 때는 입력으로 들어온 최대 크기만큼 배열을 넉넉하게 잡아놓고 문제를 푸는 것이 좋다. 최댓값이 1000인 경우, 배열의 크기를 1001로 잡고 푼다.

👉 i번째 값을 채울 때, i-1 값을 참조해서 채우게 되는데, 0번째 행부터 채우게 되면 -1번째 행을 참조하게 되어 오류 발생 가능

 

입출력할 개수가 많다면, cin, cout보다는 scanf, printf를 사용하는 것이 좋다. cin, cout에 비해 빠르기 때문이다.

따라서 특별한 경우가 아니라면, scanf, printf를 사용하는 것이 좋다.

특히 endl이 많이 느리다. 따라서 endl 대신 '\n'을 사용하는 것을 권장한다.