1. 알고리즘이란?

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전]
=> 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임

2. 최댓값 찾기, 최빈값 찾기 문제

최댓값 찾기

숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환하시오.

첫 번째 방법

각 숫자마다 모든 다른 숫자와 비교하여 최댓값인지 확인하고 만약 다른 모든 값보다 크다면 반복 중단 & 반환

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num<compare_num:
                break
        else:
            return num
# for else 문
# else문은 for문이 다 끝날 때까지 break 문이 한번도 나오지 않았다면 실행됨

result = find_max_num(input)
print(result)

두 번째 방법

최댓값을 저장할 변수를 만들고 배열을 하나씩 돌면서 각 숫자와 최댓값을 비교하면서 최댓값을 찾아 반환

input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    max_num = array[0]
    for num in array:
        if num>max_num:
            max_num = num
    return max_num


result = find_max_num(input)
print(result)

최빈값 찾기

문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오

첫 번째 방법

각 알파벳마다 문자열(입력값)을 돌면서 각 알파벳별로 몇 글자 나왔는지 확인
만약 그 숫자가 저장된 알파벳 최대 빈도수보다 크다면, 그 값을 최대 빈도수 값으로 저장하고, 최대 알파벳 변수에도 해당 알파벳 저장.

input = "hello my name is sparta"


# input에 a 몇 개인지 비교해서 세고 그 다음에 b 몇 개인지 비교해서 세기
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:
        occurrence = 0
        for char in string:
            if alphabet == char:
                occurrence += 1
        if max_occurrence < occurrence:
            max_occurrence = occurrence
            max_alphabet = alphabet
    return max_alphabet

result = find_max_occurred_alphabet(input)
print(result)

두 번째 방법

각 알파벳별 빈도수 저장 -> 빈도수 중 가장 많은 빈도 수 인덱스를 이용해 알파벳 반환

input = "hello my name is sparta"


# input에 a 몇 개인지 비교해서 세고 그 다음에 b 몇 개인지 비교해서 세기
def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        if not char.isalpha():
            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[0]
        if alphabet_occurrence > max_occurrence :
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence
    return chr(max_alphabet_index+ord('a'))


result = find_max_occurred_alphabet(input)
print(result)

내 코드

코드input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    alphabet = [0]*26
    for char in string:
        if not char.isalpha():
            continue
        num = ord(char) - ord('a')
        alphabet[num] += 1

    for number in alphabet:
        for compare_number in alphabet:
            if number<compare_number:
                break
            else: return chr(alphabet.index(number)+ord('a'))


result = find_max_occurred_alphabet(input)
print(result)를 입력하세요

3. 시간 복잡도, 공간 복잡도, 점근 표기법

시간 복잡도

입력값과 문제를 해결하는데 걸리는 시간과의 상관관계.
입력값이 2배로 늘어났을 때, 문제를 해결하는 데 걸리는 시간은 몇 배 늘어나는 지 판단.

구하는 방법 (최댓값 찾기)

for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num

위에서 연산된 것들을 더해보면,
array의 길이 X array의 길이 X 비교 연산 1번
만큼의 시간이 필요. 여기서 array(입력값)의 길이는 보통 N이라고 표현.
=> N × N = N^2
그러면 이 함수는 N^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

위에서 사용된 공간들을 더해보면,
1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
=> 26+4 = 30
30만큼의 공간 필요 판단.

But 공간을 적게 쓴 알고리즘이 더 효율적인 알고리즘이냐?
NO!
공간 사용에 있어서 상수값이 나온 경우, 비교 의미 없다. 이처럼, 대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않는다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다.

4. 곱하기 or 더하기, 반복되지 않는 문자 문제

곱하기 or 더하기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫
자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.

단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

input = [0, 3, 5, 6, 1, 2, 4]


def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for element in array:
        if element <= 1 or multiply_sum <= 1:
            multiply_sum += element
        else:
            multiply_sum *= element
    return multiply_sum

# 함정에 유의 0뿐만 아니라 1도 더해야 한다. 곱하는 것보다
# 더하는 것이 더 값을 크게 만든다.


result = find_max_plus_or_multiply(input)
print(result)

반복되지 않는 문자 문제

Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그
런 문자가 없다면 _ 를 반환하시오.

input = "abaaba"


def find_not_repeating_character(string):
    alphabet_occurrence_array = [0] * 26
    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        if alphabet_occurrence_array[index] ==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)

오늘 배운 몰랐던 개념

.isalpha()

파이썬의 내장 함수 str.isalpha() 를 이용하면 해당 문자열이 알파벳인지 확인 가능

print("a".isalpha()) # True
print("1".isalpha()) # False
s = "abcdefg"
print(s[0].isalpha()) # True

for else문

else문은 for문이 다 끝날 때까지 break 문이 한번도 나오지 않았다면 실행됨

input = [3, 5, 6, 1, 2, 4]

def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num<compare_num:
                break
        else:
            return num

result = find_max_num(input)
print(result)

ord()

ord(c)는 문자의 유니코드 값을 돌려주는 함수이다.

>>> ord('a')
97

chr()

chr(i)는 유니코드(Unicode) 값을 입력받아 그 코드에 해당하는 문자를 출력하는 함수이다.

>>> chr(97)
'a'

min()

min(iterable)은 max 함수와 반대로, 인수로 반복 가능한 자료형을 입력받아 그 최솟값을 돌려주는 함수이다.

>>> min([1, 2, 3])
1
>>> min(count_to_all_one,count_to_all_zero)
3

질문

alphabet_occurrence_array = [0] * 26 

와 같은 대입 연산도 대입 연산 1번으로 생각하는 걸까요?
-> 대입 연산자의 실제 실행 동작에 따라 다르다고 볼 수 있을 것 같습니다! 예를 들어 모든 배열의 값을 찾는 find라는 함수들은 연산 1번으로 값을 찾능 것이 아닙니다. 따라서 연산마다 다르다고 볼 수 있을 것 같습니다!