Algorithm
Latest Post
-
[BOJ] 7569번: 토마토
😃 [BOJ] 7569번: 토마토 🔗INFOLanguage usedJAVALevelGOLD 5CategoryBFSComplexity-Solving Date2024.07.22Solving Time2H 👉🏻 이 문제는 어떠 어떠한 알고리즘을 사용하는 문제입니다.그래프 이론그래프 탐색너비 우선 탐색너비 우선 탐색 알고리즘을 사용하여 문제 풀이를 진행했습니다.👉🏻 사전 필요 개념BFS👉🏻 접근 방식시간제한 1초에 배열의 최대 크기는 100 x 100 x 100 인 1,000,000 이고 6방향을 체크해야 하기 때문에 단순하게 BFS를 사용했다가 시간 제한이 걸릴 것이라 생각했습니다. 그래서 구상 시간을 오래 가져보았지만 다른 방안으로도 비슷한 복잡도가 계산되어 BFS로 구현을 시작해보았습니다.👉..
-
유클리드 호제법(최대공약수, 최소공배수)
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법(Euclidean Algorithm) 두 양의 정수 a,b (a>b)에 대하여 a=bq+r(0≤r gcd(a, b)=gcd(b, r) r=0이라면, a,b의 최대공약수는 b가 된다. (증명) gcd(a,b) = k a=nk b=mk a=bq+r nk=mkq+r r=(n-mq)k m과 n-mq 서로소라면 k는 최대공약수 (공통인수가 있다면 k는 최대공약수가 아님) (귀류법) 가정 [ m과 n-mq 서로소가 아니다. ] m = xG n-mg = yG ..