정수론 유클리드 호제법 문제풀이 중 백준 칵테일 문제를 풀게되었다. 유클리드 호제법을 알고 최대공약수를 구하는 과정 자체는 간단하지만 문제 풀이가 간단하지 않아서... 글로 정리해보려 한다. 글 작성에 앞서 문제를 푸는 아이디어를 얻기위해 여러 게시글과 백준 질문 게시판, ChatGPT의 도움을 받았다.
문제에서 상황설명이 꽤 길게 작성되어있는데 그것때문에 더욱 헷갈린 것 같다. 문제 내용을 정리하면 칵테일들중 특정 두개의 비율을 몇개 알려줄테니 전체의 비율을 구해라 이다. 이 점을 기억하고 풀이하면 도움이 될 것 같다.
• 문제 : 백준 1033번 - 칵테일
문제를 풀기 위해 아래와 같은 요소들을 고려하였다.
- 최대공약수, 최소공배수를 구할때 유클리드 호제법을 활용했다.
- 입력에서 주어지는 각 비율값을 통해 순차적으로 모든 재료의 양으로 조절해야한다. 이 과정은 그래프를 통해 이루어졌다.
- 비율을 관리하므로 분수 구조를 이용해 순차적으로 계산했다.
• 소스코드
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
rl.on("line", (line) => input.push(line)).on("close", () => {
// 최대공약수 (유클리드 호제법)
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
// 최소공배수
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
const N = parseInt(input[0]);
const graph = Array.from({ length: N }, () => []);
// 양방향 그래프 생성
for (let i = 1; i < input.length; i++) {
const [a, b, p, q] = input[i].split(" ").map(Number);
graph[a].push({ node: b, p, q });
graph[b].push({ node: a, p: q, q: p });
}
// 분수로 재료량을 저장 (num / den)
const fractions = Array(N).fill(null);
fractions[0] = { num: 1, den: 1 };
const visited = Array(N).fill(false);
// dfs로 비율에 맞춰 분수로 값 저장
function dfs(cur) {
visited[cur] = true;
for (const edge of graph[cur]) {
const next = edge.node;
if (!visited[next]) {
let newNum = fractions[cur].num * edge.q;
let newDen = fractions[cur].den * edge.p;
fractions[next] = { num: newNum, den: newDen };
dfs(next);
}
}
}
dfs(0);
// 분모의 최소공배수 찾기
let commonMultiple = 1;
for (let i = 0; i < N; i++) {
commonMultiple = lcm(commonMultiple, fractions[i].den);
}
// 분모 제거 (통분 하여 정수로 된 비율 찾기)
const result = fractions.map(({ num, den }) => (num * commonMultiple) / den);
// 최대공약수로 나누어 최종 결과 계산
let commonGCD = result[0];
for (let i = 1; i < result.length; i++) {
commonGCD = gcd(commonGCD, result[i]);
}
const finalResult = result.map((val) => val / commonGCD);
console.log(finalResult.join(" "));
});풀이과정을 찬찬히 살펴보자.
• 풀이에 앞서 - 풀이과정은 여러가지
코딩테스트 문제가 대부분 그렇지만 풀이과정은 매우 다양하다. 해당 문제도 아주 다양한 방법으로 풀이되는데 풀이법을 크게 두가지로 나누면 아래와 같다.
- 비율값 데이터를 받을때마다 연결된 모든 재료 양을 갱신한다. 이전에 받은 값들 중에 지금 입력받은 비율에 의해 영향을 받는 모든 재료들의 양을 지속적으로 갱신하는 방식. 이 방식은 비율 데이터를 연결된 순서로 받을 필요가 없다. 아무 순서로 처리해도 제대로 된 연산이 가능하다.
- 데이터를 순차적으로 계산하여 기준점을 두고 계산한다. 이 방식은 이전에 입력한 재료값에 대해 갱신이 필요하지 않다. 비율 값에 대해 차근차근 재료량을 쌓아가는 방식이기 때문에 연결된 값들에 대해 순차적인 접근이 필요하다.
이 풀이에서는 2번 풀이방식을 이용해서 문제를 해결했다.
이 방식의 풀이가 가능한 이유는 모든 재료에 대해 비율적으로 어떻게든 연결이 되어 있어야 최종 답을 구할 수 있기 때문이다.
• 풀이에 앞서 - 비율 데이터를 그래프 순차적으로 접근
비율 데이터를 양방향 그래프로 만들어 값들을 순차적으로 접근하며 재료 양을 정한다. 전체 풀이과정을 요약하면 아래와 같다.
- 비율 데이터에 대해 그래프를 생성
비율로 그래프를 생성하려면 비율 값에 대해 양방향으로 그래프를 만들어야한다. 예를들어 각 재료가 그래프의 노드를 담당하면 재료 1과 재료 2가 1:3 비율일때 노드 1번에는 [2번노드에 대해 1:3] 이라는 값이 추가되고 노드 2번에는 [1번노드에 대해 3:1] 이라는 값이 추가된다. - 분수로 재료량을 저장 (num / den)
기준점은 항상 노드 0번으로 한다. 노드 0번을 num : 1, den : 1 로 1/1 분수 저장하고, 추후 비율 데이터에 따라서 다른 재료의 값도 분수로 저장한다. - 통분을 통해 자연수 비율 찾기
분수로 저장된 값을 통분을 통해 자연수 비율을 찾는다. 이후 자연수들의 최대공약수로 수들을 나눠주면 정답이다.
1. 유클리드 호제법
풀이 과정중에 최대공약수와 최소공배수를 활용해야한다. 유클리드 호제법을 이용해 이를 구하는 함수를 구현하고 필요한곳에 가져다 사용하면 된다.
• 최대공약수
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
유클리드 호제법에서는 재귀함수를 통해 최대 공약수를 구한다. a, b (a>b)의 최대 공약수를 구할때는 나머지를 활용한다. a로 b를 나누고, 그 나머지로 b를 다시 나누는걸 반복하며 나머지가 0이 될때의 나눠진 수가 최대공약수이다.
• 최소공배수
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
최소공배수는 두 수의 곱을 최대공약수로 나누어 계산한다.
2. 양방향 그래프 만들기
비율 정보에 대해 그래프를 만든다. BFS, DFS 관련 문제를 풀이해봤다면 많이 본 방식이다.
for (let i = 1; i < input.length; i++) {
const [a, b, p, q] = input[i].split(" ").map(Number);
graph[a].push({ node: b, p, q });
graph[b].push({ node: a, p: q, q: p });
}
// 5
// 4 0 1 1
// 4 1 3 1
// 4 2 5 1
// 4 3 7 1
//
// 이 입력값에 대해 아래와 같이 graph가 만들어진다.
//
// [
// [ { node: 4, p: 1, q: 1 } ],
// [ { node: 4, p: 1, q: 3 } ],
// [ { node: 4, p: 1, q: 5 } ],
// [ { node: 4, p: 1, q: 7 } ],
// [
// { node: 0, p: 1, q: 1 },
// { node: 1, p: 3, q: 1 },
// { node: 2, p: 5, q: 1 },
// { node: 3, p: 7, q: 1 }
// ]
// ]
예를들어 입력값 4 1 3 1 은 node 4와 node 1에 대해 아래와 같이 저장된다.
- node 1에 대해 node 4는 1:3의 비율을 가진다.
graph[1]에 { node: 4, p: 1, q: 3 } 저장 - node 4에 대해 node 1은 3:1의 비율을 가진다.
graph[4]에 { node: 1, p: 3, q: 1 } 저장
이 과정을 통해 모든 재료는 비율값을 기준으로 그래프 연결이 되었고 dfs 탐색을 통해 모든 값을 탐색할 수 있게 되었다.
3. 분수로 재료의 양(상대적 비율)을 저장
문제에서 "재료의 양을 구하고 그 합을 최소로 만들어라" 라는 문구가 생각을 복잡하게 만들 수 있는데 그냥 모든 재료의 비율을 구하라는것과 같은 말이다.
이 풀이는 앞서 설명한것과 같이 기준점(항상 0번 재료)을 두고 모든 값을 비율에 따라 저장하는 방식을 사용한다.
분수는 fractions 배열에 저장이 되며 항상 기준이 되는 0번 재료는 분수 1/1 {num: 1, den: 1} 형태로 우선 저장된다.
이후 진행되는 과정을 간단한 예시로 보면 아래와 같다.
예)
node 0 : node 1 = 2 : 3 이고
node 1 : node 2 = 4 : 1 일때
node 0을 기준으로 두고 계산한다.
node 0을 1로 고정한다면 node 1은 3/2 이다.
node 1이 3/2이면 4:1 비율에 의해 node 2는 3/8 이다.
이런 과정을 DFS를 통해 반복하며 모든 노드를 비율에 맞춰 단순히 채워나가는 과정이다.
아래 예시를 하나 더 보자.
입력값 :
5
0 1 1 3
1 2 2 5
3 4 2 3
0 3 3 4
입력값이 위와 같을때 fractions 배열에 저장되는 각 node의 분수값은 아래와 같다.
모든 노드는 연결되어 있으므로 탐색 한번으로 모든 노드에 대해 비율에 맞는 분수값을 저장할 수 있다.
4. 통분, 최대공약수를 통한 전체 비율 구하기
위 예시에서 구해진 fractions 배열을 분수로 정리하면 아래와 같다.
- node0 : 1/1
- node1 : 3/1
- node2 : 15/2
- node3 : 4/3
- node4 : 12/6
다음 분모들의 최소공배수를 구하여 모든 분수를 통분한다.
- 1, 1, 2, 3, 6의 최소공배수 = 6
- 통분 후의 결과 = 6/6, 18/6, 45/6, 8/6, 12/6
분모를 제거하면 모든 노드들의 재료 비율을 구할 수 있다. 분모를 제거한뒤의 수들이 서로소가 아닌경우 최대공약수로 나누어 최소값의 비율을 찾을 수 있다.
- 모든 재료의 비율 = 6 : 18 : 45 : 8 : 12
4-1. 백준 예제 입력으로 풀어보기
백준 문제에서의 예제 입력 1번은 아래와 같다.
5
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1
이에 대해 fractions 배열을 분수로 정리하면 다음과 같다.
- node0 : 1
- node1 : 1/3
- node2 : 1/5
- node3 : 1/7
- node4 : 1
여기서 분수를 통분하고 분모를 제거하여 비율을 구한다.
- 통분 결과 = 105/105, 35/105, 21/105, 15/105, 105/105
- 모든 재료의 비율 = 105 : 35 : 21 : 15 : 105
5. 결론
유클리드 호제법을 익히기 위해 풀어본 문제인데 그래프탐색과 비율에 관한 문제풀이법에 대해서도 많이 알 수 있었다.
이것보다 더 효율이 좋고 깔끔한 해법도 있을것 같은데 한 노드에 대해 중복 연산이 발생하지 않는다는 점에서는 이 방식이 괜찮은것 같다.
중간에 비율을 곱해서 분수를 저장하는 과정에 기약분수를 구해서(약분 이후) 저장하면 큰 수를 연산할때 조금 더 깔끔하게 fractions 배열이 관리될것같기도 하다.
알고리즘 문제풀이는 방식을 모르면 난이도가 낮더라도 접근조차 힘든 문제들이 많이 있다. 다양한 유형을 풀어보고 잘 정리해두는게 문제풀이에 많은 도움이 될것같다.
📖 이 글은 학습 과정에서 정리한 내용이라 부족한 점이 있을 수 있습니다.
☑️ 틀린 부분이 있다면 편하게 알려주셔도 괜찮습니다.
😊 읽어주셔서 감사합니다.
'컴퓨터 과학 > 백준 문제풀이' 카테고리의 다른 글
| (JavaScript) 백준 11003번 : 최솟값 찾기 (0) | 2025.03.17 |
|---|---|
| (JavaScript) 백준 3190번 : 뱀 - 큐와 데크 (0) | 2025.01.16 |
| (JS) 백준 13458번 : 시험 감독 - 백준의 입력값 처리 (0) | 2025.01.13 |