알고리즘 기초 - 자료구조와 배열

🌈 자료구조와 배열

🔥 배열 원소의 최대값을 구해 출력하기

🔥 배열의 원솟값을 난수로 받아 최대값 출력

🔥 튜플, 문자열, 문자열 리스트의 최대값 구하기

🔥 배열 역순으로 정렬하는 함수만들기

🔥 소수 나열하기

1. 배열 원소의 최대값을 구해 출력하기

• while문을 무한 반복하여 'End'를 입력하기 전까지 숫자를 입력받고, 이를 num_list에 추가
• 'End'를 만나 숫자 입력이 종료되면, max_of() 함수가 실행되어 배열 내 요소를 스캔하여 최대값을 a[i]에 담음

✍🏻 python

# 배열을 받아 최대값을 출력하는 함수
def max_of(a):
    maximum = a[0]
    for i in range(1, len(a)):
         if a[i] > maximum: 
            maximum = a[i]
    return maximum
print('End를 입력할 때 까지, 배열의 값을 입력 받아 최대값을 구합니다.')
# 배열을 입력받아 num_list에 추가
number = 0
num_list = []
while True:
    s = input('숫자를 입력하세요 : ')
    if s == 'End':
        break
    num_list.append(int(s))
    number += 1
# 입력 받은 내열 내 요소 갯수와 그 요소 중 최대값을 출력
print(f'입력된 배열 내 요소는 총 {number}개 입니다.')
print(f'배열 내 요소의 최대값은 {max_of(num_list)} 입니다.')

2. 배열의 원소값을 난수로 받아 최대값 출력

• 최대값을 구하는 암수는 앞에서 사용한 max_of()를 사용
• 배열의 원솟값을 난수로 받기 위해서는 random 라이브러리 import
• 배열의 원소의 갯수를 미리 지정하기 위해서는 [None] * num 사용

✍🏻 python

# random 라이브러리 import
import random
# 배열의 최댓값을 구하는 함수
def max_of(a):
    maximum = a[0]
    for i in range(1, len(a)):
         if a[i] > maximum: 
            maximum = a[i]
    return maximum
# random.randomint()의 범위를 요청
print('난수의 최대값을 구합니다.')
num = int(input('난수의 갯수를 입력하세요 : '))
low_num = int(input('난수의 최솟값을 입력하세요 : '))
high_num = int(input('난수의 최댓갑을 입력하세요 : '))
# 원소의 갯수가 num개인 리스트 생성
num_list = [None] * num
# 난수 생성 및 num_list의 담기
for i in range(num):
    num_list[i] = random.randint(low_num, high_num)
print(f'{num_list}')
print(f'이 가운데 최댓값은 {max_of(num_list)} 입니다.')

3. 튜플, 문자열, 문자열 리스트의 최대값 구하기

• tuple, string, array는 모두 인덱스값을 가지기 때문에 max_of() 함수에 대입하면 인덱스 자릿수 마다의 값을 비교해줌
• a = ['DTS', 'AAC', 'FLAC']는 원소를 비교해 사전순으로 가장 큰 원소를 반환함

✍🏻 python

def max_of(a):
    maximum = a[0]
    for i in range(1, len(a)):
         if a[i] > maximum: 
            maximum = a[i]
    return maximum
# 비교 대상 : 각 tuple, string, array
t = (4, 7, 5.6, 2, 3.14, 1)
s = 'string'
a = ['DTS', 'AAC', 'FLAC']
print('각 배열의 원소값 중 최대값을 출력합니다.')
print(f'{t}의 최대값은 {max_of(t)} 입니다.') # (4, 7, 5.6, 2, 3.14, 1)의 최대값은 7 입니다.
print(f'{s}의 최대값은 {max_of(s)} 입니다.') # string의 최대값은 t 입니다.
print(f'{a}의 최대값은 {max_of(a)} 입니다.') # ['DTS', 'AAC', 'FLAC']의 최대값은 FLAC 입니다.

4. 배열 역순으로 정렬하는 함수만들기

• a와 같은 배열이 있을 때, a를 2로 나누는 몫만큼 자리를 교체해주면 역순으로 배열이 가능
• 이에 a의 길이가 5라면 2로 나눈 몫은 2가 되기 때문에 for문에 i는 0과 1의 값으로 반복문을 실행
• a[n-i-1]는 a의 마지막 요소값부터 for문을 통해 순차적으로 지정할 수 있기 때문에 a[i]와 자리수를 교환하면 역순으로 정렬됨

