스파르타 코딩클럽 알고보면 알기 쉬운 알고리즘 1주차

사용 언어 : Python

 

1. 최댓값 구하기

array는 숫자가 담긴 배열

 

나의 코드:

array가 음수로 이루어진 배열일 때 성립하지 않는다.

maxnum = array[0] 으로 고칠 수 있다.

def find_max_num(array):
    maxnum = 0
    for i in array:
        if maxnum < i:
            maxnum = i
    return maxnum

튜터 님의 코드 :

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


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]))

 

 

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


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. 알파벳별 빈도수 세기

힌트

# 문자인지 확인

print("a".isalpha())    # True
print("1".isalpha())    # False

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

# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a'))               # 97
print(ord('a') - ord('a'))    # 97-97 -> 0
print(ord('b') - ord('a'))    # 98-97 -> 1

 

나의 코드 : 

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26

    for i in string:
        if i.isalpha():
            index = ord(i)-ord('a')
            alphabet_occurrence_array[index] = alphabet_occurrence_array[index] + 1
    return alphabet_occurrence_array


print("정답 = [3, 1, 0, 0, 2, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("best of best sparta"))

 

튜터 님의 코드

def find_alphabet_occurrence_array(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

    return alphabet_occurrence_array

print("정답 = [3, 1, 0, 0, 2, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("best of best sparta"))

 

3. 최빈값 찾기

나의 풀이 : 

def find_max_occurred_alphabet(string):
    alphabet_num_array = [0] * 26
    maximum = alphabet_num_array[0]
    charlog = 0
    for char in string:
        if char.isalpha():
            index = ord(char) - ord('a')
            alphabet_num_array[index] += 1
    for i in alphabet_num_array:
        if i > maximum:
            maximum = i
            charlog = alphabet_num_array.index(i)
    answer = chr(charlog + ord('a'))
    return answer


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

 

튜터 님의 풀이 : 

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[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))


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

 

4. 시간 복잡도 

입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것

각 줄이 실행 = 1번의 연산

입력값의 길이는 보통 N

 

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


# 위 코드의 시간 복잡도
# array(입력값)의 길이 X array(입력값)의 길이 X 비교 연산 1번
# N*N = N^2

 

5. 공간 복잡도

저장하는 데이터의 양이 1개의 공간을 사용

알파벳을 저장하면 26

 

공간 복잡도 보다는 시간 복잡도를 신경써야 한다

 

6. 배열에서 특정 요소 찾기

나의 풀이

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


def is_number_exist(number, array):
    if number in array:
        return True


result = is_number_exist(7, input)
print(result)

튜터 님의 풀이

def is_number_exist(number, array):
    for element in array:
        if number == element:
            return True
    return False


result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

 

7. 점근 표기법

알고리즘의 성능을 수학적으로 표기하는 방법

 

빅오(Big-O)표기법

최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

e.g. O(N)

 

빅 오메가(Big-Ω)

최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지

e.g. Ω(1) 

 

8. 곱하기 or 더하기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다. [0, 3, 5, 6, 1, 2, 4]

 

 

나의 풀이

def find_max_plus_or_multiply(array):
    prev = [0] * (len(array)-1)
    prev[0] = array[0]
    for i in range(len(array)-2):
        if prev[i] + array[i+1] > prev[i] * array[i+1]:
            prev[i+1] = prev[i] + array[i+1]
        else:
            prev[i+1] = prev[i] * array[i+1]
    if prev[len(array)-2] * array[len(array)-1] > prev[len(array)-2] + array[len(array)-1]:
        return prev[len(array)-2] * array[len(array)-1]
    else:
        return prev[len(array)-2] + array[len(array)-1]


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]))

튜터님 풀이

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


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]))

 

현재 숫자나 다음 숫자가 0이나 1이 아니면 곱하기가 이득이다. 그러므로 계속 곱한다.

 

9. 반복되지 않는 문자

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

 

"abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!

 

나의 풀이

input = "abadabac"

def find_not_repeating_first_character(string):
    liststr = list(string)
    for i in liststr:
        if liststr.count(i) == 1:
            return i

    return "_"


result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

튜터 님의 풀이

def find_not_repeating_first_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)):
        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_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

10. 숙제 1 - 소수 나열하기

나의 풀이

- 해결하지 못함

input = 20


def find_prime_list_under_number(number):
    numlist = []
    for num in range(2, number +1):
        for i in range(2, num):
            for j in range(2, num):
                if i * j != num:
                    numlist.append(j)

    return numlist


result = find_prime_list_under_number(input)
print(result)

 

튜터 님의 풀이

input = 20


def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i * i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

 

11. 숙제 2 - 문자열 뒤집기

나의 풀이

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    strlist = list(string)
    zero =[]
    one = []
    for a in strlist:
        if a == "0":
            zero.append(a)
        elif a == "1":
            one.append(a)
    if len(zero) > len(one):
        return len(one)
    if len(zero) < len(one):
        return len(zero)
    if len(zero) == len(one):
        return len(zero)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

튜터 님의 풀이

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)