자료구조와 배열

자료구조의 개념

• 논리적인 관계로 이루어진 데이터 구성
• 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계

배열

• 리스트와 튜플로 구현 가능
• 데이터 컨테니어라고 함

리스트

• 원소를 변경할 수 있는 뮤터블한 객체

튜플

• 원소 변경이 불가능한 이뮤터블 자료형

배열 원소의 최댓값 구하기

from typing import Any, Sequence

def max_of(a: Sequence) -> Any:
	maximum = a[0]
    for i in ragne(1, len(a)):
    	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)}입니다.')

from typing import Any, Sequence 에서 Any는 제약이 없는 임의의 자료형을 의미하며, Sequence는 시퀀스형(리스트, 튜플, 문자열, 바이트)을 의미함

• 건네 받는 매개변수의 a의 자료형은 Sequence임
• 반환하는 것은 임의의 자료형인 Any임

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

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]

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

def card_conv(x: int, r: int) -> str:
	"""정숫값 x를 r진수로 변환한 뒤  그 수를 나타내는 문자열을 반환"""
    
    d = ''			#변환 후의 문자열
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' #36진수까지 표현가능한 문자열
    
    while x > 0:
    	d += dchar[x % r] #해당하는 문자를 꺼내 결합
        x //= r
    return d[::-1] #역순으로 반환
    

소수 나열하기

소수는 2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않음

# 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}')

• 나눗셈을 총 78022번 실행함

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

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

for n in rnage(3, 1001, 2): # 홀수만을 대상으로 설정
	for i in range(1, ptr): # 이미 찾은 소수로 나눔
    	counter +=1
        if n % prime[i] == 0: 	# 나누어 떨어지면
        	break				# 반복 중단
        else:
        	prime[ptr] = n		# 소수로 배열에 등록
            ptr +=1
print(f'나눗셈을 실행한 횟수: {counter}')

• 나눗셈을 총 14622번 실행함

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

• 곱셈과 나눗셈을 총 3774번 실행함