01-2 반복하는 알고리즘

1부터 n까지 정수의 합 구하기

1부터 n까지 정수의 합을 구하는 알고리즘을 알아본다.

• while 문 반복 알아보기
  - 반복 구조 (repetition structure)
    : 어떤 조건이 성립하는 동안 반복해서 처리 (프로그램 명령문 또는 명령어의 집합)하는 것
      → 일반적으로 루프 (loop)라고 한다.
  - 사전 판단 반복 구조
    : while 문은 실행하기 전에 반복을 계속할 것인지 판단하는 구조
  

  while 조건식: 명령문
  
  # 명령문을 루프 본문이라고 한다.

  
  - 카운터용 변수
    : 반복을 제어할 때 사용하는 i
  
  
• for 문 반목 알아보기
  - 변수가 하나만 있을 때는 while 문보다 for 문을 사용하는 것이 좋다.
  
  cf) 가우스의 덧셈으로도 1부터 n까지 정수의 합을 구할 수 있다.
  

  # 가우스(gauss) 덧셈
  # 1부터 n까지 정수의 합은 수학식 n x (n + 1) / 2
  
  sum = n * (n + 1) // 2​

   
• range( ) 함수로 이터러블 객체 생성
  - range(n)
    : 0 이상 n 미만인 수를 차례로 나열하는 수열
  - range(a, b)
    : a 이상 b 미만인 수를 차례로 나열하는 수열
  - range(a, b, step)
    : a 이상 b 미만인 수를 step 차례로 나열하는 수열

 

연속하는 정수의 합을 구하기 위해 값 정렬하기

연속하는 정수의 합을 구할 때 시작하는 값이 1이 아닌 정수를 입력받았다면 range( ) 함수에 전달할 시작 값과 끝 값을 오름차순으로 정렬해야 한다.

# a와 b를 오름차순으로 정렬

if a > b:
    a, b = b, a    # a와 b의 값을 교환 (단일 대입문 사용)

cf) 두 값 교환하기 2
     - 임시용 변수 t를 이용하여 a와 b 값을 교환할 수도 있다.
       1. a값을 t에 저장한다. (t = a)
       2. b값을 a에 대입한다. (a = b)
       3. t에 저장한 처음 a값을 b에 대입한다. (b = t)

 

반복 과정에서 조건 판단하기 1

a부터 b까지 정수의 합을 구하는 과정과 최종 값을 출력하는 프로그램

for i in range(a, b + 1):  # b - a번 반복
    if i < b:              # i가 b보다 작으면 합을 구하는 과정을 출력
        print(f'{i} + ', end='')
    else:                  # i가 b보다 크거나 같으면 최종값 출력을 위해 i =를 출력
        print(f'{i} = ', end='')
    sum += i               # sum에 i를 더함

- 문제점
  1.  반복 횟수가 많아지면 else문 실행을 위해 if문 실행이 많아진다.

- 해결 방법
   1.  for 문 안에 있는 if 문을 제외하여 별도로 두는 것이 좋다.

for i in range(a, b):
    print(f'{i} + ', end='')
    sum += i  # sum에 i를 더함

print(f'{b} = ', end ='')
sum += b      # sum에 b를 더함

→ 판단 횟수가 n번에서 0번으로 바뀌고, 심지어 반복 횟수도 1번 감소했다.

 

반복 과정에서 조건 판단하기 2

특정 문자를 줄바꿈 없이 연속으로 출력하는 프로그램

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

- 문제점
  1. for 문을 반복할 때마다 if 문을 수행한다.
  2. 상황에 따라 유연하게 수정하기 어렵다.

 

- 해결 방법

for _ in range(n // 2):
    print('+-', end='')  # n // 2개의 +-를 출력

if n % 2:
    print('+', end='')  # n이 홀수일 때만 +를 출력

- 결론
  1. 반복문에서 if 문을 수행하지 않는 것이 효율적이다.
  2. 나눗셈도 총 2번 수행된다.
  3. 카운터용 변수를 0에서 1로 변경해도 유연하게 대응할 수 있다.

 

반복 과정에서 조건 판단하기 3

*를 n개 출력하되 w개마다 줄 바꿈 하는 프로그램

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

if n % w:
    print()             # 줄바꿈

- 문제점
  1. for 문을 반복할 때마다 if 문을 실행하므로 효율적이지 않다.

- 해결 방법

for _ in range(n // w):  # 반복 n // w번 반복
    print('*' * w)

rest = n % w
if rest:
    print('*' * rest)  # if 문 1번 판단

- 결론
  1. print( ) 함수를 2단계로 실행한다.

 

양수만 입력받기

입력하는 n값을 양수로 한정한다.

while True:
    n = int(input('n값을 입력하세요.: '))
    if n > 0:
        break  # n이 0보다 커질 때까지 반복

• 무한 루프와 break 문 알아보기
  - 무한 루프 (infinite loop)
    : while 문의 조건식에 True가 사용된다.
  - break 문
    : 반복문 안에서 break 문을 실행하면 반복문을 종료할 수 있다.

cf) for 문이 종료된 이후 카운터용 변수 i값 살펴보기

while i <= n:                        # 반복을 종료할 때 i는 n + 1 
for i in range(시작값, n + 1)        # 반복을 종료할 때는 i는 n

 

직사각형 넓이로 변의 길이 구하기

• 변의 길이와 넓이가 모두 정수인 직사각형에서의 변의 길이를 구하는 프로그램
  

  for i in range(1, area + 1):  # 1부터 사각형의 넓이 계산
      if i * i > area: break
      if area % i: continue​

  → 약수를 나열하는 프로그램
• else 문이 뒤따르는 for 문을 구현한 프로그램
  

  for _ in range(n):
      r = random.randint(10, 99)
      print(r, end=' ')
      if r == 13:
          print('\n프로그램을 중단합니다.')
          break
  else :
      print('\n난수 생성을 종료합니다.')​

  cf) 난수를 생성하는 random.randint( ) 함수 알아보기
       - random.randint(a, b)
         : a 이상 b 이하인 난수를 생성하여 (a 이상 b 이하인 정수 가운데 무작위로 1개를 뽑아) 반환한다. 

 

