내일배움단 알고리즘 강의 1주차

# 알고리즘이란?

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

즉, 알고리즘이란 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임이다.

 

# 시간복잡도란?

- 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다.

# 공간복잡도란?

- 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다

 

 

시간 복잡도와 공간 복잡도가 작을 수록 좋은 알고리즘!

 

# 점근 표기법이란?

알고리즘의 성능을 수학적으로 표기하는 방법으로 알고리즘의 “효율성”을 평가하는 방법이다. 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.

점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기한다.

알고리즘은 보통 빅오 표기법으로 분석한다. 왜냐하면 대부분의 입력값은 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문에.....

 

1. 입력값에 비례해서 얼마나 늘어날지 파악해보자. 1 ? N ? N^2 ?

2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.

3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자

---

<문제1>

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

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

 

<문제풀이>

배열의 첫번째 숫자를 max_num으로 주고 비교해 가면서 max_num보다 크다면 그 숫자를 max_num으로 바꿔주었다.

array = [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
    
print(find_max_num(array))

---

<문제2>

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

"hello my name is sparta"

 

<문제풀이>

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", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet


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

---

<문제3>

Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

 

<문제풀이>

input = 20


def find_prime_list_under_number(number):
    prime_list = [] # 소수를 넣을 list

    for n in range(2, number + 1): # 2부터 n 까지
        for i in prime_list: 
            if n % i == 0 and i * i <= n: # n이 소수로 나누어 지거나 소수의 제곱이 n보다 작으면 멈춰라
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

---

<문제4>

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

"011110"

 

<문제풀이>

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0 # 1을 0으로 바꾸는 횟수
    count_to_all_one = 0 # 0을 1로 바꾸는 횟수

    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]: # 다음 숫자랑 비교해서 서로 다를때 다음 숫자가 0이면 1로 바꾸고 1이면 0으로 바꾼다
            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)