자료구조, 알고리즘 1주차

와우 처음에는 그냥 저냥 했는데 알고리즘이란 게 참 어렵구나 ㅎㅎ 많은 문제들을 풀면서 익숙해지는 수밖에 없다.

1주차에는 파이참으로 파일 관리하는 방법, 파일/폴더 이름짓기부터 시작해서

숫자열과 문자열을 처리하는 연습문제들을 풀어봤고

시간 복잡도와 공간 복잡도, 점근 표기법의 개념에 대해 알아보았다.

마지막에 푼 반복되지 않은 문자와 숙제 문자열 뒤집기가 어려웠다.

 

1. 알고리즘

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

 

2. 최댓값 찾기

첫번째 방법: 각 숫자마다 모두 다른 숫자들과 비교한다.

여기에는 for문이 두 번이나 쓰였다. for문에서 괄호를 쓰지 않게 조심해야 하고

중간 중간마다 break나 continue를 써주기. 마지막에는 return 값까지 넣어주기.

 

두번째 방법: 가장 큰 변수 만들고, 배열을 돌아가면서 그 변수와 비교하고 대입하기.

 

3. 최빈값 찾기

1) 첫번째 단계: 알파벳별 빈도수 찾기

① str.isalpha() 를 통해 문자인지 확인한다.

② for문에서 문자인지 먼저 확인할 때 if not이 먼저 나오게 한 후 아닐 경우 continue 써주기

③ 그 다음에는 else 쓸 필요 없이 바로 arr_index를 지정해준다.

④ 알파벳별 빈도수 저장하기 위해 길이가 26인 배열 만들어준다. alphabet_occurrence_array = [0] * 26

⑤ 배열의 각 원소에 알파벳마다 빈도수 추가한다. 아스키 코드 참고. ord(alphabet) - ord("a")

⑥ 배열에 하나씩 추가 alphabet_occurrence_array[arr_index] += 1

 

2) 두번째 단계: 가장 빈번하게 등장한 알파벳 찾기

① 각 알파벳들을 하나하나 문자열과 비교하면서 몇 번 나왔는지 검사한다.

for 구문이 두 번 쓰이고, alphabet_array = ["a", "b",... "z"] 설정해주어야 한다.

초기값 설정 max_occurrence = 0, max_alphabet = alphabet_array[0]

 

② 각 알파벳의 빈도수를 alphabet_occurrence_list라는 변수에 저장한다.

③ 각 문자열을 돌면서 해당 문자가 알파벳인지 확인한다.

④ 알파벳을 인덱스화시켜 알파벳 빈도수를 업데이트한다.

for index in range(len(alphabet_occurrence_array)):

  alphabet_occurrence = alphabet_occurrence_array[index]

 

⑤ 알파벳의 빈도수가 가장 높은 인덱스를 문자로 찾는다.

chr(max_alphabet_index + ord('a'))

 

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(input)
print(result)

코드 출처: 스파르타 코딩클럽

 

4. 시간복잡도

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

입력값이란 함수에서 크기가 변경될 수 있는 값이다.

입력값의 길이를 N으로 나타내고, 상수를 신경쓰지 않는다.

예를 들어 N의 제곱이나 N등의 비교를 통해 시간복잡도가 짧은 코드를 선택한다.

 

5. 공간복잡도

공간복잡도란 입력값과 문제를 해결하는 데 걸리는 공간의 상관관게이다.

대부분의 문제에서는 알고리즘의 성능이 공간보다는 시간복잡도에 의해 결정된다.

 

6. 점근표기법 (Asymptotic Notation)

점근표기법은 알고리즘의 성능을 수학적으로 표기하여 효율성을 평가하는 방법이다.

알고리즘의 성능은 항상 같은 것이 아니라 입력값의 분포에 따라 변할 수 있다.

빅오 표기법은 최악의 성능을, 빅오메가 표기법은 최선의 성능을 전제로 어느정도의 연산량이 걸릴지에 대해 다룬다.

우리는 최악의 경우에 대비하므로 빅오 표기법을 중시한다.

 

7. 알고리즘 연습문제 1: 곱하기 vs 더하기

배열에 있는 수가 0이나 1일 때는 더하기, 나머지 숫자는 곱하기.

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


def find_max_plus_or_multiply(array):
    max_cal = 0
    for element in array:
        if element <= 1 or max_cal <= 1: // |말고 or로 써주기
            max_cal += element
        else:
            max_cal *= element
    return max_cal


