[1] 자료구조와 배열
1. 배열 개념 알아보기
배열을 사용하면 따로따로 흩어진 변수를 하나로 묶어서 사용할 수 있어 코드를 쉽고 효율적으로 작성할 수 있다.
# 2-1 python
# 학생 5명의 시험 점수를 입력받아 합계와 평균을 구하는 프로그램
print('학생 그룹 점수의 합계와 평균을 구합니다.')
score1 = int(input('1번 학생의 점수를 입력하세요. : '))
score2 = int(input('2번 학생의 점수를 입력하세요. : '))
score3 = int(input('3번 학생의 점수를 입력하세요. : '))
score4 = int(input('4번 학생의 점수를 입력하세요. : '))
score5 = int(input('5번 학생의 점수를 입력하세요. : '))
total = 0
total += score1
total += score2
total += score3
total += score4
total += score5
print(f'합계는 {total}점입니다.')
print(f'평균은 {total / 5}점입니다.')-----------------------------------------------------const sumAndAvg = (num1, num2, num3, num4, num5) => {
const scoreList = [num1, num2, num3, num4, num5];
let total = 0;
scoreList.forEach((score) => (total += score));
const avg = total / 5;
console.log(`합계는 ${total}점입니다.`);
console.log(`평균은 ${avg}점입니다.`);
};
sumAndAvg(1, 2, 3, 4, 5);
// 합계는 15점입니다.
// 평균은 3점입니다.학생 점수는 하나의 값을 저장하는 변수가 아니라 묶음 단위로 값을 저장하는 배열 ( array ) 이라는 자료구조로 다뤄야 한다.
배열에는 객체가 저장되며, 배열에 저장된 객체 하나하나를 원소라고 한다.
또한 각 원소는 0, 1, 2, ... 순으로 인덱스 ( index ) 를 부여 받는다.
파이썬에서 배열 원소의 자료형 ( type ) 은 int형, float형 등 어떤 것이라도 상관없다.
2. 리스트와 튜플 알아보기
파이썬에서는 배열을 리스트 ( list ) 와 튜플 ( tuple ) 로 구현할 수 있다.
리스트와 튜플은 데이터 컨테이너라고 하며, 비슷한 기능을 하는 듯하지만 원소를 변경할 수 있는지 없는지에 따라 차이가 있다.
1 ) 리스트의 기초
리스트는 원소를 변경할 수 있는 뮤터블 ( mutable ) list 형 객체이다.
리스트는 연산자 [ ] 안에 원소를 쉼표 ( , ) 로 구분하여 표기하여 생성할 수 있다.
list01 = []
list02 = [1, 2, 3]
list03 = ['A', 'B', 'C', ]
list04 = list()
list05 = list('ABC') # ['A', 'B', 'C']
list06 = list([1, 2, 3])
list07 = list((1, 2, 3))
list08 = list({1, 2, 3})
list09 = list(range(7)) # [0, 1, 2, 3, 4, 5, 6]
list10 = list(range(3, 8)) # [3, 4, 5, 6, 7]
list11 = list(range(3, 13, 2)) # [3, 5, 7, 9, 11]
list12 = [None] * 5 # [None, None, None, None, None]2 ) 튜플의 기초
튜플은 원소에 순서를 매겨 결합한 것으로 원소를 변경할 수 없는 이뮤터블 ( immutable ) 자료형이다.
튜플은 원소를 쉼표 ( , ) 로 구분하여 나열한 뒤 결합 연산자 ( )로 둘러싸는 방식으로 생성한다.
tuple01 = ()
tuple02 = 1,
tuple03 = (1, )
tuple04 = 1, 2, 3
tuple05 = 1, 2, 3,
tuple06 = (1, 2, 3)
tuple07 = (1, 2, 3, )
tuple08 = 'A', 'B', 'C',
tuple09 = tuple()
tuple10 = tuple('ABC') # ('A', 'B', 'C')
tuple11 = tuple([1, 2, 3])
tuple12 = tuple({1, 2, 3})
tuple13 = tuple(range(7))
tuple14 = tuple(range(3, 8))
tuple15 = tuple(range(3, 13, 2))3 ) 리스트와 튜플 풀어내기
리스트나 튜플의 원솟값들을 풀어 여러 변수에 대입하는 것을 언팩 ( unpack ) 이라고 한다.
x = [1, 2, 3]
a, b, x = x
a, b, c
(1, 2, 3)3. 인덱스로 원소에 접근하기
리스트나 튜플의 원소에 접근할 때는 인덱스 ( index )를 사용하면 된다.
1 ) 인덱스식 사용하기
x = [11, 22, 33, 44, 55, 66, 77]
x[2] # 33
x[-3] # 55
x[-4] = 3.14
x # [11, 22, 33, 3.14, 55, 66, 77]
x[7] # ERROR ( no index )
x[7] = 3. 14 # ERROR ( no index )각 인덱스에 값을 대입할 때는 인덱스식을 좌변에, 대입식을 우변에 놓는다.
인덱스 범위를 벗어나면 오류가 발생한다.
존재하지 않는 원소에 접근하거나 대입해도 원소가 새롭게 추가되지는 않는다.
4. 슬라이스식으로 원소에 접근하기
리스트 또는 튜플의 원소 일부를 연속해서 또는 일정한 간격으로 꺼내 새로운 리스트 또는 튜플을 만드는 것을 슬라이스 ( slice ) 라고 한다.
1 ) 슬라이스식으로 원소 꺼내기
s[i:j] ... s[i]부터 s[j-1]까지 나열한다.
s[i:j:k] ... s[i]부터 s[j-1]까지 k씩 건너뛰며 나열한다.s = [11, 22, 33, 44, 55, 66, 77]
s[0:6] # [11, 22, 33, 44, 55, 66]
s[0:7] # [11, 22, 33, 44, 55, 66, 77]
s[0:7:2] # [11, 33, 55, 77]
s[-4:-2] # [44, 55]
s[3:1] # []2 ) 뮤터블과 이뮤터블의 대입
값이 변경되면 복사하는 것이 아니라 값을 참조하는 객체의 식별 번호가 변경된다.
이 원리로 어떤 자료형의 객체이든 상관없이 변수에 대입할 수 있다.
파이썬은 변수를 선언할 때 자료형을 선언하지 않더라도 변수 이름에 값을 대입하기만 하면 그 이름의 변수를 사용할 수 있도록 자료형을 자동으로 선언해주는 기능이 있다.
x = 6
y = 2
x, y = y + 2, x + 3
x # 4
y # 9두 대입식이 동시에 이루어지기 때문에 y의 값이 7이 아니라 9가 된다.
n = 12
id(n) # 140711199888768
n += 1
id(n) # 140711199888800n이 참조하는 곳이 int형 객체 12에서 13으로 업데이트되었다.
정수를 나타내는 int형과 문자열을 나타내는 str형은 값을 변경할 수 없다.
이렇게 값을 변경할 수 없는 특성을 이뮤터블 ( immutable )이라고 하며, 값을 변경할 수 있는 특성은 뮤터블 ( mutable ) 이라고 한다.
위의 예의 경우 int형 정수형 객체 12의 값 자체를 변경하는 것이 불가능하므로 다른 정수형 객체 13을 참조하도록 업데이트 했다.
※ 누적 변수 : 변숫값에 특정값을 더한 결괏값을 다시 대입하여 업데이트한 변수
5. 자료구조의 개념 알아보기
자료구조 ( data structure )는 논리적인 관계로 이루어진 데이터 구성을 말한다.
자료 구조 : 데이터 단위와 데이터 자체 사이의 물리적 또는 논맂거인 관계.즉, 자료구조는 데이터가 모여 있는 구조이다.
자료구조를 알아야 하는 이유는 컴퓨터에서 처리해야 하는 많은 데이터를 모아 효율적으로 관리하고 구조화하는 데 있다.
1 ) 리스트와 튜플 1
리스트나 튜플의 원소 수 ( 배열의 길이 ) 는 len() 함수로 구할 수 있다.
x = [15, 64, 7, 3.14, [32, 55], 'ABC']
len(x) # 6min(), max() 함수의 인수로 리스트나 튜플을 넘겨주면 그 리스트 또는 튜플이 가진 원소중에서 최솟값 또는 최댓값을 얻을 수 있다.
배열에 원소가 하나도 없는지 확인하고 싶다면 배열을 참조하는 변수를 조건식에 그대로 사용하면 된다.
배열의 대소 또는 등가 관계는 비교 연산자를 사용하여 판단한다.
다음 코드의 결과는 모두 True인 예이다.
[1, 2, 3] == [1, 2, 3]
[1, 2, 3] < [1, 2, 4]
[1, 2, 3, 4] <= [1, 2, 3, 4]
[1, 2, 3] < [1, 2, 3, 5]
[1, 2, 3] < [1, 2, 3, 5] < [1, 2, 3, 5, 6]맨 앞 원소부터 차례로 비교하면서 원소의 값이 같으면 다음 원소를 비교한다.
만약 어느 원소의 값이 크면 그 배열이 큰 것으로 판단한다.
또 배열의 원소 수가 다른 경우에는 원소 수가 많은 배열을 더 크다고 판단한다.
※ 등가성과 동일성은 다르다.
※ 등가성 비교는 ==을, 동일성 비교는 is를 사용한다.
※ 등가성 비교는 좌변과 우변의 값이 같은지 비교하는 것이다.
※ 동일성 비교는 값은 물론 객체의 식별 번호까지 같은지 비교한다.
2 ) 내포 표기 생성
리스트 안에서 for, if 문을 사용하여 새로운 리스트를 생성하는 기법을 내포 표기 생성이라 한다.
numbers = [1, 2, 3, 4, 5]
twise = [num * 2 for num in numbers if num % 2 === 1]
print(twise) # [2, 6, 10][2] 배열이란?
1. 배열 원소의 최댓값 구하기
def max_of(a):
maximum = a[0]
for i in range(1, len(a)):
if a[i] > maximum:
maximum = a[i]맨 처음 a[0]의 값에 주목하여 이를 maximum에 대입한다.
그 뒤 for 문에서는 a[1]~a[4]까지 차례대로 주목한다.
이와 같이 배열 원소를 하나씩 차례로 주목하여 살펴보는 방식을 알고리즘 용어로 스캔 ( scan ) 이라고 한다.
스캔 과정에서 if 문의 조건식이 True일 때, 즉 주목한 원소의 값이 최댓값인 maximum보다 크면 a[i]의 값을 maximum에 대입한다.
2. 배열 원소의 최댓값을 구하는 함수 구현하기
# 2-2
# 배열 원소의 최댓값을 구하는 함수
from typing import Any, Sequence
def max_of(a: Sequence) -> Any:
maximum = a[0]
for i in range(1, len(a)):
if a[i] > maximum:
maximum = a[i]
return maximum
if __name__ == '__main__':
print('배열의 최댓값을 구합니다.')
num = int(input('원소 수를 입력하세요. : '))
x = [None] * num
for i in range(num):
x[i] = int(input(f'x[{i}]값을 입력하세요. : '))
print(f'최댓값은 {max_of(x)}입니다.')-------------------------------------------------------------------------const getMaxInNumList = (numList) => {
console.log("배열의 최댓값을 구합니다.");
maximum = -999999999999999;
numList.forEach((num) => (maximum = maximum < num ? num : maximum));
console.log(`최댓값은 ${maximum}입니다.`);
};
getMaxInNumList([172, 153, 192, 140, 165]);
// 배열의 최댓값을 구합니다.
// 최댓값은 192입니다.2-2는 함수 어노테이션과 if name == 'main'에 따라 프로그램을 실행하도록 작성했다.
3. 주석과 자료형 힌트
2-2의 Any와 Sequence에 대해서 살펴보겠다.
Any는 제약이 없는 임의의 자료형을 의마하며, Sequence는 시퀀스형을 의미한다.
또한 시퀀스형에는 리스트형, 바이트 배열형, 문자열형, 튜플형, 바이트열형이 있다.
※ 파이썬에서는 자료형 선언 없이 변수나 함수를 자유롭게 사용할 수 있지만 명시적으로 해석하기 어려운 경우가 있다.
※ 그래서 등장한 기능이 어노테이션 ( annotation, 주석 달기 ) 이다.
※ 어노테이션은 말 그대로 주석 달기일 뿐이며, 코드 자체에는 어떠한 영향도 미치지 않는다.
4. 재사용할 수 있는 모듈 작성하기
파이썬에서는 하나의 스크립트 프로그램을 모듈 ( module ) 이라고 한다.
2-2 프로그램의 파일 이름을 max.py로 설정한다면 모듈 이름은 max 이다.
if name == 'main'에서 name은 모듈 이름을 나타내는 변수이고 작성 규칙은 다음과 같다.
스크립트 프로그램이 직접 실행될 때 변수 __name__은 '__main__'이다.
스크립트 프로그램이 임포트될 때 변수 __name__은 원래 모듈 이름이다.모든 것을 객체로 다루는 파이썬에서는 모듈도 당연히 객체이다.
따라서 if name == 'main'은 max.py를 직접 시작한 경우에만 실행한다는 것을 의미한다.
5. 모듈 테스트하기
# 2-3
# 배열 원소의 최댓값을 구해서 출력하기
from max import max_of
print('배열의 최댓값을 구합니다.')
print('주의: "End"를 입력하면 종료됩니다.')
number = 0
x = []
while True:
s = input(f'x[{number}]값을 입력하세요. : ')
if s == 'End':
break
x.append(int(s))
number += 1
print(f'{number}개를 입력했습니다.')
print(f'최댓값은 {max_of(x)}입니다.')모듈 max로 정의된 max_of() 함수를 사용할 수 있도록 임포트했다.
그리고 빈 리스트 x를 생성한다.
while문을 실행하고 사용자가 End를 입력하면 break 문이 작동하여 while 문을 종료한다.
하지만 입력받은 값이 End가 아니라면 입력받은 문자열을 int() 함수로 변환하고 배열 x에 차례대로 추가한다.
변수 number는 0으로 초기화한 뒤 정수를 입력받을 때마다 1씩 증가시킨다.
입력받은 정수의 개수는 배열 x의 원소 수와 일치된다.
1 ) 배열의 원솟값을 난수로 결정하기
# 2-4
# 배열 원소의 최댓값을 구해서 출력하기 ( 원솟값을 난수로 생성 )
import random
from max import max_of
print('난수의 최댓값을 구합니다.')
num = int(input("난수의 개수를 입력하세요. : "))
lo = int(input("난수의 최솟값을 입력하세요. : "))
hi = int(input("난수의 최댓값을 입력하세요. : "))
x = [None] * num
for i in range(num):
x[i] = random.randint(lo, hi)
print(f'{(x)}')
print(f'이 가운데 최댓값은 {max_of(x)}입니다.')-------------------------------------------------------------------------const getMaxInNumList = (numList) => {
maximum = -999999999999999;
numList.forEach((num) => (maximum = maximum < num ? num : maximum));
return maximum;
};
const randomInt = (low, high) => {
return Math.floor(Math.random() * (high - low)) + low;
};
const maxOfRandomNumbers = (number, low, high) => {
let newList = [];
for (let i = 0; i < number; i++) {
newList.push(randomInt(low, high));
}
console.log(newList);
console.log(`이 가운데 최댓값은 ${getMaxInNumList(newList)}입니다.`);
};
maxOfRandomNumbers(5, 10, 99);
// [ 72, 20, 28, 92, 37 ]
// 이 가운데 최댓값은 92입니다.2 ) 튜플, 문자열, 문자열 리스트의 최댓값 구하기
# 2-5
# 각 배열 원소의 최댓값을 구해서 출력하기 ( 튜플, 문자열, 문자열 리스트 )
import random
from max import max_of
t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']
print(f'{t}의 최댓값은 {max_of(t)}입니다.')
print(f'{s}의 최댓값은 {max_of(s)}입니다.')
print(f'{a}의 최댓값은 {max_of(a)}입니다.')3 ) 리스트와 튜플 2
따로따로 생성한 리스트에서 모든 원소의 값이 같아도 실체는 각각 다르다.
lst1 = [1, 2, 3, 4, 5]
lst2 = [1, 2, 3, 4, 5]
lst1 is lst2 # Falselst1과 lst2 모두 [1, 2, 3, 4, 5]로 같은 리스트를 생성한 것처럼 보이지만 이는 리터럴이 아니기 때문에 False가 나온다.
리스트를 2개 선언하여 서로 대입해도 원소 자체는 복사되지 않는다.
앞에서도 설명했듯이 대입에서 복사되는 것은 값이 아니라 참조하는 곳이기 때문이다.
lst1 = [1, 2, 3, 4, 5]
lst2 = lst1
lst1 is lst2 # True
lst1[2] = 9
lst1 # 1, 2, 9, 4, 5]
lst2 # 1, 2, 9, 4, 5]대입식 lst2 = lst1에서 lst2는 lst1을 참조하기 때문에 lst1에서 인덱스식으로 원솟값을 바꾸면 lst2의 원솟값도 바뀐다.
enumerate() 함수는 인덱스와 원소를 짝지어 튜플로 꺼내는 내장 함수이다.
인덱스값을 따로 지정하지 않아도 되는 이유는 리스트가 이터러블 객체, 곧 순차 반복 객체이기 때문이다.
x = ['John', 'George', 'Paul', 'Ringo']
# ver 1
for i in range(len(x)):
print(f'x[{i}] = {x[i]}')
# x[0] = John
# x[1] = George
# x[2] = Paul
# x[3] = Ringo
# ver 2
for i, name in enumerate(x):
print(f'x[{i}] = {name}')
# x[0] = John
# x[1] = George
# x[2] = Paul
# x[3] = Ringo
# ver 3
for i, name in enumerate(x, 1):
print(f'{i}번째 = {name}')
# 1번째 = John
# 2번째 = George
# 3번쨰 = Paul
# 4번째 = Ringo문자열, 리스트, 튜플, 집합, 딕셔너리 등의 자료형 객체는 모두 이터러블 ( 반복 가능 ) 하다는 공통점이 있다.
이터러블 객체는 원소를 하나씩 꺼내는 구조이며, 이터러블 객체를 내장 함수인 iter()의 인수로 전달하면 그 객체에 대한 이터레이터 ( 반복자 ) 를 반환한다.
6. 배열 원소를 역순으로 정렬하기
먼저 맨 앞 원소와 맨 끝 원소의 값을 교환한다.
이어서 각각 하나씩 안쪽의 원솟값을 교환하는 작업을 반복한다.
# 2-6
# 뮤터블 시퀀스 원소를 역순으로 정렬
from typing import Any, MutableSequence
def reverse_array(a: MutableSequence) -> None:
n = len(a)
for i in range(n//2):
a[i], a[n - i - 1] = a[n - i - 1], a[i]
if __name__ == '__main__':
print("배열 원소를 역순으로 정렬합니다.")
nx = int(input("원소 수를 입력하세요. : "))
x = [None] * nx
for i in range(nx):
x[i] = int(input(f'x[{i}]값을 입력하세요. : '))
reverse_array(x)
print('배열 원소를 역순으로 정렬했습니다.')
for i in range(nx):
print(f'x[{i}] = {x[i]}')--------------------------------------------------------const reverseArray = (arr) => {
console.log("배열 원소를 역순으로 정렬합니다.");
const len = arr.length;
for (let i = 0; i < Math.floor(len / 2); i++) {
const temp = arr[i];
arr[i] = arr[len - i - 1];
arr[len - i - 1] = temp;
}
console.log("배열 원소를 역순으로 정렬했습니다.");
arr.forEach((number, index) => console.log(`x[${index}] = ${number}`));
};
reverseArray([1, 2, 3, 4, 5, 6]);
// 배열 원소를 역순으로 정렬합니다.
// 배열 원소를 역순으로 정렬했습니다.
// x[0] = 6
// x[1] = 5
// x[2] = 4
// x[3] = 3
// x[4] = 2
// x[5] = 11 ) 리스트를 역순으로 정렬하기
리스트 자기 자신을 역순으로 정렬하려면 list형의 reverse( ) 함수를 사용할 수 있다.
x.reverse()reversed( ) 함수를 호출하는 reversed(x)는 x의 원소를 역순으로 정렬하는 이터러블 객체를 생성한다.
따라서, 어떤 리스트의 원소를 역순으로 정렬한다면, reversed( ) 함수가 반환하는 이터러블 객체를 list( ) 함수에 넘기고 새로운 리스트를 생성해야 한다.
y = list(reversed(x))7. 기수 변환하기 ( n진수 구하기 )
이번에는 정숫값을 임의의 기수로 변환하는 알고리즘을 살펴보겠다.
10진수 정수를 n진수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에 몫을 반복해서 나눠야 한다.
몫이 0이 될 때까지 이 과정을 반복하고 나머지를 역순으로 늘어놓으면 기수로 변환한 수가 된다.
1 ) 기수 살펴보기
n 진수는 n을 기수로 하는 수이다.
10진수 ( decimal )
다음과 같이 숫자 10종류를 사용하여 수를 나타낸다.
0 1 2 3 4 5 6 7 8 9
- 1자릿수 : 0~9
- 2자릿수 : 10 ~ 99
- 3자릿수 : 100 ~ 9998진수 ( octal )
다음과 같이 숫자 8종류를 사용하여 수를 나타낸다.
0 1 2 3 4 5 6 7
- 1자릿수 : 0 ~ 7
- 2자릿수 : 10 ~ 77
- 3자릿수 : 100 ~ 77716진수 ( hexadecimal )
다음과 같이 숫자 16종류를 사용하여 수를 나타낸다.
0 1 2 3 4 5 6 7 8 9 A B C D E F
- 1자릿수 : 0 ~ F
- 2자릿수 : 10 ~ FF
- 3자릿수 : 100 ~ FFF# 2-7
# 10진수 정숫값을 입력받아 2 ~ 36진수로 변환하여 출력하기
def card_conv(x: int, r: int) -> str:
d = ""
dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
while x > 0:
d += dchar[x % r]
x //= r
return d[::-1]
if __name__ == '__main__':
print("10진수를 n진수로 변환합니다.")
while True:
while True:
no = int(input("변환할 값으로 음이 아닌 정수를 입력하세요. : "))
if no > 0:
break
while True:
cd = int(input("어떤 진수로 변환할까요? : "))
if 2 <= cd <= 36:
break
print(f'{cd}진수로는 {card_conv(no, cd)}입니다.')
retry = input("한 번 더 변환할까요? ( Y ... 예 / N ... 아니요 ) : ")
if retry in {"N", 'n'}:
break---------------------------------------------------------------------------const convertNumber = (originNumber, target) => {
newCardinalNumber = [];
character = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
while (originNumber > 0) {
newCardinalNumber.push(character[originNumber % target]);
originNumber = Math.floor(originNumber / target);
}
return newCardinalNumber.reverse().join("");
};
console.log(`29는 2진수로 ${convertNumber(29, 2)}입니다.`);
// 29는 2진수로 11101입니다.x를 r로 나눈 나머지를 인덱스로 하는 문자, 곧 dchar[x % r]를 문자열 d에 추가한다.
문자열 dchar에는 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"이 들어있으므로 각 문자를 인덱스로 접근할 수 있다.
2 ) 함수 사이에 인수 주고받기
# 1부터 n까지 정수의 합 구하기
def sum_1ton(n):
s = 0
while n > 0:
s += n
n -= 1
return s
x = int(input('x의 값을 입력하세요. : '))
print(f'1부터 {x}까지 정수의 합은 {sum_1ton(x)}입니다.')sum_1ton( ) 함수의 실행 과정에서 매개변수 n의 값은 5 -> 4 -> ... 으로 1씩 감소한다.
함수가 종료할 때 n값은 0이다.
호출하는 곳에서 sum_1ton( ) 함수로 전달하는 실제 인수는 x이다.
변수 x의 값 ( 5 ) 은 호출하기 전의 값 그대로인 것을 확인할 수 있다.
파이썬에서는 매개변수에 실제 인수가 대입된다.
int 타입은 이뮤터블 타입이기 때문에 변수 n의 값이 업데이트되는 시점에 다른 객체를 참조하게 된다.
파이썬에서 인수 전달은 실제 인수인 객체에 대한 참조를 값으로 전달하여 매개변수에 대입되는 방식이다.
다른 프로그래밍 언어에서는 실제 인수의 값을 매개변수에 복사하는 값에 의한 호출 ( call by value ) 을 사용하거나, 실제 인수의 참조를 매개변수에 복사하여 매개변수가 실제 인수와 같아지는 참조에 의한 호출 ( call by reference ) 을 사용한다.
하지만 파이썬에서는 이 2가지 호출의 중간적인 방식으로 참조하는 값을 전달한다.
파이썬 공식 문서에서는 객체 참조에 의한 전달 ( call by object reference ) 이라는 용어를 사용하여 설명하고 있다.
# 리스트에서 임의의 원솟값을 업데이트하기
def change(lst, idx, val):
lst [idx] = val
x = [11, 22, 33, 44, 55]
print('x =', x)
index = int(input('업데이트할 인덱스를 선택하세요. : '))
value = int(input("새로운 값을 입력하세요. : "))
change(x, index, value)
print(f'x = {x}')인수가 뮤터블하면 함수 안에서 업데이트한 값이 원래 호출한 곳으로 전달된다는 것을 알 수 있다.
8. 소수 나열하기
어떤 정수 이하의 소수 ( prime number )를 모두 나열하는 알고리즘을 살펴보겠다.
소수는 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수이다.
만약 나누어 떨어지는 정수가 하나 이상 존재하면 그 수는 합성수 ( composite number ) 이다.
# 2-8
# 1,000 이하의 소수를 나열하기
counter = 0
for n in range(2, 1001):
for i in range(2, n):
counter += 1
if n % i == 0:
break
else:
print(n)
print(f'나눗셈을 실행한 횟수 : {counter}')1 ) 9가 소수인지 판단하기
9는 i가 3일 때 나누어 떨어지므로 break 문이 동작하여 for 문의 반복이 중단된다.
2 ) 13이 소수인지 판단하기
13은 한 번도 나누어 떨어지지 않는다.
즉, n이 i로 나누어 떨어지는 경우가 한 번도 없고, 나눗셈은 모두 11번 실행된다.
- n이 소수일 때 : for 문은 마지막까지 실행된다.
- n이 합성수일 때 : for 문은 중단된다.이 프로그램은 불필요한 나눗셈을 계속 실행하고 있다.
3 ) 알고리즘 개선하기 1
# 2-9
# 1,000 이하의 소수를 나열하기 ( 알고리즘 개선 1 )
counter = 0
ptr = 0
prime = [None] * 500
prime[ptr] = 2
ptr += 1
for n in range(3, 1001, 2):
for i in range(1, ptr):
counter += 1
if n % prime[i] == 0:
break
else:
prime[ptr] = n
ptr += 1
for i in range(ptr):
print(prime[i])
print(f'나눗셈을 실행한 횟수 : {counter}')소수를 구하는 과정에서 지금까지 구한 소수를 배열 prime의 원소로 저장하도록 개선했다.
n이 소수인지 판단할 때 배열 prime에 저장한 소수로 나눗셈을 하면 된다.
주의할 점은, 2는 소수인 것이 분명하므로 2를 배열의 첫 원소인 prime[0]에 저장한다는 것이다.
4 이상의 짝수는 2로 나누어 떨어지므로 for문에서는 n값을 2씩 증가시켜 3, 5, 7,..., 999로 홀수의 값만 생성한다.
- 같은 결과 ( 해답 )를 얻을 수 있는 알고리즘은 여러 개일 수 있다.
- 빠른 알고리즘은 많은 메모리를 요구한다.4 ) 알고리즘 개선하기 2
넓이가 100인 직사각형의 가로, 세로 변의 길이를 생각해보자.
5 X 20과 20 X 5는 가로, 세로 변의 길이는 다르지만 같은 직사각형이다.
따라서 모든 직사각형은 정사각형인 10 X 10ㅇ을 경계로 대칭 구조를 이룬다.
직사각형 한 변의 길이만 나눗셈을 시도하고, 그 과정에서 한 번도 나누어 떨어지지 않으면 소수라고 판단해도 좋다.
# 2-10
# 1,000 이하의 소수를 나열하기 ( 알고리즘 개선 2 )
counter = 0
ptr = 0
prime = [None] * 500
prime[ptr] = 2
ptr += 1
prime[ptr] = 3
ptr += 1
for n in range(5, 1001, 2):
i = 1
while prime[i] * prime[i] <= n:
counter += 2
if n % prime[i] == 0:
break
i += 1
else:
prime[ptr] = n
ptr += 1
counter += 1
for i in range(ptr):
print(prime[i])
print(f'나눗셈을 실행한 횟수 : {counter}')곱셈과 나눗셈 횟수가 14,622번에서 3,774번으로 크게 줄었다.
알고리즘을 개선함에 따라 계산 속도가 빨라지는 것을 실감할 수 있다.
const getPrime = () => {
const primes = [];
for (let i = 2; i < 1001; i++) {
let isPrimeNumber = false;
for (let j = 2; j < i; j++) {
if (i % j === 0) isPrimeNumber = true;
}
if (!isPrimeNumber) primes.push(i);
}
};
const getPrimeVer1 = () => {
let ptr = 0;
const primes = [];
primes.push(2);
ptr += 1;
for (let i = 3; i < 1001; i += 2) {
let isPrimeNumber = false;
for (let j = 1; j < ptr; j++) {
if (i % primes[j] === 0) {
isPrimeNumber = true;
break;
}
}
if (!isPrimeNumber) {
primes.push(i);
ptr += 1;
}
}
};
const getPrimeVer2 = () => {
let ptr = 0;
const primes = [];
primes.push(2);
ptr += 1;
primes.push(3);
ptr += 1;
for (let i = 5; i < 1001; i += 2) {
let j = 1;
let isPrimeNumber = false;
while (primes[j] * primes[j] <= i) {
if (i % primes[j] === 0) {
isPrimeNumber = true;
break;
}
j += 1;
}
if (!isPrimeNumber) {
primes.push(i);
ptr += 1;
}
}
};
console.time("basic");
getPrime();
console.timeEnd("basic");
// basic: 4.524ms
console.time("ver1");
getPrimeVer1();
console.timeEnd("ver1");
// ver1: 0.404ms
console.time("ver2");
getPrimeVer2();
console.timeEnd("ver2");
// ver2: 0.174ms5 ) 리스트의 원소와 복사
파이썬에서 변수는 객체와 연결된 이름에 불과하다.
따라서 리스트 내 각 원소의 자료형을 다르게 사용할 수 있다.
리스트를 복사할 때 사용하는 copy( ) 함수는 주의해서 사용해야 한다.
리스트를 복사한 후 원솟값을 변경하면 복사된 원솟값까지 변경될 수 있기 때문이다.
이는 리스트의 얕은 복사를 수행하기 때문이다.
얕은 복사에서는 리스트 안의 모든 원소가 참조하는 곳까지 복사된다.
이러한 상황을 피하려면 구성 원소 수준으로 복사하는 방법이 필요하며, 이를 깊은 복사라고 한다.
깊은 복사는 copy 모듈 안의 deepcopy( ) 함수로 수행한다.
deepcopy( )는 리스트의 원소뿐만 아니라 구성 원소 ( 원소의 원소 ) 도 복사된다.
