1. 정의 -문자열이란? string이나 char[ ] 배열 초기화 함수: memset(배열이름, 초기화값, sizeof(배열이름)); -GCD란? Greatest Common Divisor: 최대공약수 -LCM이란? Least Common Multiple: 최소공배수 두 자연수의 공통된 배수 중 가장 작은 수 -> 최대공약수를 통해 구할 수 있음 2. 동작 원리 -GCD 방식1: 두 수 m, n를 입력받고 2부터 n까지 두 자연수를 모두 나누어보면 최대공약수를 구할 수 있음 방식2: 유클리드 호제법 m을 n으로 나눈 나머지를 r이라고 하면, m과 n의 최대공약수는 n과 r의 최대공약수와 같은 것을 이용 -LCM 두 수의 곱을 두 수의 최대공약수로 나누어주면 최소공배수를 알 수 있음 3. 코드 //GCD..
알고리즘
1. 벨만 포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다. 시간복잡도가 느리다. -> O(VE) 2. 동작 원리 시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면, x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다. 모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기 3. 코드 #define INF 987654321 typedef pair P; long long dist[510]; //각 도시의 거리 계산 long long 필수 vec..
