자료구조와 알고리즘

• 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론
• 효율적인 자료구조란?
  프로그램의 실행시간 효율과 저장공간 효율을 의미한다.
  (실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해주는 것이 효과적으로 설계되었다고 할 수 있는 자료구조다.)
• 각 자료구조의 장단점을 숙지, 상황별로 적합한 자료구조를 선택하는 능력이 중요하다.
• 자료구조 : 데이터를 어떤 구조로 저장하고, 탐색하고, 삭제해야 가장 효율적인가?
  (메모리를 가장 효율적으로 사용할 수 있는 방법이 무엇일까? -> 실행속도에 영향)
  알고리즘 : 문제를 해결하는 방법론

알고리즘

• 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임, 집합
• 어떤 값을 입력으로 받아 원하는 값으로 출력하는 잘 정의된 계산 절차 를 말한다. 따라서 알고리즘은 어떤 입력을 어떤 출력으로 변환하는 일련의 계산 과정이라 할 수 있다.

알고리즘 예제1

• 최댓값 구하기 방법1

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)

• 최댓값 구하기 방법2

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)

• 둘 중 어느 방법이 더 효율적으로 보이는지?
  
  

알고리즘 예제2

• 알파벳 빈도수 세기

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26    # 알파벳 별로 빈도수를 저장하기 위한 길이가 26인 것을 0으로 초기화된 배열을 만들어 놨음
                                            # 26인 이유는 알파벳이 a~z까지 26개이기 때문
    for char in string:                     # 배열의 한 원소씩 돌린다.
        if not char.isalpha():              # 알파벳이 아니면
            continue                        # 반복문의 다음 인덱스로 넘어가는 방법, char가 알파벳이면 continue를 지나 다음 코드 실행
        arr_index = ord(char) - ord("a")    # ord(char) - ord("a") 의 값이 배열의 인덱스값이 됨.
        alphabet_occurrence_array[arr_index] += 1
    return alphabet_occurrence_array

print(find_alphabet_occurrence_array("hello my name is sparta"))

알고리즘 예제2

• 최빈값 찾기

# 첫번째 방법 : 각 알파벳마다 문자열을 돌면서 몇 글자가 나오는지 확인하는 것
input = "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", "w", "x", "y", "z"]
# 알파벳을 하나하나 비교해주어야하기에 다 적어놓음 하나하나 꺼내서 input에 있는 알파벳과 비교해보고 있다면 빈도수를 업데이트해줌.
# 가장 최고가 나오면 변환하자. 최고로 많이 나온 횟수를 저장하기 위한 변수(max_occurrence)와
# 최고로 많이 나왔던 알파벳을 저장하기 위한 변수(max_alphabet) 두 가지가 필요
    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_occurrence = occurrence
            max_alphabet = alphabet

    return max_alphabet


result = find_max_occurred_alphabet(input)
print(result)

# 두번째 방법 : 꿀팁이었던 alphabet_occurrence_array 활용
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  # 최대로 많이 발생했던 알파벳을 가지고싶다
                                                   # alphabet_occurrence_array을 비교하며 최고로 많이 나온 알파벳을 찾아야한다.
    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        # index 0 -> alphabet_occurrence 3
        alphabet_occurrence = alphabet_occurrence_array[index]

        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)