내일배움캠프 AI, 13일차 TIL - 2022.09.16

스파르타 코딩클럽 내일배움캠프 AI 웹개발자양성과정 3회차

2022.09.16. 13일차 - TIL

 

 

1. 자료구조, 알고리즘 강의

• 최댓값 찾기 : [3, 5, 6, 1, 2, 4] 의 배열에서 가장 큰 수를 반환

# 1. 각 숫자마다 모든 다른 숫자와 비교해 최댓값 확인
def find_max_num(array):
    for num in array:  # array의 길이(n)만큼의 연산
    	for cp_num in array:  # array의 길이(n)만큼의 연산
        	if num < cp_num:  # 비교 연산 1번
                   break
        # for num in array에서 break가 한번도 실행되지 않으면 num을 반환
        else:
        	return num

# 시간 복잡도 : n * n = n^2
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))


############################################################################
# 2. 가장 큰 수를 저장할 변수를 만들고, 배열에서 해당 변수값과 비교
def find_max_num(array):
    max_num = array[0]  # 대입 연산 1번
    for num in array:  # array의 길이(n)만큼의 연산
    	if num > max_num:  # 비교 연산 1번
        	max_num = num  # 대입 연산 1번
    return max_num

# 시간 복잡도 : 1 + 2*n
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• 시간 복잡도 판단 : 각 줄이 실행되는 명령은 1번의 연산으로 본다, 반복문은 자료의 크기 n번의 연산으로 본다 -> 두번째 방법이 더 좋음(상수는 신경쓰지 않는다...)
• 최빈값 찾기 : "hello my name is sparta" 문자열에서 가장 많이 포함된 알파벳 반환

# 1. 각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인
def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0  # 빈도가 가장 높은 알파벳의 빈도값
    max_alphabet = alphabet_array[0]
    
    for alphabet in alphabet_array:  # alphabet_array의 각 알파벳에 대해 접근
    	occurrence = 0  # alphabet_array의 각 요소 별 빈도수 변수
        for char in string:  # 문자열의 각 문자에 대해 접근
        	if char == alphabet: 
                   occurrence +=1
                
        if occurrence > max_occurrence:
        	max_alphabet = alphabet  # 빈도가 가장 높은 알파벳
            max_occurrence = occurrence  # 빈도가 가장 높은 알파벳의 빈도값
        
    return max_alphabet


result = find_max_occurred_alphabet(input)
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
###############################################################################
# 2. 각 알파벳의 빈도수를 alphabet_occurrence_list 변수에 저장
def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0]^26  #index=0은 a, value는 빈도값 이런식으로
    
    for char in string:
    	if not char.isalpha():  # 알파벳이 아닌 경우(띄어쓰기) skip
        	continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1
        
    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
    	alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index
            
    
    return char(max_alphabet_index + ord('a'))


result = find_max_occurred_alphabet(input)
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

• 공간 복잡도 : 저장하는 데이터의 양이 1개의 공간 사용 -> alphabet_occurrence_array 는 공간 26을 차지
• 공간 복잡도 보다 시간 복잡도를 더 신경 써야한다.
• 52N + 104 든 3N + 106 이든 N^2에 비해 아무것도 아니다.
• 점근 표기법 : 알고리즘의 성능을 수학적으로 표기하는 방법 -> '효율성' 평가
  - 빅오 : 최악의 성능이 나올 때의 연산량 -> 우리는 항상 최악의 상황을 가정한다!!
  - 빅오메가 : 최선의 성능이 나올 때의 연산량
• 문제1 : 0 혹은 양의 정수로 이루어진 배열에서 좌 -> 우로 숫자를 확인하여 곱셉 or 덧셈 연산을 적용해 가장 큰 수 구하기

# 0 또는 1일 때는 더하기가 더 큰 수를 만든다.
def find_max_plus_or_multiply(array):
    multiply_sum = 0  # 합
    for number in array:  # array의 길이만큼 시간복잡도
    	if number <= 1 or multiply_sum <= 1:  # 숫자가 1보다 작거나 같을 때 or 합이 1보다 작거나 같을 때
        	multiply_sum += number
        else:
        	multiply_sum *= number
    return multiply_sum


# 시간 복잡도 : n
result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

• 문제2 : 영어로 되어 있는 문자열에서 반복되지 않는 첫번째 문자를 반환, 없으면 _를 반환

# 문자열에서 각 알파벳 별 빈도수 확인
input = "abadabac"

def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26  # 알파벳 별 빈도수 저장 배열
    
    for char in string:
    	if not char.isalpha():  # 알파벳이 아니면 skip
        	continue
         arr_index = ord(char) - ord("a")  # 인덱스로 바꾸기
         alphabet_occurrence_array[arr_index] += 1  # 빈도값 1 증가
         
    not_repeating_character_array = []  #한번만 등장한 알파벳의 배열
    for index in range(len(alphabet_occurrence_array)):  # 빈도수 저장 배열의 각 요소에 대해
    	alphabet_occurrence = alphabet_occurrence_array[index]
        
        if alphabet_occurrence == 1:  # 빈도수가 1이면
        	not_repeating_character_array.append(chr(index + ord("a")))  # 처음 등장한 알파벳 배열에 추가
         
     for char in string:  # 문자열에서 먼저 등장하는 알파벳을 찾기 위해
        if char in not_repeating_character_array:
            return char
            
    return "_"

