← 브론즈 III

중첩 반복문

반복문 안의 반복문으로 격자와 쌍을 순회한다.

기초 & 구현

브론즈 III

선수 지식: 반복문

1강 중첩 반복문의 개념 공식

중첩 반복문이란?

반복문 안에 또 반복문이 들어간 구조입니다. 격자(표)를 훑거나, 모든 쌍을
검사하거나, 도형을 그릴 때 필수입니다.

1. 기본 모양

for (int i = 0; i < 3; i++) {       // 바깥 반복 (행)
    for (int j = 0; j < 3; j++) {   // 안쪽 반복 (열)
        cout << i << ',' << j << ' ';
    }
    cout << '\n';
}

출력:

0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,1 2,2

바깥이 한 바퀴 돌 때마다 안쪽이 처음부터 끝까지 전부 돕니다. 즉 안쪽은
바깥 횟수만큼 반복됩니다.

for i in range(3):
    for j in range(3):
        print(f"{i},{j}", end=' ')
    print()

2. 어떤 일에 쓰나

격자 순회 : 2차원 배열의 모든 칸을 방문 (i=행, j=열).
모든 쌍 검사 : N개 중 두 개를 고르는 모든 조합.
도형 출력 : 별 찍기 등(바깥=줄, 안쪽=그 줄의 글자).

// 모든 쌍 (i < j) 검사
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == target) ...

j를 i+1부터 시작하면 같은 쌍을 두 번 세지 않습니다.

3. 복잡도 — 곱해진다!

바깥 $$N$$ 번, 안쪽 $$M$$ 번이면 안쪽 본문은 $N \times M$ 번 실행됩니다.

구조	실행 횟수
2중 반복 ( $N \times N$ )	$$O(N^2)$$
3중 반복	$$O(N^3)$$

$$N = 1000$$ 이면 $$N^2 = 10^6$$ 으로 괜찮지만, $$N = 100000$$ 이면 $N^2 = 10^{10}$ 으로
시간 초과입니다. 중첩 깊이가 늘수록 N의 한계가 급격히 작아진다는 점을 꼭
기억하세요.

정리

반복문 안의 반복문 — 바깥 한 바퀴마다 안쪽 전체 실행.
격자 순회, 모든 쌍, 도형 출력에 쓰인다.
복잡도는 곱해진다 — 2중이면 $$O(N^2)$$ .
N이 크면 중첩 반복은 시간 초과 위험.

2강 중첩 반복문 구현과 연습 공식

중첩 반복문 구현 레퍼런스

격자 처리와 모든 쌍 검사 패턴을 코드로 정리하고, 흔한 함정을 짚습니다.

1. 2차원 격자 채우고 처리하기

int n, m; cin >> n >> m;
int a[100][100];
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];

long long sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        sum += a[i][j];      // 전체 합
cout << sum << '\n';

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum(sum(row) for row in a))

2. 모든 쌍 중 최댓값/조건 검사

int best = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        best = max(best, abs(a[i] - a[j]));   // 두 수 차의 최대
cout << best << '\n';

best = 0
for i in range(n):
    for j in range(i + 1, n):
        best = max(best, abs(a[i] - a[j]))
print(best)

j를 i+1부터 두면 같은 쌍·자기 자신을 피합니다.

3. 구구단/곱셈표

for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++)
        cout << i * j << '\t';   // 탭으로 정렬
    cout << '\n';
}

4. 함정과 패턴 인식

줄바꿈 위치 — 격자/표 출력 시 줄바꿈은 안쪽 반복이 끝난 뒤 바깥에서.
변수 혼동 — 안쪽에서 i를 바꾸면 바깥이 꼬임. 안쪽은 j만 다루기.
복잡도 폭발 — N이 크면 2중·3중 반복이 시간 초과. N의 한계를 먼저 계산.
인덱스 범위 — i는 0~n-1, j는 0~m-1.

문제에 "N×M 격자", "모든 두 수의 쌍", "표를 출력", "행과 열" 같은 말이 보이면
중첩 반복문입니다.

정리

중첩 반복은 (1) 바깥=행/첫째, 안쪽=열/둘째, (2) 줄바꿈은 안쪽 종료 후 바깥에서,
(3) 모든 쌍은 j = i+1부터, (4) 복잡도가 곱해지므로 N 한계 확인 — 이 네 가지가
핵심입니다.

구조	실행 횟수
2중 반복 ( $N \times N$ )	$\(O(N^2)\)$
3중 반복	$\(O(N^3)\)$