[바미] 알고리즘 수업 - 알고리즘의 수행 시간 4

https://www.acmicpc.net/problem/24265

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

---

코드

function menOfPassionAlgorithmPerformance(n) {
    // 코드1의 수행 횟수, n(n-1)/2번
    console.log((n * (n - 1)) / 2);
    // 코드1의 수행 횟수를 다항식으로 나타냈을 때, 최고차항의 차수는 2
    console.log(2);
}

const readline = require('node:readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', (line) => {
  const n = parseInt(line, 10); // 10진수로 변환
  menOfPassionAlgorithmPerformance(n);
  rl.close();
});

문제 설명

이번 문제에서 제시된 MenOfPassion 알고리즘은 배열 내 모든 가능한 요소 쌍의 곱의 합을 계산합니다. 

 

이 알고리즘의 핵심은 배열의 각 요소를 순회하면서, 현재 요소보다 인덱스가 높은 요소들과의 곱을 찾아 합계에 더하는 것입니다. 

 

여기서 i와 j는 배열의 인덱스를 나타내며, 0이 아닌 1부터 시작한다는 점에 유의해야 합니다(일반적으로 인덱스가 0부터 시작하는 경우가  여기서는 1부터 시작한다고 가정합니다.).

 

이 문제에 제시된 알고리즘의 동작 방식을 좀 더 구체적으로 설명해보겠습니다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

1. 먼저 합계를 저장할 변수 sum을 0으로 초기화합니다.
2. 그 후 i를 1부터 n-1까지 반복합니다. 이 반복문은 배열의 첫 번째 요소부터 마지막에서 두 번째 요소까지 각 요소를 순회합니다.
3. j를 i+1부터 n까지 반복합니다. i 요소의 바로 다음 요소부터 마지막 요소까지 순회하며, 이는 i 요소와 조합할 수 있 모든 요소를 대상으로 합니다.
4. 내부 반복문에서 A[i]와 A[j]의 곱을 계산하고, 이 값을 sum에 더합니다. 이 과정은 모든 가능한 i와 j의 조합에 대해 반복됩니다.
5. 모든 반복이 완료되면, 계산된 합계 sum이 반환됩니다.

이 알고리즘은 특히, 각 요소가 다른 모든 요소와 한 번씩만 곱해지도록 합니다. 이는 중복 계산을 방지하고, 배열 내 모든 가능한 요소 쌍의 곱셈 결과를 정확하게 합산하는 데 중요합니다.

 

만약 A[] = [1, 2, 3]이고 n = 3일 때, 알고리즘은 다음과 같이 동작하게 됩니다.

i=1, j=2일 때: 1 × 2 = 2
i=1, j=3일 때: 1 × 3 = 3
i=2, j=3일 때: 2 × 3 = 6
합계 sum = 2 + 3 + 6 = 11

 

이러한 방식으로 MenOfPassion 알고리즘은 배열 내 모든 요소 쌍의 곱셈 합을 효율적으로 계산합니다.