result = find_max_plus_or_multiply(input)
print(result)

8. 알고리즘 연습문제 2: 반복되지 않은 문자

핵심은 문자가 몇 번 나왔는지 저장하는 방법을 생각해내는 것이다.

앞에서 최빈값 찾기 첫번째 단계인 알파벳별 빈도수 찾기를 이용하면 편리하다.

input = "abadabac"

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


result = find_not_repeating_first_character(input)
print(result)

9. 알고리즘 연습문제 3: 소수 나열하기

내가 푼 답은 비효율적이라네 ㅠㅠ 뚀륵 왜그런지 보자.

input = 20


def find_prime_list_under_number(number):
    prime_list_array = []
    for num in range(1, number+1):
        if num > 1: //소수는 1보다 크다
            for i in range(2, num): //2부터 num까지의 수 중에
                if num % i == 0: //그 수로 나누어 떨어지면 소수가 아니다
                    break
                    //비효율적인 이유: 2부터 num-1까지 모든 수로 나누어 떨어지지 않는지 확인하기보다는
                    //2부터 n-1까지 "모든 소수"로 나누어 떨어지지 않는지 알아보도록 해야 한다.
                    //ex. 2와 3으로 나누어 떨어지지 않는다면 2*3=6으로도 나누어 떨어지지 않는다
            else:
                prime_list_array.append(num) // 어떤 수로도 나누어 떨어지지 않은 수를 소수 배열에 추가한다
    return prime_list_array


result = find_prime_list_under_number(input)
print(result)

 

1차 개선 방법

input = 20


def find_prime_list_under_number(number):
    prime_list_array = []
    for num in range(2, number + 1):
        for i in prime_list_array: //구한 소수들 중에
            if num % i == 0: //어떤 소수로 떨어지면 소수가 아니다
                break
                //개선 이유: 2부터 n-1까지 "모든 소수"로 나누어 떨어지지 않는지 알아보도록 해야 한다.
        else:
            prime_list_array.append(num) // 어떤 수로도 나누어 떨어지지 않은 수를 소수 배열에 추가한다
    return prime_list_array


result = find_prime_list_under_number(input)
print(result)

//아직도 비효율적인 이유: 자연수 n이 소수이기 위한 필요충분조건
//n이 n^2보다 크지 않은 어떤 소수로도 나눠지지 않는다는 점을 이용해서
//i^2 <= n 일때까지만 비교하기

 

2차 개선 방법

input = 20


def find_prime_list_under_number(number):
    prime_list_array = []
    for num in range(2, number + 1):
        for i in prime_list_array: //구한 소수들 중에
            if num % i == 0 and i * i <= num://어떤 소수로 떨어지면 소수가 아니고
            				//어떤 소수의 제곱근이 확인하는 수보다 작을 때까지만 비교한다
                break
        else:
          prime_list_array.append(num) // 어떤 수로도 나누어 떨어지지 않은 수를 소수 배열에 추가한다
    return prime_list_array


result = find_prime_list_under_number(input)
print(result)

내가 짠 게 맞다고 생각했는디... 모든 알고리즘은 개선할 수 있다는 생각을 갖고 효율성을 찾아 많이 고민해봐야 한다.

 

10. 알고리즘 연습문제 4: 문자열 뒤집기

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

처음에는 문제 자체를 이해 못하다가 여러가지로 구글링하다가 여타 다른 문제와는 조금 다르다는 걸 알게 되었다.

첫째는 010101을 101010으로 바꾸는 게 아니라, 000000이나 111111로 한 가지 숫자로 바꾸는 게 관건이고,

둘째는 이 두가지 방법 중에서 어느 것이 최소 횟수로 뒤집을 수 있는지를 min으로 비교해야 하는 게 최종 목적이다.

 

input = "011110"

// 0에서 1로, 1에서 0으로 변하는 순간에 주목해야 한다.
// 전체를 0으로 또는 1로 만들기 위한 숫자를 계산하기.

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 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]:
            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_zero, count_to_all_one)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

마지막 숙제는 고민하는 시간이 30분을 넘었지만 못풀어서 정답을 봤다.

이 배움을 통해 다음에는 전체를 0으로, 또는 1로 만드는 수를 세는 생각을 할 수 있었으면 좋겠다.