🖇️알고리즘 스터디 2주차

02-2장. 배열이란

-배열의 원솟값을 난수로 결정하기+최댓값 원소 구하기

import random
from max import max_of        #max라는 모듈로부터 max_of란 함수 임포트

print('난수의 최댓값을 구합니다.')
num=int(input('난수의 개수:'))
lo=int(input('난수의 최솟값:'))
hi=int(input('난수의 최댓값:'))
x=[None]*num      #원소 수가 num인 빈 리스트 생성

for i in range(num):
	x[i]=random.randint(lo,hi)      #lo 이상 hi 이하인 정수 난수 반환
    
print(f'{(x)}')
print(f'이 가운데 최댓값은 {max_of(x)}.')

-리스트, 튜플의 대입
: 리스트를 두 개 선언하고 서로 대입해도 복사되는 것은 값이 아니라 참조하는 곳

-리스트 스캔
: enumerate() 함수는 인덱스와 원소를 짝지어 튜플로 꺼내는 내장 함수

-배열 원소를 역순으로 정렬하기

for i in range(n//2):
	a[i], a[n-i-1]=a[n-i-1], a[i]

-기수 변환하기(n진수 구하기)

def card_conv(x: int, r: int) ->str:	
#정수 x를 r진수로 변환하고 그 수를 문자열로 반환

	d=''	#변환 후의 문자열
    dchar= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    
    while x>0:
    	d+=dchar[x%r]	#해당하는 문자를 꺼내 결합
        x//=r
        
    return d[::-1]		#역순으로 반환

-파이썬에서 인수 전달
: 실제 인수인 객체에 대한 참조를 값으로 전달하여 매개변수에 대입되는 방식

인수가 이뮤터블일 때-> 함수 안에서 매개변수의 값을 변경하면 다른 객체를 생성하고 그 객체에 대한 참조로 업데이트 됨. 호출하는 쪽의 실제 인수에는 영향을 주지 x

인수가 뮤터블일 때-> 객체 자체를 업데이트함. 호출하는 쪽의 실제 인수는 값이 변경됨.

-소수 저장하기 알고리즘

counter=0	#나눗셈 횟수 카운트
ptr=0		#이미 찾은 소수 개수
prime=[None]*500	#소수를 저장하는 배열

prime[ptr]=2	#소수 2 초깃값으로 지정
ptr+=1

for n in range(3, 1001, 2)		#홀수만 대상으로 설정
	for i in range(i, 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}')

-"어떤 정수 n은 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않으면 소수라고 할 수 있다"
=> 제곱근보다 제곱이 구하기 훨씬 간단하므로 역으로 이용

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		#소수로 배열에 등록
        counter+=1

for i in range(ptr):
	print(prime[i])

++105p RE