[알고리즘] 스파르타 코딩 : 알고리즘 - 1주차

알고리즘 : 어떤 문제의 해결을 위해, 입력된 자료를 토대로 하여 원하는 출력을 유도해 해는 규칙의 집합

 

시간 복잡도 : 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

ㄴ 상수는 신경쓰지 않음!

 

공간 복잡도 : 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

 

공간 복잡도모다는 시간 복잡도를 더 신경써야 함

 

점근 표기법 : 알고리즘의 성능을 수학적으로 표기하는 방법, 알고리즘의 효율성을 평가하는 방법

ㄴ 빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸리는지?

ㄴㄴex) O(N)

ㄴ 빅 오메가(Big-Ω) 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸리는지?

ㄴㄴex) Ω(1) 

 

최댓값 찾기

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

def find_max_num(array):
    max_num = input[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"


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_alphabet_index = index
            max_occurrence = alphabet_occurrence

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


result = find_max_occurred_alphabet(input)
print(result)

 

곱하기 or 더하기

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

A. 1, 0일 때는 더하고, 나머지는 곱해야 가장 큰 수가 나옴

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


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

    return multifly_sum


result = find_max_plus_or_multiply(input)
print(result)

 

반복되지 않는 문자

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

A. 알파벳 빈도수 구한 뒤, 해당 문자열에서 빈도수 1인 알파벳 나오면 반환

input = "abacabade"


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_char_arr = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence == 1:
            not_repeating_char_arr.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_char_arr:
            return char
    return "_"

result = find_not_repeating_character(input)
print(result)

 

 

숙제

소수 나열하기

Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

A. 소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다

ㄴ개선1 -> 2부터 n-1까지의 모든 소수로 나누어 떨어지지 않으면 소수

ㄴ개선2 -> 소수 특징 : 소수 N은 N의 제곱근보다 작은 어떤 소수로도 나눠지지 않음 ( prime_list[i] * prime_list[i] <= N 일 때까지만 비교 )

input = 29


def find_prime_list_under_number(number):
    prime_list = []
    for n in range(2, number + 1):
        i = 0
        while len(prime_list) > i and prime_list[i] * prime_list[i] <= n:
            if n % prime_list[i] == 0:
                break
            i += 1
        else:
            prime_list.append(n)
    return prime_list
    
    
result = find_prime_list_under_number(input)
print(result)

 

문자열 뒤집기

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

 

A. 0에서 1로 변하는 순간 혹은 1에서 0으로 변하는 순간 뒤집는 횟수++됨

 

모두 0으로 만들기

0 -> 1이 될 때 count_to_all_zero += 1

 

모두 1으로 만들기

1 -> 0이 될 때 count_to_all_one += 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

    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)