input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
answer = array[0] # 배열의 첫 번째 값인 3을 answer에 넣음
for i in array: # 배열의 값들을 하나씩 불러옴
if i > answer: # i는 배열의 0번째, 1번째, 2번째, ... 값들이 들어옴
answer = i # 두 값을 비교해서 큰 값이 answer에 업데이트 됨
return answer # for문이 다 돌면 answer에는 배열의 가장 큰 값이 저장돼 있음
result = find_max_num(input)
print(result)
# 출력화면
# 6
저번 주 알고리즘 실시간 특강 때 풀었던 문제라 쉽게 풀 수 있었다 ㅎㅎ 본의 아니게 복습했네
- 최빈값 구하기
2가지 방법으로 풀 수 있음
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', 'w', 'x', 'y', 'z']
max_occurrence = 0 # 가장 많이 나온 알파벳이 몇 번 나왔는지를 담을 그릇
max_alphabet = alphabet_array[0] # 가장 많이 나온 알파벳이 뭔지 담을 그릇
for alphabet in alphabet_array: # 알파벳 배열을 돌면서 a,b,c,...하나씩 꺼냄
occurrence = 0 # 알파벳이 몇 번 나왔는지 담을 그릇
for char in string: # 입력값 string에서 문자 하나씩 꺼냄
if char == alphabet: # string의 문자 한 개와 알파벳 배열의 알파벳이 일치하면
occurrence += 1 # 알파벳 출현 횟수에 1을 더해줌
if occurrence > max_occurrence: # 그 더해진 알파벳 출현 횟수가 가장 많이 나온 알파벳 출현 횟수보다 크면(초기값 0)
max_occurrence = occurrence # 알파벳 출현 횟수를 max_occurrence에 담음
max_alphabet = alphabet # 그 알파벳이 뭔지 알 수 있게 해당 알파벳을 max_alphabet에 담음
return max_alphabet # 알파벳 배열만큼 for문이 다 돌면 max_alphbet을 반환함
26길이의 알파벳 배열을 선언하고 입력값과 같은 알파벳이 나오면 occurrece를 1씩 증가시켜 max와 비교하고 더 크면 해당 알파벳을 max알파벳에 넣어주는 방법
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26 # 숫자 0을 알파벳 수 만큼의 길이의 배열에 넣어 변수에 담음
for alpha in string: # 입력값 string에서 문자 하나씩 꺼냄
if not alpha.isalpha(): # 해당 문자가 문자가 아니면
continue # for문이 다시 돌아서 다음 문자를 꺼냄
else: # 해당 문자가 문자가 맞으면
arr_index = ord(alpha) - ord("a") # 해당 문자의 아스키값에서 a 아스키 값을 빼면 해당 문자의 알파벳배열 인덱스가 나옴
alphabet_occurrence_array[arr_index] += 1 # 해당 알파벳 자리에 1을 더해줌
# for문이 다 돌면 이렇게 채워짐 occurrence_array = [3, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]
max_occurrence = 0 # 가장 많이 나온 알파벳 횟수 초기값 0
max_alphabet_index = 0 # 가장 많이 나온 알파벳 인덱스 초기값 0
for index in range(len(alphabet_occurrence_array)): # alphabet_occurrence_array의 길이만큼 for문이 돎(0부터 25까지)
alphabet_occurrence = alphabet_occurrence_array[index] # index 0 -> alphabet_occurrence 3
if alphabet_occurrence > max_occurrence: # 인덱스 0부터 25까지 쭉 비교하는데 alphabet_occurrence 값이 max값보다 크면
max_alphabet_index = index # max알파벳인덱스 값에 해당 인덱스 번호를 넣고
max_occurrence = alphabet_occurrence # 해당 알파벳이 나온 횟수도 max값에 넣음
return chr(max_alphabet_index + ord("a")) # 다시 숫자->문자로 변환해서 반환함
알파벳 개수(26)만큼의 0으로 된 배열을 선언하고 해당 알파벳의 인덱스값을 아스키코드를 이용해 변환하여 찾아주는 방법, 알파벳 출현횟수를 1씩 증가시켜 가장 큰 횟수와 그 알파벳이 인덱스값을 각 max값에 저장, 맥스인덱스값을 다시 아스키코드를 이용하여 문자로 변환해서 반환하는 방법
- 더하기 or 곱하기
문제를 잘못 이해해서 인덱스 0과 1 곱하거나 더해서 큰값, 1과 2 곱하거나 더해서 큰값 .... 해서 가장 큰 값 찾기로 생각했다
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
max_num = 0
for index in range(len(array) - 1):
plus = array[index - 1] + array[index]
mult = array[index - 1] * array[index]
if plus > max_num or mult > max_num:
if plus > mult:
max_num = plus
else:
max_num = mult
return max_num
result = find_max_plus_or_multiply(input)
print(result)
# 출력화면
# 30
ㅋㅋㅋㅎㅎㅎ...당차게 풀고 강의를 들었는데 문제를 완전히 잘못 이해한 거였다
아래는 정답코드이다...
def find_max_plus_or_multiply(array):
multiply_sum = 0 # 반환할 변수 생성
for number in array: # 입력값 array를 돌면서 하나씩 꺼냄
# 배열의 숫자가 1보다 작거나 같으면, 또는 반환할 값(초기값이 0이니까)이 1보다 작거나 같으면
if number <= 1 or multiply_sum <= 1:
multiply_sum += number # 숫자를 더해주고
else: # 아니면
multiply_sum *= number # 숫자를 곱해라
return multiply_sum
<공간 복잡도 계산>
1번째 방법
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"]
# -> 26 개의 공간을 사용합니다
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet = alphabet_array[0] # 1개의 공간을 사용합니다.
for alphabet in alphabet_array:
occurrence = 0 # 1개의 공간을 사용합니다
alphbet_array의 길이 = 26
max_occurrence, max_alphabet, occurrence 변수 = 3
총 29 만큼의 공간 사용함
2번째 방법
alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') # 1개의 공간을 사용합니다
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet_index = 0 # 1개의 공간을 사용합니다
for index in range(26):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
alphbet_array의 길이 = 26
arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
총 30 만큼의 공간 사용
29나 30이나 상수라 효율성에는 큰 상관이 없음
대부분의 문제에서 알고리즘의 성능이 공간에 의해서 좌우되지 않음
즉, 공간복잡도보다는 시간복잡도를 더 신경 써야 함!
<시간 복잡도 계산>
1번째 방법
for alphabet in alphabet_array: # alphabet_array 의 길이(26)만큼 아래 연산이 실행
occurrence = 0 # 대입 연산 1번 실행
for char in string: # string 의 길이만큼 아래 연산이 실행
if char == alphabet: # 비교 연산 1번 실행
occurrence += 1 # 대입 연산 1번 실행
if occurrence > max_occurrence: # 비교 연산 1번 실행
max_alphabet = alphabet # 대입 연산 1번 실행
max_occurrence = number # 대입 연산 1번 실행
alphabet_array의 길이 * 대입 연산 1번
alphabet_array의 길이 * string의 길이 * (비교 연산 1번 + 대입 연산 1번)
alphabet_array의 길이 * (비교 연산 1번 + 대입 연산 2번)
여기서 string의 길이를 보통 N이라고 표현함
위의 시간을 다음과 같이 표현 할 수 있음
26*(1 + 2*N + 3) = 52N + 104
즉, 1번째 방법은 N만큼의 시간이 필요함
2번째 방법
for char in string: # string 의 길이만큼 아래 연산이 실행
if not char.isalpha(): # 비교 연산 1번 실행
continue
arr_index = ord(char) - ord('a') # 대입 연산 1번 실행
alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행
max_occurrence = 0 # 대입 연산 1번 실행
max_alphabet_index = 0 # 대입 연산 1번 실행
for index in range(len(alphabet_occurrence_list)): # alphabet_array 의 길이(26)만큼 아래 연산이 실행
alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행
if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행
max_occurrence = alphabet_occurrence # 대입 연산 1번 실행
max_alphabet_index = index # 대입 연산 1번 실행
string의 길이 * (비교 연산 1번 + 대입 연산 2번)
대입 연산 2번
alphabet_array의 길이 * (비교 연산 1번 + 대입 연산 3번)
위의 시간을 다음과 같이 표현함
N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106
즉, 2번째 방법도 N만큼의 시간이 필요함!
<숙제>
- 문자열 뒤집기
뭔소리인지 잘 모르겠는데 일단 이렇게 짜봤다
def find_count_to_turn_out_to_all_zero_or_all_one(string):
zero_count = 0
one_count = 0
for i in string:
if i == "0":
zero_count += 1
else:
one_count += 1
count = 0
for zero_one in range(len(string)):
if one_count > zero_count:
if string[zero_one] == "0":
string[zero_one] = "1"
count += 1
else:
if string[zero_one] == "0":
string[zero_one] = "1"
count += 1
return count
오류가 났다..ㅎ
string[zero_one] = "1"
~~~~~~^^^^^^^^^^
TypeError: 'str' object does not support item assignment
머리가 안 돌아가서 걍 답지를 봤다
input = "011110"
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
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)
위 코드는 답지를 고대로 베낀 코드인데 출력화면이 1이 떴다
0을 두 번 바꿔야 하니까 2가 떠야 하는데...
코드를 자세히 보았다
인덱스 i와 인덱스 i + 1이 같을 경우가 안 적혀 있었다
그래서
else:
if string[i] == '0':
count_to_all_one += 1
if string[i] == '1':
count_to_all_zero += 1
이 코드를 추가했다
그랬더니 어떤 0과 1의 조합을 넣어도 답이 맞게 출력됐다
input = "011110"
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
else:
if string[i] == '0':
count_to_all_one += 1
if string[i] == '1':
count_to_all_zero += 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
