[알고리즘] 최댓값, 최빈값

Yungsang Hwang·2022년 7월 20일
algorithm알고리즘최댓값최빈값
0

알고리즘

목록 보기
1/1

알고리즘 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"))
profile
Yungsang Hwang
하루종일 몽상가

0개의 댓글