🍭알고리즘 Algorithm 공부 1일차

🤖 알고리즘이란?

• 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합
• 여러 단계 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다
• 알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다.

📚 알고리즘을 공부해야 하는 이유

• 좋은 개발자가 되기 위해

  • 좋은 개발자란 좋은 프로그램을 구현할 줄 알아야함
  • 좋은 프로그램이란? 적은 공간을 이용 빠른 속도로 수행하는 프로그램
  • 즉 좋은 프로그램을 위해선 특정자료구조나 접근방법을 사용해야 함

• 좋은 회사에 취직하기 위해

  • 유망 IT기업 외에도 많은 스타트업까지 코딩테스트를 개발자의 필수 관문으로 삼고있음

  • 기초적인 지식과 해결책으로 적절한 사고를 할 수 있는지에 대한 검증

    ---

📌 최대값 찾기

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

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

• 첫번째 방법 문제풀이 (다중 포문으로 풀기)

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)

• 두번째 방법 문제풀이 (지정 변수로 풀기)

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)

🔠 최빈값 찾기

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

  def find_max_occurred_alphabet(string):
      # 이 부분을 채워보세요!
      return "a"
  
  result = find_max_occurred_alphabet(input)
  print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
  print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
  print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

• 참고! 문자인지 확인하는 방법

  • 파이썬의 내장함수 str.isalpha()를 이용

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

  • 알파벳 별로 빈도수를 리스트에 저장하기

    # [0,0,0,0,0,0,...,0,0]
    alphabet_occurrence_array = [0] * 26

  • 컴퓨터는 0과 1숫자 밖에 모름, 때문에 문자도 숫자로 기억함

  • 이때 어떤 숫자와 어떤 문자를 대응시키는가에 따라 여러가지 인코딩 방식이 있는데 통상 아스키 코드 방식을 많이 사용함

• 참고! 문자를 아스키 코드로 변환하는 법

  # 내장 함수 ord() 이용해서 아스키 값 받기
  
  print(ord('a')) 

