2. 반복 알고리즘

---

 

 

1. 반복 구조 (Repetition Structure)

어떤 조건이 성립하는 동안 프로그램 명령문이나, 명령어의 집합을 반복 처리하는 구조를 반복 구조라고 부른다.

일반적으로 루프(Loop)라고 부른다.

 

1.1) 판단 반복 구조

조건식을 이용하여 반복을 계속할 것인지 판단하는 반복 구조를 판단 반복 구조라고 부른다.

사전 판단 반복 구조와 사후 판단 반복 구조로 구분된다.

 

---

 

2. 1~n까지 정수 합 구하기

정수 n을 입력받아 1부터 n까지의 정수 합(1+2+3+4+~+n)을 구하는 알고리즘을 구현해보자.

python이 지원하는 반복문은 for문과 while문이 있다.

이 2가지 방법을 모두 활용해 구현해보자.

 

2.1) while 문을 사용하여 구현하기

### 1~n까지의 합 계산하기(while문 사용) ###

print('1~n까지의 합 계산')

n = int(input("Input Num: ")    ## User Input

sum = 0
i = 1

while (i <= n):    ## i <= n 조건이 참일 경우,
    sum += i    ## 1부터 n까지 차례대로 sum 변수에 합산
    i += 1      ## 1~n까지 값 1씩 증가
    
print(f"Result: {sum}")

위 코드에서 알 수 있듯이, while문은 조건식이 평가 결과가 참인 경우 명령문을 반복하는 구조이다.

즉, 조건식이 참일 경우, 반복할 하위 명령문들을 반복한 뒤, 다시 조건식을 검사해 참인지 여부를 판단한다.

이 알고리즘의 프로그램 순서도는 다음과 같다.

순서도를 살펴보면 구조를 크게 다음과 같이 2가지 파트로 나눠서 볼 수 있다.

• 합을 구하는 준비 단계 (변수 초기화 단계)
• 루프 동작 단계 (while 문)

i 변수 값이 n 값 이하라면, i 값을 1만큼 증가시키면서 루프 본문(while 문 하위의 명령문들)을 실행한다. 

i는 카운터용 변수(counter)로써, 반복을 제어할 때 사용되는 변수이다.

여기서 while 문은 n의 값이 6일 경우, i의 값이 1부터 6까지 증가하므로, 총 6번 반복된다.

단, while문의 조건식은 조건식 값이 거짓인 경우를 판별해야 하므로 총 7번 검사한다.

 

2.2) for 문을 사용해 구현하기

### 1~n까지의 합 계산하기(for문 사용) ###

print('1~n까지의 합 계산')

n = int(input("Input Num: ")    ## User Input

sum = 0
i = 1

for i in range(1, n+1):    ## i ~ n까지 i값을 1씩 증가; iterator
    sum += i    ## 1부터 n까지 차례대로 sum 변수에 합산
    
    
print(f"Result: {sum}")

while문으로 구현했던 부분을 for문으로 변경하였다.

python의 for문은 다른 언어의 일반적인 for문과 다르게 반복자(iterator)를 사용해 구현된다.

위 코드를 예시로 보면 다음과 같다.

for i in range(1, n+1) :

range(1, n+1)은 이터러블 객체(iterable object)로써, 반복할 수 있는 객체에 해당한다.

즉, 개별 원소를 반복적으로 셀 수 있는 자료형을 사용하면, 초기값(1)부터 종료 값(n+1) 미만까지 지정해준 간격만큼 바뀐 값을 in 연산자 좌측에 있는 변수에 할당해준다.

여기서 만약 n이 6이라면, i의 값은 다음과 같이 변한다.

i = 1
i = 2
i = 3
i = 4
i = 5
i = 6

간격은 따로 설정해주지 않는 이상 1로 설정되며, 필요에 따라 음수 값을 넣어줄 수도 있다.

 

---

 

3. range( ) 함수를 이용한 이터러블 객체(iterable object) 생성

이터러블 객체(iterable object)는 반복할 수 있는 객체를 의미한다.

python에서 for문을 사용할 때 자주 볼 수 있는 range( ) 함수가 대표적이다.

이터러블 객체에는 이터러블 자료형을 추가해 사용할 수 있다.

이터러블 자료형은 개별 원소를 반복적으로 셀 수 있는 자료형을 의미한다.

python에 존재하는 이터러블 자료형은 list, tuple, dict, set, str 등이 있다.

 

---

 

4. 1부터 n까지 정수의 합 계산하기 (가우스 덧셈)

1부터 100까지의 합을 계산하는 식으로 유명한 '가우스 덧셈' 공식을 for문을 사용해 구현해보자.

가우스 덧셈 공식은 다음과 같다.

 

4.1) 연속하는 정수의 합 구하기

파트 4의 내용을 다시 정의하면 연속하는 정수의 합 구하기 알고리즘이라고 볼 수 있다.

### a부터 b까지의 정수 합 구하기(for문)