# 시간 복잡도 : n
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

• 1주차 과제
  - 소수 나열하기(수를 입력받고 해당 수까지의 소수를 나열해 출력)

input = 20


def find_prime_list_under_number(number):
    prime_numbers = []
    if number == 1: 
        return prime_numbers
    else:
        for num in range(2, number+1):
            prime_numbers.append(num)
            for i in range(2, int(num**0.5)+1):
                if num % i == 0:
                    del prime_numbers[-1]
                    break
        
    return prime_numbers


result = find_prime_list_under_number(input)
print(result)

    - 문자열 뒤집기(이건 문제를 이해 못해서 해설 봤다...;;; 모두 0 or 모두 1로 변환하기 위해 뒤집는 횟수를 카운트해 최소인 값 출력)

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0  # 모두 0으로 만들기 위해 필요한 횟수
    count_to_all_one = 0  # 모두 1로 만들기 위해 필요한 횟수

    if string[0] == '0':  # 첫번째가 0일 경우
        count_to_all_one += 1  # 전체가 1로 되기 위해서는 바뀌어야 하기에 1증가
    elif string[0] == '1':  # 첫번째가 1일 경우
        count_to_all_zero += 1  # 전체가 0으로 되기 위해서는 바뀌어야 하기에 1증가

    for i in range(len(string) - 1):
        if string[i] != string[i+1]:  # 값이 연속되지 않을 경우 
            if string[i+1] == '0':  # 다음 숫자가 0일 경우
                count_to_all_one += 1  #전체가 1로 되기 위해서는 바뀌어야 하기에 1증가
            if string[i+1] == '1':  # 다음 숫자가 1일 경우
                count_to_all_zero += 1  # 전체가 0이 되기 위해서는 바뀌어야 하기에 1증가

    return min(count_to_all_one, count_to_all_zero)  # 둘 중 최소값을 선택


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

 

 

2. 백준

계속 시간 초과가 떠서 어떻게 해야 할지 고민했다... 이거 저거 찾아보다 에세토스테네스의 체인가 하는 것까지 가서 코드를 완성했지만 그래도 통과가 되지 않았다. 

가장 먼저 한 방법은 이전과 같이 2부터 해당 수까지 계속 나누어 소수를 찾는 방법이다.

m, n = list(map(int, input().split()))
numbers = []

for i in range(m, n+1):
    if i == 1:
        continue

    numbers.append(i)
    for j in range(2, i):
        if i % j == 0:
            del numbers[-1]
            break

for v in numbers:
    print(v)

하지만 시간 초과로 실패했다... 그럴 수 밖에 없는 것이 지금 n^2의 시간으로 굉장히 오래 걸린니다... 두번째 방법은 에스토스테네스의 체를 이용한 방법이다. 이 방법은 2부터 하나씩 진행해 나갈 때 배수를 모두 배제하는 방법이다.

# 에스토스테네스의 체
def primeNumber(n) :
    # 배열 생성 후 초기화(2, 3, 4, )
    prime_numbers = [0, 0]
    for i in range(2, n+1):
        prime_numbers.append(i)

    # 2부터 시작해 특정 수의 배수를 모두 지우기
    for i in range(2, n+1):
        if prime_numbers[i] == 0:  # 이미 지워진 수 건너뛰기
            continue
        # 이미 지워진 수가 아니라면 그 배수부터 출발해 수 지우기
        for j in range(i*2, n+1, i):
            prime_numbers[j] = 0

    # 값이 0인 요소 제거
    while 0 in prime_numbers:
        prime_numbers.remove(0)

    return prime_numbers
    
    
m, n = list(map(int, input().split()))
arr = primeNumber(n)
for number in filter(lambda x: x>=m, arr):
    print(number)

결국 방법을 검색해보니 해당 수의 제곱근까지만 검사하면 해결된다고 해서 아래와 같이 진행했다.

# n의 약수는 무조건 sqrt(n)의 범위에 존재
# n = 12일 경우, n의 제곱근은 3.46
# 12의 약수는 1, 2, 3, 4, 6, 12 => 1*12, 2*6, 3*4, 4*3, 6*2, 12*1
# n의 제곱근까지 향하게 되면 이후 몫과 나누는 값은 반대로 바뀐다
# 따라서 n의 제곱근까지 나누어 떨어지는지 여부를 조사해 소수판별을 빠르게 한다.
def isPrime(num): # num이 소수인지 판별하는 함수
    if num == 1: # num이 1이면 소수가 아님
        return False
    else:
        for i in range(2, int(num**0.5)+1): 
            if num%i == 0: # 2~num의 제곱근까지 검사
                return False
            
        return True

m, n = map(int, input().split())
for i in range(m, n+1):
    if isPrime(i):
        print(i)

 

 

3. 후기

백준 문제 난이도가 점차 올라가는 것이 느껴진다... 이제 문제 하나하나가 버거워졌다. 알고리즘 강의도 병행해서 듣고 있는데 얼마나 효과를 볼 지 잘 모르겠다. 백준 재귀단계까지 못 푼 문제들을 정리해야겠다.