반복문 건너뛰기와 여러 범위 스캔하기

for 문을 반복하는 과정에서 특정 조건일 때 반복문을 건너뛰도록 만들 수 있다.

for i in range(1, 13):
    if i == 8:
        continue
    print(i, end=' ')

- 문제점
  1. 비용이 많이 든다.
  2. 건너뛰어야 하는 값을 모르거나, 건너뛰어야 하는 값이 변화한다면 매번 if, continue 문을 사용해야 한다.

- 해결 방법

for i in list(range(1, 8)) + list(range(9, 13)):
    print(i, end=' ')

- 결론
  1. 단순히 리스트를 이용하여 8을 건너뛰었다.
  2. 다만 for 문은 생성한 리스트 원소를 하나씩 꺼내 반복하므로 반복을 위한 연산 비용은 여전히 발생한다.

 

비교 연산자를 연속으로 사용하는 방법과 드모르간의 법칙

2자리 양수를 입력받는 프로그램

while True:
    no = int(input('값을 입력하세요.: '))
    if no >= 10 and no <= 99:
        break

• 비교 연산자를 연속으로 사용한 방법
  : 연속으로 사용한 비교 연산자는 'and 결합'으로 취급하여 간결하게 구현할 수 있다.

  while True:
      no = int(input('값을 입력하세요.: '))
      if 10 <= no <= 99:
          break​

   
• 드모르간의 법칙을 사용한 방법
  : 논리 부정 연산자인 not 연산자를 사용한다.

  while True:
      no = int(input('값을 입력하세요.: '))
      if not(no < 10 or no > 99):
          break​

  - 드모르간의 법칙 (De Morgan's laws)
    : 각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.
    1. x and y와 not(not x or not y)의 논릿값은 같다.
    2. x or y와 not(not x and not y)의 논릿값은 같다.

cf) 구조적 프로그래밍 (structured programming)
     : 입력과 출력으로 이루어진 구성 요소를 계층으로 배치하여 프로그램을 구성하는 방법
       - 순차, 선택, 반복이라는 세 종류의 제어 흐름을 사용한다.

 

다중 루프 알아보기

• 구구단 곱셈표를 출력하는 프로그램

  for i in range(1, 10):      # 행 루프
      for j in range(1, 10):  # 열 루프
          print(f'{i * j : 3}', end='')
      print()                 # 행 변경​​

   
• 직각 이등변 삼각형으로 출력하기
  - 이중 루프를 응용하면 특수 문자로 표현한 삼각형이나 사각형을 출력할 수 있다.

  # 왼쪽 아래가 직각인 이등변 삼각형
  
  for i in range(n):          # 행 루프
      for j in range(i + 1):  # 열 루프
          print('*', end='')
      print()

  # 오른쪽 아래가 직각인 이등변 삼각형
  
  for i in range(n):              # 행 루프
      for _ in range(n - i - 1):  # 열 루프(공백을 출력)
          print(' ', end='')
      for _ in range(i + 1):
          print('*', end='')      # 열 루프(*을 출력)
      print()​

  
   

파이썬 변수 알아보기

- 파이썬에는 데이터, 함수, 클래스, 모듈, 패키지 등을 모두 객체 (object)로 취급한다.
- 객체는 자료형 (data type)을 가지며 메모리 (저장 공간)를 차지한다.

- 파이썬은 이런 특징 때문에 파이썬의 변수는 값을 갖지 않는다는 특징이 있다.

- 정리
  1. 변수는 객체를 참조하는 객체에 연결된 이름에 불과하다.
  2. 모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 식별 번호 (identity)를 가진다.

 

cf) 리터럴 (literal)
    : 값 자체를 의미한다. 즉, 문자 자체에 의해 값이 주어지는 문자열이다.

n = 1      # 전역 변수(함수 내부·외부에서 사용)
def put_id():
    x = 1  # 지역 변수(함수 내부에서만 사용)
    print(f'id(x) = {id(x)}')
    
print(f'id(1) = {id(1)}')
print(f'id(n) = {id(n)}')
put_id()

# 실행 결과
id(1) = 140706258954032
id(n) = 140706258954032
id(x) = 140706258954032

- 변수
  1. 전역 변수 (global variable)
     : 함수 외부에서 정의한 변수 (프로그램 전체에서 사용할 수 있다)
  2. 지역 변수 (local variable)
     : 함수 내부에서 정의한 변수 (함수 내부에서만 사용할 수 있다)

 

- 파이썬에서는 함수가 시작하고 종료함에 따라 객체가 생성되거나 소멸하지 않는다.

# [Do it! 실습 1C-5] 1부터 100까지 반복하여 출력

for i in range(1, 101):
    print(f'i = {i:3}   id(i) = {id(i)}')
    
    
# 실행 결과
i =   1   id(i) = 140706258954032
i =   2   id(i) = 140706258954064
i =   3   id(i) = 140706258954096
i =   4   id(i) = 140706258954128
(...생략...)

- 결론
  1. i의 값과 식별 번호 둘 다 갱신 (즉, i가 1씩 늘어날 때마다 참조하는 곳도 갱신)된다는 것을 실행 결과에서 알 수 있다.