04_반복문

Supplementary Materials

MIT OpenCourseWare - Intro to CS & Programming in Python

• 2. Branching & Iteration

1. 반복문의 개요

필요성

• 똑같은 작업이나 규칙적인 작업을 여러 번 수행해야 할 때,
• 코드를 복사·붙여넣기 하는 대신 효율적으로 처리하기 위함

제어 구조

• 순차 구조, 선택 구조와 함께 프로그램의 3대 제어 구조 중 하나

종류

• 횟수 제어 반복(for 문): 정해진 횟수만큼 반복 (예: 10번 출력)
• 조건 제어 반복(while 문): 특정한 조건이 만족되는 동안 계속 반복 (예: 정답을 맞힐 때까지)

2. while 반복문 (조건 반복)

while은 조건식(condition)이 True인 동안 코드 블록을 반복해서 실행한다.

while condition:
    # 반복할 코드

동작 순서

1. 조건식을 검사한다.
2. True이면 블록을 실행한다.
3. 다시 조건식을 검사한다.
4. False가 될 때까지 반복한다.

n = 0
 
while n < 5:
    print(n)  # 0, 1, 2, 3, 4
    n = n + 1

숲 탈출 예제

n = input("You're in the Lost Forest. Go left or right? ")
 
while n == "right":
    n = input("You're in the Lost Forest. Go left or right? ")
 
print("You got out of the Lost Forest!")

사용자가 "right"를 입력하는 동안 계속 질문하고, 다른 값을 입력하면 반복문을 빠져나온다.

주의사항

while에서는 조건이 항상 True이면 무한 반복(Infinite Loop)이 발생한다.

• 언젠가 False가 되도록 반복문 내부에서 관련 값을 변경하거나, break를 사용한다.

cf.

• Python에서는 특이하게도 while 루프에 else를 붙일 수 있다.
• else는 조건식이 False로 평가되면 실행된다.
• 만약 while loop가 break 문으로 종료되면 else는 무시된다.

3. for 반복문 (횟수 반복)

반복 횟수나 순회할 값의 범위를 알고 있을 때는 for가 편리하다.

# for 변수 in 시퀀스(리스트 등):
#	리스트나 range()의 항목들을 하나씩 가져와서 반복 실행한다.
 
for n in range(5):
    print(n)

range(start, stop, step)

수열을 생성하여 반복 횟수를 지정할 때 주로 사용한다.

range(start, stop, step)

• start: 시작값, 생략하면 0

• stop: 종료 기준값, 이 값은 포함하지 않음

• step: 증가 간격, 생략하면 1

• range(종료값): 0부터 종료값-1까지 생성 (종료값은 포함되지 않는다.)

• range(시작값, 종료값): 시작값부터 종료값-1까지 생성

• range(시작값, 종료값, 증가값): 간격을 두고 생성 (역순 가능)

예제

range(5)는 0, 1, 2, 3, 4를 생성한다. 따라서 위 코드는 앞의 while 예제와 같은 결과를 낸다.

mysum = 0
 
for i in range(7, 10):
    mysum += i
 
print(mysum)  # 7 + 8 + 9 = 24

mysum = 0
 
for i in range(5, 11, 2):
    mysum += i
 
print(mysum)  # 5 + 7 + 9 = 21

4. 흐름 제어 키워드

break

break는 현재 실행 중인 반복문을 즉시 종료한다.

mysum = 0
 
for i in range(5, 11, 2):
    mysum += i
    if mysum == 5:
        break
        mysum += 1
 
print(mysum)

첫 반복에서 i는 5이고 mysum도 5가 됩니다. 조건이 참이므로 바로 반복문을 종료한다.

• 출력 결과: 5
• break 다음의 mysum += 1은 실행되지 않음
• 중첩 반복문에서는 가장 안쪽 반복문 하나만 종료

continue

continue는 현재 반복을 건너뛰고 다음 반복을 시작한다.

5. 반복문 활용

for와 while의 선택

