완전탐색과 쌍 비교: 중복 없는 후보 열거와 순위 계산

완전탐색에서 두 위치의 쌍 열거와 공동 순위 계산은 무엇이 다른가요?

완전탐색은 가능한 후보를 빠짐없이 확인하는 방법입니다. 두 개를 고르는 문제와 각 사람을 전체와 비교하는 문제는 반복 범위가 다릅니다.

[2,5,3,5]에서 합이 7인 인덱스 쌍은 (0,1)과 (0,3)입니다. 값이 같은 두 5도 서로 다른 위치입니다.

적용 조건·범위: 두 예제 모두 O(N²) 시간입니다. N=9의 쌍은 36개지만 N=100,000의 쌍은 4,999,950,000개입니다. 입력 제한과 후보당 계산량을 함께 보세요. 작은 입력에서는 단순한 완전탐색을 기준 답으로 삼아 더 빠른 풀이와 비교하기도 좋습니다.

본문 근거: Competitive Programmer’s Handbook — Antti Laaksonen

이 글에서 할 일: 쌍 열거와 공동 순위 계산에 맞는 반복 범위를 선택합니다. 선수 지식: 배열 인덱스·중첩 반복문.

순서 없는 쌍은 i보다 큰 j만 고릅니다

아래 JavaScript 예제는 서로 다른 두 위치를 골라 합이 목표값인 쌍을 찾습니다. 코드 아래의 결과를 보면서 같은 쌍을 두 번 세지 않는 반복 범위를 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function pairIndices(values, target) {
  const result = [];
  for (let i = 0; i < values.length; i++) {
    for (let j = i + 1; j < values.length; j++) {
      if (values[i] + values[j] === target) result.push([i, j]);
    }
  }
  return result;
}

console.log(JSON.stringify(pairIndices([2, 5, 3, 5], 7)));

실행 결과

[[0,1],[0,3]]

j = i + 1이면 자기 자신과 비교하지 않고, (i,j)와 (j,i)를 중복으로 세지 않습니다. 서로 다른 두 인덱스는 작은 인덱스를 i로 정하는 방법이 하나뿐이므로 모든 쌍을 정확히 한 번 방문합니다.

원소 N개에서 후보 수는 (N-1)+(N-2)+…+1 = N(N-1)/2입니다. 두 명을 제외하는 문제라면 전체 합에서 values[i]+values[j]를 빼고 조건을 확인할 수 있습니다. 찾은 뒤 나머지를 원래 순서대로 출력해야 한다면 입력을 임의로 정렬하지 않습니다.

node --version

node pairs.js

등수는 자신보다 큰 점수의 수에 1을 더합니다

아래 JavaScript 예제는 각 점수보다 큰 점수가 몇 개인지 세어 등수를 구합니다. 코드 아래의 결과와 표를 보면서 동점인 점수에 같은 순위가 매겨지는 이유를 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function ranks(scores) {
  const result = [];
  for (let i = 0; i < scores.length; i++) {
    let rank = 1;
    for (let j = 0; j < scores.length; j++) {
      if (scores[j] > scores[i]) rank++;
    }
    result.push(rank);
  }
  return result;
}

console.log(JSON.stringify(ranks([80, 90, 90, 70])));

실행 결과

[3,1,1,4]

각 i의 등수를 구할 때는 j를 처음부터 끝까지 확인합니다. 이때 비교는 >입니다. 자신과 동점인 점수는 증가 조건을 통과하지 않습니다. >=로 바꾸면 자신과 동점자까지 더해져 결과가 달라집니다. 이 규칙은 1,1,3처럼 공동 순위 뒤의 등수를 건너뜁니다.

node --version

node ranks.js

후보 수로 실행량을 판단합니다

두 예제 모두 O(N²) 시간입니다. N=9의 쌍은 36개지만 N=100,000의 쌍은 4,999,950,000개입니다. 입력 제한과 후보당 계산량을 함께 보세요. 작은 입력에서는 단순한 완전탐색을 기준 답으로 삼아 더 빠른 풀이와 비교하기도 좋습니다.

순위 결과 배열은 O(N) 공간, 쌍 결과는 정답 쌍이 P개이면 O(P) 공간입니다. 빈 입력은 빈 결과를 반환하고, 한 점수의 등수는 1입니다. 같은 숫자라도 인덱스가 다르면 별도 후보라는 점을 유지하세요.

직접 확인하고 문제에 적용하기

[5,5,5]의 등수와 합이 10인 쌍의 수는 각각 얼마일까요?

• 일곱 난쟁이 풀이 — 제외할 두 명 찾기
• 등수구하기 풀이 — 공동 순위 적용
• 배열 인덱스와 연산 비용

참고 자료

자료 확인일: 2026년 10월 19일.

• Competitive Programmer’s Handbook — Antti Laaksonen — 5장의 완전탐색과 22장의 조합 수.