✔ Ax+By=C [백준 21568] 문제 분석하기 확장 유클리드 호제법을 그대로 구현 손으로 풀어보기 C의 값이 A와 B의 최대 공약수의 배수 형태인지 확인한 후, 최대 공약수의 배수 형태라면 C의 값을 최대 공약수로 변경 최대 공약수의 배수 형태가 아니라면 -1을 출력한 후 프로그램을 종료 A와 B에 관해 나머지가 0이 나올 때까지 유클리드 호제법을 수행 나머지가 0이 나오면 x = 1, y = 0으로 설정한 후 미리 구한 몫들의 식에 대입하면서 역순으로 계산 최종으로 계산된 x, y 값에 C를 x와 y의 최대 공약수로 나눈 값을 각각 곱해 방정식의 해를 구함 예) 5x + 9y = 2일 때 이 식을 만족하는 정수 x, y를 구해보자 1. 5x + 9y = 2 → 5x + 9y = 1 2. 유클리드 ..
✔ 칵테일 [백준 1033] 문제 분석하기 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있으므로 사이클이 없는 트리 구조로 이해하도록 함 그럼로 DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소 공배수와 최소 공약수를 구하고, 재료의 최소 질량을 구함 손으로 풀어보기 인접 리스트를 이용해 각 재료의 비율 자료를 그래프로 구현 데이터를 저장할 때마다 비율과 관련된 수들의 최소 공배수를 업데이트 임의의 시작점에 최대 공배수 값을 저장 임의의 시작점에서 DFS로 탐색을 수행하면서 각 노드의 값을 이전 노드의 값과의 비율 계산을 통해 계산하고 저장 각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력 예) 4 0 1 1 / 4 1 3 1 / 4 2 5 1 / 4 3 7 1 0 → ..
✔ 최대공약수 [백준 1850] 문제 분석하기 입력값이 크면 단순한 방법으로 최소 공배수를 찾을 수 없음 그러므로 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다는 규칙을 바탕으로 문제에 접근 예) 3, 6의 최대 공약수는 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타낼 수 있음 손으로 풀어보기 유클리드 호제법을 이용해 주어진 A, B의 최대 공약수를 구함 공약수의 길이만큼 1을 반복해 출력 슈도코드 작성하기 a(1번째 수) b(2번째 수) 결괏값 = gcd(a, b) 결괏값만큼 1을 반복해 출력하기 gcd { if(b가 0이면) a가 최대 공약수 else gcd(작은 수, 큰 수 % 작은 수) } 코드 구현하기 /** * 1850) 최대..
✔ 최소공배수 [백준 1934] 문제 분석하기 최소 공배수는 A와 B가 주어졌을 때 'A * B / 최대 공약수'를 계산해 구할 수 있으므로 유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주어 최소 공배수를 구하도록 함 손으로 풀어보기 유클리드 호제법을 이용해 A, B의 최대 공약수를 구함 두 수의 곱을 최대 공약수로 나눈 값을 정답으로 출력 슈도코드 작성하기 t(테스트 케이스) for(t만큼 반복하기) { a(1번째 수) b(2번째 수) 결괏값 = a * b / gcd(a, b) 결괏값 출력하기 } gcd { if(b가 0이면) a가 최대 공약수 else gcd(작은 수, 큰 수 % 작은 수) } 코드 구현하기 /** * 1934) 최소공배수 */ public cl..
✔ GCD(n, k) = 1 [백준 11689] 문제 분석하기 문제를 만족하는 자연수의 개수가 오일러 피 함수의 정의이므로 오일러 피 함수를 구현 손으로 풀어보기 서로소의 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언 2 ~ N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result / 소인수) 연산으로 result 값을 업데이트 n에서 이 소인수는 나누기 연산으로 삭제함 예) 현재 소인수가 2일 때, 2⁷ * 11 * 13을 11 * 13으로 변경 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수이므로 result = result - (result / n) 연산으로 result 값을 마지막으로 업데이트한 후 출력 예) n = 15 N..
✔ 제곱 ㄴㄴ 수 [백준 1016] 문제 분석하기 에라토스테네스의 체 알고리즘 방식으로 제곱수 판별 로직에 사용 손으로 풀어보기 2의 제곱수인 4부터 max값까지 제곱수를 찾음 이때 데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색 탐색한 배열에서 제곱수로 확인되지 개수를 센 후 출력 예) min = 1, max = 10 제곱수 pow start_index j Check 배열 i = 2, pow = 4 1 1 1 *4 - 1 = 3 Check[3] = 4 [false, false, false, true, false, false, false, false, false, false] 2 2 *4 - 1 = 7 Check[7] = 8 [false, false, fa..
✔ 소수&팰린드롬 [백준 1747] 문제 분석하기 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아냄 손으로 풀어보기 2 ~ 10000000 사이에 존재하는 모든 소수를 구함 그 중 N보다 크거나 같은 소수에서 팰린드롬 수인지를 판별 소수의 값을 char 배열 형태로 변환한 후 양끝의 투 포인터를 비교하면 쉽게 팰린드롬 수인지 판별 가능 최초로 팰린드롬 수가 나오면 프로그램을 종료 슈도코드 작성하기 N(어떤 수) A(소수 배열) for(2 ~ 10000001) { A 배열 초기화 } for(A 배열 길이의 제곱근까지 반복하기) { 소수가 아니면 넘어감 for(소수의 배수 값을 10000001까지 탐색하기) {..
✔ 거의 소수 [백준 1456] 문제 분석하기 최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결 이를 위해 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구하도록 함 손으로 풀어보기 2 ~ 10000000 사이에 존재하는 모든 소수를 구함 각각의 소수에 관해 소수를 N 제곱한 값이 B보다 커질 때까지 반복문을 수행 소수를 N 제곱한 값이 A보다 크거나 같으면 거의 소수로 판단해 카운트 N 제곱한 값을 구하는 도중 값의 범위가 long형을 초과하는 경우가 발생할 수 있으므로 N^k과 B 값이 아니라 N과 B/N^(k-1)을 비교하는 형식을 사용 예) A = 1, B = 1000 모든 소수 2, 3, 5, 7, 11, 13, 17, 19, 23..