print('a부터 b까지의 정수 합 계산')

## User Input ##
a = int(input("a: "))
b = int(input("b: "))
## -- ##

if (a > b) :    ## a, b를 오름차순으로 정렬
    a, b = b, a

sum = 0

for i in range(a, b+1) :    ## a~b까지의 합 계산
    sum+= i
    
print(f"Result: {sum}")

만약 시작 값인 a가 종료 값인 b보다 큰 수가 들어가게 되면, 큰 수 ~ 작은 수까지의 합을 계산하는 오류가 발생한다.

이러한 경우를 대비해 a 값을 b 값보다 항상 작은 수가 되도록 유지하고자 a, b를 오름차순으로 정렬하는 조건문이 추가되었다.

 

4.2) 두 값 교환하기

python에서는 튜플 자료형(tuple)을 제공한다.

튜플은 배열과 유사하지만, 1번 지정된 값을 이후에 변경할 수 없는 자료형이다.

python에서는 이 튜플 자료형을 응용하여 2개의 변수 값을 손쉽게 변경할 수 있는 단일 대입문 기능을 제공한다.

a = 1
b = 4

print(a)
print(b)

a, b = b, a

print(a)
print(b)

## OUTPUT ##
1
4
4
1
## -- ##

튜플을 제공하지 않는 다른 언어에서 변수의 두 값을 변경하기 위해서는 임시 변수를 사용해야 한다.

물론 python에서도 이러한 방식을 사용할 수 있다.

a = 5
b = 3

print(a)
print(b)

temp = a
a = b
b = temp

print(a)
print(b)


## OUTPUT ##
5
3
3
5
## -- ##

위의 2가지 코드를 그림으로 표현하면 다음과 같다.

 

4.3) 반복 과정 출력하기 1

a부터 b까지의 정수 합을 계산하는 알고리즘을 구현할 때, 계산 과정을 수식으로 표현하도록 응용해보자.

3부터 7까지의 정수 합을 계산한다고 가정하면, 3 + 4 + 5 + 6 + 7 = 25가 출력되는 것이다.

계산이 진행되고 있는 중간 값 정수 뒤에는 +가 붙어서 출력돼야 하고, 마지막 값 정수 뒤에는 =이 붙어서 출력돼야 한다.

즉, 3부터 6까지는 +가 뒤에 붙고, 7에는 =이 붙어야 한다는 것이다.

### a부터 b까지의 정수 합 구하기(for문)

print('a부터 b까지의 정수 합 계산')

## User Input ##
a = int(input("a: "))
b = int(input("b: "))
## -- ##

if (a > b) :    ## a, b를 오름차순으로 정렬
    a, b = b, a

sum = 0

for i in range(a, b+1) :    ## a~b까지의 합 계산
    if (i < b) :
        print(f"{i} + ", end='')    ## 진행 중인 값
    elif (i >= b) :
        print(f"{i} = ", end='')    ## 최종값
    
print(sum)

코드 가독성을 위해 else 대신 elif를 사용했다. else로 작성해도 차이점은 없다.

여기서 a의 값을 3, b의 값을 7이라고 가정하면, for문은 총 5번 반복된다.

또한 if문의 검사 횟수도 총 5번이다.

즉, 반복문을 1번 돌 때마다 매번 if문의 조건을 검사하며 실행된다는 것이다.

이 반복 횟수를 좀 더 줄여서 최적화를 진행해보자.

 

4.4) 반복 과정 출력하기 2

알고리즘 자체는 1과 동일하다.

a부터 b까지의 정수 합을 구하는 과정과 정수의 합을 출력하는 알고리즘이다.

다만 계산 과정 출력을 담당하는 부분에 다음과 같이 약간의 수정이 필요하다.

for문을 돌면서 i값을 증가시키는 계산을 처리할 때마다 매번 if문으로 조건을 따지는 대신, 처음부터 + 기호가 붙어야 하는 범위를 하나로 묶어버리는 것이다.

a가 3, b가 7이라고 가정하면, 3부터 6까지는 + 기호가 붙어야 하며, 최종 값인 7은 = 기호가 붙어야 한다.

조건을 따지지 않아도 3부터 6까지 + 기호가 붙는 것은 고정된 결과이므로, if 조건문 검사를 생략하면 된다.

### a부터 b까지의 정수 합 구하기(for문)

print('a부터 b까지의 정수 합 계산')

## User Input ##
a = int(input("a: "))
b = int(input("b: "))
## -- ##

if (a > b) :    ## a, b를 오름차순으로 정렬
    a, b = b, a

sum = 0

for i in range(a, b) :    ## a~b-1까지의 합 계산
    print(f"{i} + ", end='')
    sum += i
    
print(f"{b} = ", end='')
sum += b

print(sum)

이제 for문은 총 n-1번 수행되며, if문 판단은 1번만 수행된다.

 

4.5) 특정 문자를 줄 바꿈 없이 번갈아가며 출력하는 알고리즘 1

