[자료구조와 알고리즘] 2. 반복하는 알고리즘
본 포스팅은 “자료구조와 함께 배우는 알고리즘(파이썬)” 책 내용을 기반으로 작성되었습니다. 잘못된 내용이 있을 경우 지적해 주시면 감사드리겠습니다.
2-1. range() 함수로 이터러블 객체 생성하기
- range(n): 0 이상 n 미만인 수를 차례로 나열하는 수열
- range(a, b): a 이상 b 미만인 수를 차례로 나열하는 수열
- range(a, b, step): a 이상 b 미만인 수를 step 간격으로 나열하는 수열
2-2. 연속하는 정수의 합을 구하기 위해 값 정렬하기
print('a 부터 b 까지 정수의 합 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))
if a > b:
a, b = b, a # a와 b를 오름차순으로 정렬
sum = 0
for i in range(a, b+1):
sum += i
print(f'{a}부터 {b}까지 정수의 합은 {sum} 입니다.')
(결과) a 부터 b 까지 정수의 합 구합니다.
정수 a를 입력하세요.: 7
정수 b를 입력하세요.: 2
2부터 7까지 정수의 합은 27 입니다.
참고로 a, b = b, a 부분은 우변의 b, a에 의해 두 값을 압축한 튜플 (b, a) 가 생성된다. 대입 시 튜플 (b, a)를 다시 풀어 b, a로 만든 다음 각각 a와 b에 대입한다.
2-3. 반복 과정에서 조건 판단하기 1
print('a 부터 b 까지 정수의 합 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))
if a > b:
a, b = b, a
sum = 0
for i in range(a, b+1):
if i < b:
print(f'{i} + ', end='')
else:
print(f'{i} = ', end='')
sum += i
print(sum)
(결과) a 부터 b 까지 정수의 합 구합니다.
정수 a를 입력하세요.: 4
정수 b를 입력하세요.: 4
4 = 4
a 부터 b 까지 정수의 합 구합니다.
정수 a를 입력하세요.: 3
정수 b를 입력하세요.: 7
3 + 4 + 5 + 6 + 7 = 25
print('a부터 b까지 정수의 합을 구합니다.')
a = int(input('정수 a를 입력하세요.: '))
b = int(input('정수 b를 입력하세요.: '))
if a > b:
a, b = b, a
sum = 0
for i in range(a, b):
print(f'{i} + ', end='')
sum += i
print(f'{b} = ', end='')
sum += b
print(sum)
위 코드와 아래 코드의 결과는 같다. 그런데 a가 1이고 b가 10,000 일 때, for 문에서 10,000번 반복하는 동안 9,999번이 if 문을 거치고 마지막 1번이 else 문을 거친다. 즉, 마지막 1번 실행을 위해 조건문을 쓰게 되는 것이다. 이럴 거면 for 문 안에 있는 if 문을 제외하는 것이 좋다.
2-4. 반복 과정에서 조건 판단하기 2
print('+와 -를 번갈아 출력')
n = int(input('몇 개를 출력할까요?: '))
for i in range(n):
if i % 2:
print('-', end='')
else:
print('+', end='')
print()
(결과) +와 -를 번갈아 출력
몇 개를 출력할까요?: 5
+-+-+
print('+와 -를 번갈아 출력')
n = int(input('몇 개를 출력할까요?: '))
for _ in range(n // 2):
print('+-', end='')
if n % 2:
print('+', end='')
print()
마찬가지로 위, 아래 코드는 동일한 내용을 출력한다. 위 코드는 for 문을 반복할 때 마다 if 문을 수행한다. n이 50,000이면 if 문도 50,000번 수행한다. 아래 코드와 같이 수정하면 if 문을 마지막 한 번만 수행하면 된다.
2-5. 반복 과정에서 조건 판단하기 3
print('*를 출력합니다.')
n = int(input('몇 개를 출력할까요?: '))
w = int(input('몇 개마다 줄바꿈할까요?: '))
for i in range(n):
print('*', end='')
if i % w == w-1:
print()
if n % w:
print()
(결과) *를 출력합니다.
몇 개를 출력할까요?: 14
몇 개마다 줄바꿈할까요?: 5
*****
*****
****
print('*를 출력합니다.')
n = int(input('몇 개를 출력할까요?: '))
w = int(input('몇 개마다 줄바꿈할까요?: '))
for _ in range(n // w):
print('*' * w)
rest = n % w
if rest:
print('*' * rest)
이 코드도 위, 아래 모두 동일한 내용을 출력한다. 그러나 위 코드는 for 문을 반복할 때마다 if 문을 실행하므로 효율적이지 않다. 이를 개선한 코드가 아래 코드다.
2-6. 양수만 입력받기
print('1부터 n까지 정수의 합을 구합니다.')
while True:
n = int(input('n값을 입력하세요.: '))
if n > 0:
break
sum = 0
i = 1
for i in range(1, n + 1):
sum += i
i += 1
print(f'1부터 {n}까지 정수의 합은 {sum}입니다.')
(결과) 1부터 n까지 정수의 합을 구합니다.
n값을 입력하세요.: -6
n값을 입력하세요.: 0
n값을 입력하세요.: 10
1부터 10까지 정수의 합은 55입니다.
while 문 조건식에 True가 사용된 것은 무한 반복되도록 만든 것으로, 무한 루프 라고 한다. 여기서는 반복문 안에서 break 문을 실행하면 반복문을 종료할 수 있다는 점을 이용하여 무한 루프를 탈출했다. do~while 문이나 repeat~util 문 등은 사후 판단 반복문인데, 파이썬은 이러한 사후 판단문이 제공되지 않아 break 문을 사용하여야 한다.
그림 2-1. while 반복문 순서도
2-7. 직사각형 넓이로 변의 길이 구하기
area = int(input('직사각형의 넓이를 입력하세요.: '))
for i in range(1, area+1):
if i * i > area: break
if area % i: continue
print(f'{i} x {area // i}') # 짧은 변, 긴 변 순서로 출력
(결과) 직사각형의 넓이를 입력하세요.: 32
1 x 32
2 x 16
4 x 8
i x i가 area를 초과하면 사각형의 최대 넓이를 초과하면서도 가장 긴 변의 길이가 되므로 프로그램을 종료한다. 또한, area가 i로 나누어 떨어지지 않으면 i는 변의 길이가 될 수 없으므로, 출력할 필요가 없게 된다.
2-8. 반복문 건너뛰기와 여러 범위 스캔하기
건너뛰어야 하는 값을 모르거나 건너뛰어야 하는 값이 매번 변화할 때 if, continue 문 사용해야 한다.
for i in range(1, 13):
if i == 8:
continue
print(i, end=' ')
print()
(결과) 1 2 3 4 5 6 7 9 10 11 12
그러나 건너뛰는 값을 안다면 if문 쓸 필요없이 더 효율적인 프로그램이 있다.
for i in list(range(1, 8)) + list(range(9, 13)):
print(i, end=' ')
print()
(결과) 1 2 3 4 5 6 7 9 10 11 12
2-9. 비교 연산자를 연속으로 사용하는 방법과 드모르간 법칙
print('2자리 양수를 입력하세요.')
while True:
no = int(input('값을 입력하세요.: '))
if no >= 10 and no <= 99:
break
print(f'입력받은 양수는 {no} 입니다.')
조건문 if no>= 10 and no <= 99: 부분을 다른 방법으로 구현할 수 있다.
- 비교 연산자를 연속으로 사용
if 10 <= no <= 99: - 드모르간의 법칙 사용
if not(no < 10 or no > 99):
드모르간의 법칙은 각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다는 것이다! 이 법칙을 일반적으로 나타내면 다음과 같다.
- x and y와 not(not x or not y)의 논리값은 같다.
- x or y와 not(not x and not y)의 논리값은 같다.
참고로 구조적 프로그래밍이란 입력과 출력으로 이루어진 구성 요소를 계층으로 배치하여 프로그램을 구성하는 방법을 말한다. 순차, 선택, 반복이라는 세 종류의 제어 흐름을 사용한다.
2-10. 다중 루프 알아보기
- 구구단 곱셈표 출력
print('-'*27) for i in range(1, 10): for j in range(1, 10): print(f'{i * j:3}', end='') # i*j를 3자리로 출력한다! print() print('-' * 27)(결과) ————————— 1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81 —————————
- 직각 이등변 삼각형으로 출력하기 ```python print(‘왼쪽 아래가 직각인 이등변 삼각형을 출력합니다.’) n = int(input(‘짧은 변의 길이를 입력하세요.: ‘))
for i in range(n): for i in range(i+1): print(‘*’, end=’’) print()
(결과) 왼쪽 아래가 직각인 이등변 삼각형을 출력합니다.
짧은 변의 길이를 입력하세요.: 5
*
**
***
****
*****
```python
print('오른쪽 아래가 직각인 이등변 삼각형을 출력합니다.')
n = int(input('짧은 변의 길이를 입력하세요.: '))
for i in range(n):
for _ in range(n-i-1):
print(' ', end='')
for _ in range(i+1):
print('*', end='')
print()
(결과) 오른쪽 아래가 직각인 이등변 삼각형을 출력합니다.
짧은 변의 길이를 입력하세요.: 5
*
**
***
****
*****
2-11. 파이썬의 변수
파이썬에서는 데이터, 함수, 클래스, 모듈, 패키지 등을 모두 객체로 취급한다. 객체는 자료형을 갖고, 메모리를 차지한다. 이런 특징으로 파이썬의 변수는 값을 갖지 않는다는 특징이 있다. 쉽게 말하자면, x=17 에서 x가 17 값을 갖고 있다 말할 수 없다는 것이다.
- 변수는 객체를 참조하는 객체에 연결된 이름에 불과하다.
- 모든 객체는 메모리를 차지하고, 자료형뿐만 아니라 식별 번호를 갖는다.
Leave a comment