Python 알고리즘 자료구조와 배열(하)

 < 모듈을 가져와 테스트 하기 >

 

 

max로 정의된 max.py() 함수를 사용할 수 있도록 import를 통해 가져오고, 난수를 뽑기 위해서 random 도 함께 import 하였습니다.  from [가져올 모듈=파일 이름]에서 max_of() 함수를 import 하겠다는 의미이고, x라는 빈 리스트를 입력할 개수만큼 공간 None으로 만듭니다.

 그 후 random.randint(low,high)를 통해  최솟값과 최댓값 사이의 값 중 1개를 뽑게 한 후, for 문을 통해 입력할 개수만큼 작동시키면 가져온 max_of() 함수를 사용해 원하는 값을 뽑아낼 수 있습니다.

 

 

 

 

 <배열 원소를 역순으로 정렬하는 알고리즘>

 

 배열 원소를 역순으로 정렬하는 알고리즘을 생각해봅시다. 예로 배열 a의 원소가 7개이고 [2,5,1,3,9,6,7]로 저장되어 있다면 이것을 역순으로 [7,6,9,3,1,5,2]로 바꾸어 볼 것입니다. 원소의 개수가 홀수인 경우는 가운데 값은 두고, 첫 번째와 마지막, 두 번째와 마지막 앞의 원소 이렇게 바꿔주면 되기 때문에 [ 원소수 // 2 ]는 교환 횟수입니다. 

- 왼쪽 원소의 인덱스(배열의 맨 앞에서 시작하는)      i  =>     n이 7이면 0 -> 1 -> 2

- 오른쪽 원소의 인덱스(배열의 맨 끝에서 시작하는)  n - i -1 =>   n이 7이면 6 -> 5 -> 4

 

 

 

 2행은 명시적으로 잘 표현해주기 위해서 사용한것이고, reverse_array() 함수에 매개변수의 길이를 n이라는 변수에 참조. 교환 횟수만큼 for문을 통해 배열 원소를 차례로 역수 취해준다.

 num을 통해 원소의 개수를 입력하고, x 배열안에 입력한 원소의 개수만큼 None을 만들어준다.  그 후 0~num-1 만큼 x[i]안에 차례로 값을 입력한다. 앞에 만들어 주었던 reverse_array(x)하여 x를 역순으로 정렬한 후 출력하면 원하는 역순으로 정렬하는 프로그램이 완성된다.

 

 

 

 

 

 

 

 

  

 

< 기수 변환하는 알고리즘 >

 

 이번에는 정숫값을 임의의 기수로 변환하는 알고리즘에 대해 볼 것인데, 첫 번째로는 n진수에 대한 이해가 필요합니다. n의 진수는 0~n-1까지의 수를 사용하여 나타내는 방법이고, 사용할 수 있는 수가 끝나면 한 자릿수를 올려 표현하는 방식입니다.

 

 

1행부터 13행까지 

def card_conv(x: int, r: int) -> str: 의 코드에서는 정숫값 x를 r 진수로 변환한 뒤 그 수를 나타내는 문자열을 반환시키는 함수입니다. d는 변환 후의 문자열을 나타내고 6행의 while 문에서는 해당하는 문자를 꺼내 결합하는 부분입니다.

그 후 9행에서 꺼내 결합한 것을 다시 역순으로 돌려 알맞게 반환 합니다.

 11행부터 28행까지

16행에서 변환할 값을 입력, 그리고 21행에서 바꾸어 줄 진수 입력한다. no, cd의 조건은 아래에 있고 입력된 값을 card_conv(no, cd) 함수를 통해 변환되어 출력된다.

 

 

 

 

 

 

 

< 약수 알고리즘 >

 

 #prime01. py

 

 1000 이하의 소수를 나열하는 프로그램이다. for 문을 통해 2 ~ 1000까지의 수를 i번 반복시키면서, n을 통해 소수를 구한다. 나누어 떨어지면 소수가 아니고, 반복은 더 이상 불필요하므로 중단시킨다.

 끝까지 나누어 떨어지지 않으면 else 문을 통해 print(i)로 소수 출력

옆 코드를 사용하면 나눗셈을 78022번 실시한다.

 

 

 

#prime02. py

 

 prime01.py과 다른 점은 소수를 구하는 과정에서 지금까지 구한 소수를 배열 prime의 원소로 저장하도록 개선한 것입니다. n이 소수인지 판단할 때 배열 prime에 저장한 소수로 나눗셈을 하면 됩니다. 5행에서 2는 소수인 것이 분명하므로 첫 원소인 prime [0]에 저장한다는 것입니다.

 3부터 시작하여 소수를 이중 for 문으로 구합니다. 옆의 for문은 그림처럼 prime [i]의 i값으로 나눗셈을 반복하는 것입니다. 결과 나눗셈을 실행한 횟수는 14622번 실시합니다.

prime01.py의 나눗셈 실행 횟수에 비해 효율적으로 알고리즘을 개선한 것입니다.

 

 

 

 

 

#prime03. py

 

 옆의 코드는 prime02.py에서 한번 더 개선한 것입니다. 한 아이디어를 추가한 것인데 예로 넓이가 100인 직사각형이 있다면, 5로 나누어 떨어지지 않는다면 20으로도 물론 나누어 떨어지지 않을 것입니다. 이것은 직사각형 한 변의 길이만 나눗셈을 시도하고 그 과정에서 한 번도 나누어 떨어지지 않으면 소수라고 판단해도 좋을 것 같다는 생각이 듭니다. 

[ n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다. ]라는 아이디어를 적용하여 개선한 프로그램이 prime03.py입니다. 14행의 prime [i]*prime [i] <=n 에서는 prime[i]가 n의 제곱근보다 작거나 같은지를 곱셉을 통해 판단합니다. 

 prime01.py, prime02.py 는 나눗셈의 횟수만 세었는데, 곱셉과 나눗셈을 하는 데 드는 비용은 같으므로 prime03.py 에서는 곱셈, 나눗셈 횟수의 합계를 counter에 저장합니다.

 결과적으로 곱셈과 나눗셈을 실행한 횟수는 3774번 실시합니다. 이렇게 같은 목적을 가진 코드라 하더라도 알고리즘을 어떻게 구사하느냐에 따라 기능을 더 효율적으로 사용이 가능하다는 것을 볼 수 있었습니다.

 

 

 

 

 

 

cf)

 < 얕은 복사와 깊은 복사 >

 

 

 

리스트를 복사할 때 사용하는 copy() 함수는 주의해서 사용하여야 합니다. 리스트를 복사한 후 원 솟값을 변경하면 복사된 원 솟값까지 변경될 수 있기 때문입니다.  copy를 사용하여 리스트 y를 복사한 뒤 x [0][1]=9로 업데이트하면 y까지 업데이트됩니다. 그 이유는 리스트의 얕은 복사를 수행하기 때문인데 리스트 안의 모든 원소가 참조하는 곳까지 복사됩니다. 

 이러한 상황을  피하려면 구성 원소 수준으로 복사하는 방법이 필요하며, 깊은 복사라고 합니다. 깊은 복사는 copy 모듈 안의 deepcopy() 함수로 수행합니다.

 위는 얕은 복사를 이용한 x, y의 값 출력, import부터는 deepcopy()를 사용하기 위해 copy모듈을 임포트 한 후 x를 y로 깊은 복사 하여 출력한 것입니다.