사용자가 입력한 횟수만큼 + 기호와 - 기호를 번갈아가면서 출력해주는 알고리즘을 구현해보자.

위 과정에서 봤던 것처럼 if문을 사용해 매번 어떤 기호를 출력해야 하는지 검사해 출력하는 방법이 가장 기본적인 방법일 것이다.

### +와 -를 번갈아 출력하기 ###

print("+와 -를 번갈아 출력하는 알고리즘")

n = int(input("몇 개를 출력할까요?: "))    ## User Input

for i in range(n) :
    if (i % 2) :    ## 홀수인 경우 - 출력
        print('-', end='')
    else :          ## 짝수인 경우 + 출력
        print('+', end='')

print()

for문을 반복할 때마다 if문 또한 반복된다.

이렇게 구현하면 구현 난이도는 낮지만, 상황에 따라 유연한 대처가 어려워진다는 단점이 생긴다.

즉, i의 범위를 바꾸면, 홀수와 짝수의 순서도 바뀌어버릴 수 있다.

이 문제를 해결하려면 다음과 같이 +- 기호 세트를 한꺼번에 출력하도록 묶어버리면 된다.

 

4.6) 특정 문자를 줄 바꿈 없이 번갈아가며 출력하는 알고리즘 2

for문이 '+-'를 (n//2) 번 출력하도록 수정한다.

### +와 -를 번갈아 출력하기 ###

print("+와 -를 번갈아 출력하는 알고리즘")

n = int(input("몇 개를 출력할까요?: "))    ## User Input

for _ in range(n//2) :
    print("+-", end='')    ## +- 세트를 짝수 개만큼 출력

if (n % 2) :
    print('+', end='')    ## 값이 홀수라면, + 기호를 끝에 추가

print()

 

4.7) 특수 문자를 n번 출력하되, w개마다 줄 바꿈을 적용하는 알고리즘 1

위에서 진행한 +, - 기호를 반복 출력하는 알고리즘을 변형하였다.

이제는 w개만큼의 특수 문자가 출력되면, 줄 바꿈을 적용한다.

### *를 n개 출력하되, w개마다 줄바꿈하기 ###

print("*를 n개 출력하되, w개마다 줄바꿈하기")

## User Input ##
n = int(input("몇 개 출력할까요?: "))
w = int(input("몇 개마다 줄바꿈할까요?: "))
## -- ##

for i in range(n) :
    print('*', end='')
    
    if (i % w == w - 1) :    ## n번 판단
        print()    ## 줄바꿈
    
if (n % w) :    ## 1번 판단
    print()    ## 줄바꿈

for문이 n번 반복되면, if문 판단도 n번 반복된다.

줄 바꿈을 적용하기 위해 사용되는 아래 if문의 동작 원리는 다음과 같다.

if (i % w == w - 1) :    ## n번 판단
        print()    ## 줄바꿈

n이 15이며, w가 5일 때, 현재 i 값이 9라고 가정한다.

if문의 조건식에 값을 대입해 계산해보면 다음과 같은 수식이 나온다.

9 % 5 == 5 - 1

위 수식의 결과는 참이므로, 줄 바꿈이 적용된다.

 

4.8) 특수 문자를 n번 출력하되, w개마다 줄 바꿈을 적용하는 알고리즘 2

먼저 특수 문자 *를 먼저 n // w개만큼 출력한다.

만약 n이 15이며 w가 5일 경우, 15 // 5 == 3이므로, w개만큼 꽉 채워서 *을 1줄에 출력하게 되는 일종의 '세트'는 총 3개가 나온다.

만약 n이 14이며 w가 5일 경우, 14 // 5 == 2이므로, w개만큼 꽉 채워서 *을 1줄에 출력하게 되는 일종의 '세트'는 총 2개가 나온다.

이때, 출력해야 하는 전체 *의 개수인 n은 14이므로, 나머지 4개가 남게 된다.

이 나머지는 n % w 수식 계산으로 찾아낼 수 있다.

n // w개만큼 *의 '세트'를 출력한 뒤, 나머지 값을 찾기 위해 n % w의 값 존재 여부를 판별하는 if문을 추가한다.

만약 if문 조건이 참일 경우, 나머지 *가 존재함을 의미하므로, 나머지 *도 출력해준다.

### *를 n개 출력하되, w개마다 줄바꿈하기 ###

print("*를 n개 출력하되, w개마다 줄바꿈하기")

## User Input ##
n = int(input("몇 개 출력할까요?: "))
w = int(input("몇 개마다 줄바꿈할까요?: "))
## -- ##

for _ in range(n // w) :    ## n//w번 반복
    print('*' * w)    ## 특수 문자를 w개만큼 한꺼번에 출력

rest = (n % w)    ## 출력해야 하는 나머지

if (rest) :    ## 1번 판단
    print('*' * rest)    ## 나머지 출력 분 출력

 

---

 

---

수고하셨습니다!

---