[정글 베이직 4] 두 수의 합 완성

 

이중 반복문이면 된다고 생각했다.

배열에서 두 수를 골라서 합이 target이 되면 저장하면 되잖아.
근데 실행해봤더니 결과에 (0, 1)도 있고 (1, 0)도 있었다.
같은 쌍이 두 번 들어간 거다.

심지어 (0, 0)도 들어갔다. 자기 자신과의 합.
조건을 하나 빠뜨렸을 뿐인데 결과가 완전히 달라졌다.

---

문제 소개

정수 배열과 목표 값이 주어진다.
두 수를 골랐을 때 합이 target이 되는 모든 인덱스 쌍 (i, j)를 찾는 것.
단, i < j 조건을 지켜야 한다.

항목	내용
입력	nums: 정수 배열, target: 목표 합
출력	(i, j) 인덱스 쌍의 리스트 — i < j
핵심 도구	이중 반복문, range(i+1, n), 완전 탐색(Brute Force)

예제 입출력은 이렇다.

# 입력
nums   = [2, 7, 11, 15]
target = 9

# 출력
[(0, 1)]
# nums[0] + nums[1] = 2 + 7 = 9

---

일단 이중 반복문부터 썼다

뼈대를 받았고, TODO 부분만 채웠다.

def find_two_sum_pairs(nums, target):
    pairs = []
    n = len(nums)

    for i in range(n):
        for j in range(n):          # ← 여기가 문제
            if nums[i] + nums[j] == target:
                pairs.append((i, j))

    return pairs

동작은 한다. 근데 결과가 이상했다.
nums = [2, 7, 11, 15], target = 9로 테스트했더니

[(0, 1), (1, 0)]

(0, 1)은 맞다. 근데 (1, 0)은 뭐지.
2 + 7이나 7 + 2나 합은 9지만, 같은 쌍을 두 번 센 거다.
문제는 i < j를 지키라고 했는데, range(n)으로 쓰면 j가 i 앞으로도 간다.

---

버그가 2개 있었다

① for j in range(n) → range(i+1, n) (핵심 버그)

지금 이렇게 되어 있으면 j는 0부터 n-1까지 전부 돈다.
그래서 이런 일이 생긴다.

(i, j)	합	문제
(0, 0)	2 + 2 = 4	자기 자신과의 합
(0, 1)	2 + 7 = 9 ✅	정답 — 여기만 원했다
(1, 0)	7 + 2 = 9	(0, 1)과 같은 쌍 중복

j를 항상 i 뒤에서 시작하면 이 문제가 사라진다.
for j in range(n) 을 for j in range(i+1, n) 으로 바꾸면 된다.

# j가 i+1부터 시작하면
# → j는 항상 i보다 크다 (i < j 조건 자동 만족)
# → 자기 자신과의 비교 없음
# → 중복 쌍 없음

for i in range(n):
    for j in range(i+1, n):   # ← 핵심 수정

② pass 한 줄

pass는 공부용 자리표시자다. 구현이 완성됐으면 지워도 되고, 남겨도 동작에 영향은 없다.

---

최종 코드

BEFORE — 버그 있는 코드 for i in range(n): for j in range(n): if nums[i] + nums[j] == target: pairs.append((i, j))

AFTER — 수정된 코드 for i in range(n): for j in range(i+1, n): if nums[i] + nums[j] == target: pairs.append((i, j))

바뀐 건 딱 한 글자다.
range(n) → range(i+1, n).

함수 전체로 쓰면 이렇다.

def find_two_sum_pairs(nums, target):
    pairs = []
    n = len(nums)

    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                pairs.append((i, j))

    return pairs

---

코드가 하는 일을 한 번씩 보면

nums   = [2, 7, 11, 15]
target = 9

i=0 (값 2)
  j=1 → 2 + 7  = 9  ✅  (0, 1) 추가
  j=2 → 2 + 11 = 13
  j=3 → 2 + 15 = 17

i=1 (값 7)
  j=2 → 7 + 11 = 18
  j=3 → 7 + 15 = 22

i=2 (값 11)
  j=3 → 11 + 15 = 26

결과: [(0, 1)]

range(i+1, n) 이 왜 중복을 막는가

j는 항상 i보다 크다.
그래서 (0, 1)을 보면 (1, 0)은 볼 일이 없다.
또 j가 i에서 시작하지 않으니 (0, 0) 같은 자기 자신과의 비교도 없다.

# j 시작점 비교
range(n)       # 0, 1, 2, 3 ... → i보다 작은 인덱스도 포함
range(i+1, n)  # i+1, i+2  ... → 항상 i 뒤에서만 시작

---

전체 테스트

# 테스트 케이스 1
nums   = [2, 7, 11, 15]
target = 9
# [(0, 1)]   → nums[0]+nums[1] = 2+7 = 9

# 테스트 케이스 2
nums   = [1, 3, 4, 2, 5, 6]
target = 7
# [(0, 5), (1, 3), (2, 4)]
# 1+6=7, 3+4=7, ... 잠깐, 직접 확인해보자
# i=0: j=1→4, j=2→5, j=3→3, j=4→6, j=5→7✅ (0,5)
# i=1: j=2→7✅ (1,2), j=3→5, j=4→8, j=5→9
# i=2: j=3→6, j=4→9, j=5→10
# i=3: j=4→7✅ (3,4), j=5→8
# i=4: j=5→11
# 결과: [(0,5), (1,2), (3,4)]

# 테스트 케이스 3
nums   = [1, 1, 1, 1]
target = 2
# [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]  → 6개
# nC2 = 4*3/2 = 6

---

시간복잡도

코드 구조	복잡도	이유
for i in range(n)	O(n)	한 번 훑기
for i → for j (이중 반복문)	O(n²)	n × n 가까이 비교
정렬 sort()	O(n log n)	비교 대상

이 코드는 이중 반복문이니까 O(n²)다.
정확히는 n(n-1)/2번 비교하지만, 빅오 표기에서 상수는 버리니까 O(n²)으로 쓴다.

같은 문제를 dictionary를 써서 O(n)으로 줄이는 방법도 있다.
지금 단계에서는 완전 탐색 구조를 먼저 손에 익히는 게 중요하다.

---

기억해두면 쓸모 있는 패턴

배열에서 두 개를 골라 비교하는 문제는 거의 항상 이 구조다.

for i in range(n):
    for j in range(i+1, n):
        # nums[i], nums[j]로 무언가 한다

두 수의 합, 두 점 사이 거리, 모든 쌍 비교.
range(i+1, n) 이 한 줄이 i < j 조건을 자동으로 만족시켜준다.

---

마무리

버그의 원인은 반복 범위 하나였다.

range(n)으로 쓰면 j가 i보다 앞으로도 간다.
range(i+1, n)으로 쓰면 j는 항상 i 뒤에서만 시작한다.
이중 반복문을 쓸 때 안쪽 루프의 시작점이 어디인지 항상 의식하는 것.
이번 문제에서 가져가는 습관이다.

다음 문제로 넘어갔다.

🌿