• 풀이

  1. 필요한것

     • 문자를 숫자로 변경하는 방법
     • 알파벳이 몇 번 들어올 지 저장할 방법
     • 어떤 알파벳이 가장 많이 들어왔는지 확인할 방법
     • 가장 많이 들어온 알파벳을 리턴

  2. 필요한 코드 작성법

     1. 문자를 숫자로 변경하는 방법

        • 컴퓨터는 문자를 아스키코드로 인식한다!
        • 아스키코드 번호(정수)로 변경하는 파이썬 메서드 ord("알파벳") 을 사용한다

        alphabet = "a"
        ord_alphabet = ord(alphabet)
        print(ord_alphabet)

     2. 알파벳이 몇 번 들어올 지 저장할 방법

        • 이 중에서 알파벳이 몇 번 들어있는지 확인하려면 뭔가 저장해줄 공간이 필요하다
        • 알파벳 a-z를 예시로 26개의 각 공간을 담고 있는 리스트를 만들어 본다

        alphabet_list = ["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"]

        • 이렇게 알파벳이 들어있는 리스트를 일일이 알파벳을 달면서 만든다면, 어떤 알파벳인지 확인하는 것은 그렇다 치더라도, 어디에 저장할 것이냐는 물음이 생긴다.
        • 그렇다면 0이 a이고, 25가 z라고 상정한 0이 들어있는 리스트를 만들어 알파벳이 있을 때마다 1을 더해줘 기록하는 리스트를 만들어 본다면?

        alphabet_list = [0] * 26

        • 간단하면서 저장할 수 있는 공간이 마련되었다.

     3. 어떤 알파벳이 가장 많이 들어왔는지 확인할 방법

        • 알파벳이 얼마나 들어올지 저장할 수 있는 리스트가 만들어진 상태에서 확인할 알파벳이 몇 번째 인덱스에 해당하는지 확인하여 1을 더해주면 카운트가 되는 셈이다.
          • 확인한 알파벳은 몇 번째 숫자인지 확인하기 —> ord() 사용
          • ord() 를 사용하여 확인한 정수를 index로 활용하기
          • 리스트[인덱스] 의 값을 1 더해주기

     4. 가장 많이 들어온 알파벳을 리턴

        • 리스트에 가장 많이 담긴 값이 몇 번째 인덱스인지 가져가야 한다
          • 필요한 것은 몇 번째 알파벳인지이다. 몇 번 들어왔느냐가 아니다!
        • 최댓값을 구하는 알고리즘을 구해서 그 값에 해당하는 인덱스를 구하자
        • 인덱스를 구하는 메서드는 리스트.index(값) 이다.

        list_fruits = ["사과", "배", "체리"]
        favorite_fruit = "배"
        index_num = list_fruits.index(favorite_fruit)

  3. 알고리즘 작성 및 코딩

     1. 알고리즘 작성

        1. 입력받은 문자를 알파벳 단위로 잘라내기

           • 입력받은 문자는 공백을 포함하여 단어로 묶여있다. 한 글자 단위로 자르자
           • list() 메서드를 사용하면 글자 단위로 분해할 수 있다.

           source_sentence = "go go coding of co! 0719-2022"
           source_list = list(source_sentence)

           • 이렇게 작성하면 리스트 안의 데이터가 알파벳, 특수문자, 숫자, 공백 등이 다양하게 들어오게 된다.
           • 알파벳 검사 메서드 str.isalpha(값) 을 사용해서 알파벳인 값만 리스트에 담아주자

           source_list = []
           for char in list(source_sentence):
           	if str.isalpha(char):
           		source_list.append(char)

           • 이렇게 입력받은 문자를 알파벳 단위로 잘라 리스트로 저장까지 했다!

        2. 알파벳 리스트 작성

           • 다음은 위의 입력 알파벳들을 한 번씩 확인하면서 각 알파벳을 카운트할 공간이 필요하다

           alphabet_list = [0] * 26

           • 입력받은 알파벳이 A-Z까지 있을 가능성이 있기에 26개의 알파벳을 모두 저장할 공간을 만든 것이다

        3. 알파벳 카운트

           • 입력 받은 문자를 알파벳으로 담아둔 source_list
           • 알파벳 a-z 카운트할 수 있는 26길이의 리스트 alphabet_list
           • 두 가지의 리스트를 가지고 알파벳이 몇 번 들어갔는지 카운트한다
           • 반복문으로 source_list를 슬라이싱하여 어떤 알파벳인지 확인하고

           for char in source_list:
           	# 알파벳을 번호로 만들기
           	ord(char)
           	# 알파벳을 0~25 사이의 숫자로 만드려면 a~z의 값에서 a를 빼주면 된다!
           	target_index = ord(char) - ord("a")

           • 알파벳에 해당하는 번호를 찾아 alphabet_list에 카운트한다

           for char in source_list:
           	target_index = ord(char) - ord("a")
           	alphabet_list[target_index] += 1

        4. 알파벳 최댓값, 최빈값 찾기

           • 이제 source_list의 알파벳을 alphabet_list 리스트에 카운트했다.
           • 카운트가 가장 많이 된 최대수를 찾고 나서 해당 값의 인덱스를 찾자

           max_num = alphabet_list[0]
           for num in alphabet_list:
           	if num > max_num:
           		max_num = num
           # 최대수를 값으로 인덱스 찾아내기
           target_index = alphabet_list.index(max_num)
           # chr을 사용해서 다시 문자로 변환
           target_char = chr(target_index)

     2. 코드

     source_sentence = "go go coding of co! 0719-2022"
     
     source_list = []
     for char in list(source_sentence):
     	if str.isalpha(char):
     		source_list.append(char)
     
     alphabet_list = [0] * 26
     
     for char in source_list:
     	target_index = ord(char) - ord("a")
     	alphabet_list[target_index] += 1
     
     max_num = alphabet_list[0]
     for num in alphabet_list:
     	if num > max_num:
     		max_num = num
     target_index = alphabet_list.index(max_num)
     target_char = chr(target_index)

• 튜터님의 풀이
  • 첫번째 풀이

    1. 각 알파벳마다 문자열을 돌며 몇 글자가 나왔는지 확인

    2. 먄약 그 숫자가 저장한 알파벳 빈도 수보다 크면, 그 값을 저장하고 제일 큰 알파벳으로 저장

    3. 이 과정을 반복!

       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"]
       
       		# 초기의 최빈값은 0, 리스트의 0번째 인덱스값(즉, "a")은 max_alphabet으로 설정
           max_occurrence = 0
           max_alphabet = alphabet_array[0]
       
       		# a-z 에서 a를 alphabet으로 돌림 (발생빈도는 0)
           for alphabet in alphabet_array:
               occurrence = 0
       				# 우리가 넣고 싶은 문자열의 첫 글자 넣기(H..e..l..l.o..m.....a!)
       				# alphabet과 같으면 발생빈도를 1 올리고 다시 for 돌림
               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"))

  • 두번째 풀이

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

    2. 각 문자열을 돌면서 해당 문자가 알파벳인지를 확인

    3. 알파벳을 인덱스화 시켜 각 알파벳의 빈도수를 업데이트

    4. 알파벳의 빈도수가 가장 높은 인덱스를 알아냈죠

    5. 여기서 max_alphabet_index가 0이기 때문에 인덱스를 문자로 변경해야 함!

    6. 아스키 코드번호를 실제 문자로 변환하려면 chr()함수를 사용

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