그래프와 구현 방법그래프 ?아래와 같은 자료구조를 그래프라고 한다. 대표적인 구현 방식으로 3가지가 있다.엣지 리스트인접 행렬인접 리스트엣지 리스트이름에서 알 수 있듯이 엣지(Edge; 간선)를 중심으로 그래프를 표현한다. → 즉 그래프의 모든 간선을 리스트 형태로 저장한다 !가중치 X → 두 정점(출발지, 도착지)가중치 O → 두 정점(출발지, 도착지), 가중치List edgeList = new ArrayList();edgeList.add(new Edge(1, 2, 5)); // 간선 (1 -> 2), 가중치 5edgeList.add(new Edge(2, 3, 3)); // 간선 (2 -> 3), 가중치 3장점간선의 개수가 적을 때 메모리를 절약할 수 있다 !구현이 간단하고, 특정 알고리즘(ex: 크루..
유클리드 호제법을 이용하여 GCD를 구하는 방법[ ] 유클리드 알고리즘의 원리 ? → 두 수 a와 b가 있을 때, a와 b의 GCD는 b와 a를 b로 나눈 나머지의 GCD와 같다 !GCD(a, b) = GCD(b, a % b) ex) **GCD(48, 18)**를 구하는 과정(1) 48 ÷ 18 = 2 (나머지 12) → GCD(48, 18) = GCD(18, 12)(2) 18 ÷ 12 = 1 (나머지 6) → GCD(18, 12) = GCD(12, 6)(3) 12 ÷ 6 = 2 (나머지 0) → GCD(12, 6) = GCD(6, 0) = 6유클리드 알고리즘의 단계큰 수(a)를 작은 수(b)로 나눈 나머지를 구한다.작은 수(b)와 나머지(a % b)를 가지고 다시 나눗셈을 반복한다.나머지가 0이 될 때..
오일러피 함수[ ] 오일러피 함수는 1부터 n까지의 정수 중에서 n과 서로소인 정수의 개수를 구하는 함수이다. ( ex: n = 9 일 때, 1부터 9 사이에서 9와 서로소인 정수는 1, 2, 4, 5, 7, 8로 총 6개이다. )$$ \phi(9) = 6 $$n이 소수인 경우$$ \phi(n) = n - 1 $$n이 소수가 아닌 경우(일반적인 경우)소인수(p1, p2, … , pk) 분해를 사용하여 계산 가능하다 !$$\phi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \dots \times \left(1 - \frac{1}{p_k}\right) $$[ ] 코드로 구현하면 다음과..
https://thin-azimuth-2a9.notion.site/GDG-11ff4ee21c0080de9516c35f8404978f?pvs=4
https://thin-azimuth-2a9.notion.site/cf-117f4ee21c0080f1bd47f07bf9dfa241?pvs=4
https://thin-azimuth-2a9.notion.site/106f4ee21c00807a958ecc9619df6e60?pvs=4