✍🏻 python

a = [1,2,3,4,5]
def reverse_array(a):
    n = len(a) # 5
    for i in range(n//2): # i는 0, 1
        a[i], a[n - i - 1] = a[n - i - 1], a[i]
        # a[0], a[4] = a[4], a[0]
        # a[1], a[3] = a[3], a[1]
    print(a)         
reverse_array(a) # [5, 4, 3, 2, 1]

• 배열의 원소를 입력 받아 배열을 역순으로 정렬시키기
• 배열 길이를 num_len으로 받고, 이 길이만큼 빈 배열을 생성함
• for문을 통해 배열의 자릿수만큼 숫자를 입력받아 배열을 완성시킨 뒤, 함수를 호출해 역순 정렬
• 자리숫에 5를 입력하고, 1~5까지 수를 배열 안에 순차적으로 넣었을 때 역정렬시킨 결과
• reversed() 함수는 이러한 구조로 역순으로 정렬함

✍🏻 python

def reverse_array(a):
    n = len(a)
    for i in range(n//2):
        a[i], a[n - i - 1] = a[n - i - 1], a[i]
# 원소의 갯수를 입력 받고, 그만큼 자릿수를 가진 배열을 생성        
print('배열 원소를 역순으로 정렬합니다.')
num_len = int(input('원소 수를 입력하세요'))
num_list = [None] * num_len
# for문을 통해 요소의 값을 순차적으로 받음
for i in range(num_len): # num_list의 요소 갯수만큼 for문을 실행해 입력값을 배열에 담음
    num_list[i] = int(input(f'num_list[{i}]의 값을 입력하세요 : '))
reverse_array(num_list)
print('배열 원소를 역순으로 정렬했습니다.')
# 출력
for i in range(num_len):
    print(f'num_list[{i}] = {num_list[i]}')

5. 소수 나열하기

• 1과 자기 자신 이외의 정수로 나누어 떨어지지 않는 정수를 소수라 부름
• 즉, 정수가 n일 때 2부터 n-1까지 정수로는 나누어 떨어지지 않음
• 만약 2부터 n-1까지 정수 중 나누어 떨어지는 수가 있다면 이는 합성수라 부름
• 2부터 1000까지 정수 중 소수를 구하려면 2부터 100까지를 반복문을 돌리고, 내부 포문을 사용해 각 숫자가 2부터 n-1까지 수로 나눠지지 않는 n값을 구함

✍🏻 소수 구하기(~1000까지) : 실행 횟수 78022

counter = 0
for n in range(2, 1001):
    for i in range(2, n):
        counter += 1 #counter = counter + 1
        if n % i == 0:
            break
    else:
        print(n)
print(f'나눗셈을 실행한 횟수는 {counter} 입니다.') # 나눗셈을 실행한 횟수는 78022 입니다.

✍🏻 소수 구하기(~1000까지) 개선 1 : 실행 횟수 14622

counter = 0
ptr = 0
prime = [None] * 500
# 2는 소수이기 때문에 default로 prime 배열에 0번째로 추가
prime[ptr] = 2 
ptr += 1 # 배열에 첫번째로 2를 추가한 후 ptr은 1로 올림. 올리지 않으면 초기값이었던 2가 아래 for문에 덮여씌어지기 때문
# n은 3부터 1000까지 for문 반복하고, 짝수는 필요없기 때문에 홀수만 반복함
for n in range(3, 1001, 2): # n이 3일 때
    for i in range(1,ptr):  # n이 3일 때, ptr은 1이기 때문에 for문이 1부터 0까지라 실행안됨
        counter += 1
        if n % prime[i] == 0:
            break
    else:
        prime[ptr] = n  # prime[1] 에 3을 대입
        ptr += 1  # else문이 실행되었기 때문에,, ptr은 1 올려줌
# 위 for문이 실행된 이후 결과적인 ptr값 만큼 for문을 실행
for i in range(ptr):
    print(prime[i]) # prime 배열에 담긴 요소갯수를 출려
print(f'나눗셈을 실행한 횟수는 {counter} 입니다.') # 나눗셈을 실행한 횟수는 14622 입니다.