while은 조건 중심, for는 범위·횟수 중심의 반복문이다.

for	while
반복 횟수나 범위를 알고 있을 때 적합	언제 끝날지 미리 알기 어려울 때 적합
반복 변수가 자동으로 변경됨	조건에 사용하는 값을 직접 변경해야 함
break로 조기 종료 가능	break로 조기 종료 가능
대부분 while로 다시 작성 가능	항상 자연스럽게 for로 바꿀 수 있는 것은 아님

중첩 반복문

중첩 반복문(Nested Loop)

• 반복문 안에 또 다른 반복문이 있는 구조
• 다차원 데이터 처리, 복잡한 패턴 출력, 모든 경우의 수(조합) 계산 등에 사용된다.

리스트 - for문의 기초

리스트(List)

• 여러 데이터를 묶어서 저장하는 자료구조
• 인덱스: 0부터 시작하며, list[0] 등으로 접근한다.
• 동적 추가: list.append(값)을 통해 항목을 추가할 수 있다.

---

cf. 실습

에라토스테네스의 체 (Sieve of Eratosthenes)

• 지정한 범위(1부터 $n$까지) 내의 모든 소수(Prime Number)를 빠르고 효율적으로 구하는 대표적인 알고리즘이다.
• 마치 체로 쳐서 불필요한 합성수를 걸러내고 소수만 남기는 방식이라 이런 이름이 붙었다.

동작 원리

1. 2부터 n까지의 모든 숫자를 준비한다.
2. 아직 지워지지 않은 가장 작은 수 $p$를 찾는다. ($p$는 소수이다.)
3. $p$를 제외한 $p$의 배수들을 모두 지운다.
4. $p$의 제곱($p^2$)이 $n$보다 작거나 같을 때까지 2~3 과정을 반복한다.
5. 남은 모든 수가 소수가 된다.

def sieve_of_eratosthenes(n):
    # 0부터 n까지의 소수 여부를 저장하는 리스트 (초기값은 모두 True)
    is_prime = [True] * (n + 1)
    
    # 0과 1은 소수가 아니므로 False로 설정
    is_prime[0] = is_prime[1] = False
    
    
    # 2부터 n의 제곱근까지만 확인하면 된다.
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # i가 소수라면, i의 배수들을 모두 False로 변경한다.
            # i * i 이전의 배수들은 이미 이전 단계에서 걸러졌으므로, i * i부터 시작한다.
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    # True로 남아있는 인덱스(소수)들을 리스트로 추출하여 반환한다.
    return [i for i in range(n + 1) if is_prime[i]]
 
# 사용 예시 (1부터 50까지의 소수)
print(sieve_of_eratosthenes(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

주요 최적화 포인트

제곱근까지만 탐색 (int(n**0.5) + 1 또는 math.isqrt(n) + 1)

• 어떤 수 $n$이 합성수라면, $n=a\times b$ 형태로 나타낼 수 있으며 두 인수 중 적어도 하나는 $\sqrt{n}$ 이하이다.
• 따라서 $\sqrt{n}$ 이하의 소수인 배수만 제거하면 $n$ 이하의 모든 합성수가 걸러진다.

배수 지우기 시작 위치 (i * i)

• $i$의 배수를 지울 때 $i\times 2,i\times 3\dots$ 등은 $i$보다 작은 소수(2, 3 등)에 의해 이미 지워졌다.
• 따라서 $i\times i$부터 지우기 시작하면 불필요한 중복 연산을 줄일 수 있다.

복잡도

시간 복잡도: $O(N\log (\log N))$

• 거의 선형 시간($O(N)$)에 가까울 정도로 매우 빠르다.
• 코딩 테스트 등에서 특정 범위 안의 소수를 모두 구해야 할 때 최선의 선택이다. 공간 복잡도: $O(N)$
• n + 1 크기의 리스트가 필요하다.
• ($N$이 매우 크다면 메모리 사용량에 주의해야 한다.)