🚨 알고리즘 더 파헤쳐 보자!
Q 1) 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. (단, '+' 보다 '✕'를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.)
👉 내가 쓴 코드
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
multy_sum = 0
for num in array:
if num > 1:
multy_sum *= num
else:
multy_sum += num
return multy_sum
result = find_max_plus_or_multiply(input)
print(result) #8머가 문제지,,,,???
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
multy_sum = 0
for num in array:
if num > 1 or multy_sum > 1:
multy_sum *= num
else:
multy_sum += num
return multy_sum
result = find_max_plus_or_multiply(input)
print(result) #8선생님 코드 보고 했는데 뭐가 문제지,,,,? 왜지,,,?
선생님 코드
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
multy_sum = 0
for num in array:
if num <= 1 or multy_sum <= 1:
multy_sum += num
else:
multy_sum *= num
return multy_sum
result = find_max_plus_or_multiply(input)
print(result) #728시간 복잡도 = O(N)이다. 다른 계수는 신경쓰지 않아도 된다고 하는데 왤까?,,,? 이것도 나중에 찾아보고 기록해야겠다.
Q 2) 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
"abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!
▶️ 정답
input = "abadabac"
def find_not_repeating_character(string):
alphabet_occurrence_array = [0] * 26
for rmf in string:
if not rmf.isalpha():
continue
arr_index = ord(rmf) - ord("a")
alphabet_occurrence_array[arr_index] += 1
not_repeating_character_array = []
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence == 1:
not_repeating_character_array.append(chr(index + ord('a')))
for char in string:
if char in not_repeating_character_array:
return char
return "_"
result = find_not_repeating_character(input)
print(result)
▶️ 설명
alphabet_occurrence_array = [0] * 26
for rmf in string:
if not rmf.isalpha():
continue
arr_index = ord(rmf) - ord("a")
alphabet_occurrence_array[arr_index] += 1이 부분은 앞에서 알파벳 최빈값 찾을 때 배열을 정하는 코드였고, 마찬가지로 이렇게 쓸 거라 그 코드에서 가져옴.
not_repeating_character_array = []
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence == 1:
not_repeating_character_array.append(chr(index + ord('a')))이 부분은 앞에서 쓰여진 코드가 알파벳 순서대로 최빈값 배열을 만들어 준 것을 최빈값이 1인 알파벳만 뽑아내서 배열로 만드는 코드이다.
for char in string:
if char in not_repeating_character_array:
return char이 부분은 알파벳 순서대로 최빈값이 1인 배열을 원래의 input 순서로 받아오기 위해 for문 돌려서 첫 번째 글자로 가져오는 코드이다.
▶️ 시간 복잡도
이것도 바로 O(N) 만큼 걸린다. 함수 구문 하나하나를 보지 않더라도, 1차 반복문이 나왔고, array 의 길이 만큼 반복한다? 그러면 O(N) 겠네 라고 생각해주시면 된다. 다른 계수는 다 버려버~!
Q 3) 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
input = 20
아래와 같이 반환되야 한다
[2, 3, 5, 7, 11, 13, 17, 19]
▶️ 첫 번째 코드
input = 20
#소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다.
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): #2~number+1이 n에 대입
for i in range(2, n):
if n % i == 0:
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)range(a,b)가 a부터 b-1까지의 범위를 말하는 것이라 for n in range(2, number + 1): 이렇게 표시해준다.
▶️ 두 번째 코드
input = 20
# 소수는 자기 자신과 1 외에는 아무 것도 나눌 수 없다.
# 주어진 자연수 N이 소수이기 위한 필요 충분 조거은
# N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.
# 수가 수를 나누면 몫이 발생하는 데, 몫과 나누는 수 둘 중 하나는
# 반드시 N의 제곱근 이하인 것이다.
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): # 2 ~ (number+1)이 n에 대입
# n이 20이라고 하면
# i는 2~19
# 2 ~ (n-1) 중엣어 소수인 숫자만
for i in range(2, n): # i의 범위 2 ~ (n-1)
if n % i == 0 and i * i <= n: # n = 2,3만 적용된다. 제곱근이 루트 20이니까!
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)
Q 4) 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
(예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.)
input = "011110"
▶️ 선생님 코드
input = "011110"
# 모두 0으로 만드는 방법에서 최소로 뒤집는 숫자
# count_all_zero
# 0 -> 1로 문자열이 전환되는 순간 count_all_zero += 1
# 모두 1으로 만드는 방법에서 최소로 뒤집는 숫자
# count_all_one
# 1 -> 0로 문자열이 전환되는 순간 count_all_one += 1
# 1) 뒤집어질 때, 즉 0에서 1 혹은 1에서 0으로 바뀔 때
# 2) 첫번째 원소가 0인지 1인지에 따라서 숫자 추가해줘야 함
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0
count_to_all_one = 0
if string[0] == '0':
count_to_all_one += 1
elif string[0] == '1':
count_to_all_zero += 1
for i in range(len(string) - 1):
if string[i] != string[i + 1]: # 앞 뒤 숫자가 다를때
if string[i + 1] == '0':
count_to_all_one += 1
if string[i + 1] == '1':
count_to_all_zero += 1
# print((count_to_all_one, count_to_all_zero)) #(2, 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)생각은 했는데 코드가 대체 왜 안나오는겨,,,, 일단은 정답을 많이 보고 생각해서 내 걸로 만들어서 나중에 완강 후 다시 한 번 더 풀어봐야지