알고리즘 4일차

알고리즘 더 풀어보기(1)

• Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
  단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
• 문제 코드

  [0, 3, 5, 6, 1, 2, 4]
  
  def find_max_plus_or_multiply(array):
      return 1
  
  result = find_max_plus_or_multiply
  print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
  print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
  print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

• 이 문제 알고리즘의 핵심은 0과 1을 곱했을 때는 더하는 것이 오히려 더 클 것이라는 것
• 그렇다면 참조하는 숫자 값에 0과 1이 있다면 더해보고, 1보다 크다면 곱해보는 분기 조건을 추가해보자
• 정답 코드

  def find_max_plus_or_multiply(array):
      multiply_sum = 0
      for number in array:
          if number <= 1 or multiply_sum <= 1:
              multiply_sum += number
          else:
              multiply_sum *= number
      return multiply_sum
  
  result = find_max_plus_or_multiply
  print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
  print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
  print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

• 역설계 코드

  def find_max_plus_or_multiply(array):
      multiply_sum = 0
      for number in array:
          if number <= 1 or multiply_sum <= 1:
              multiply_sum += number
          else:
              multiply_sum *= number
      return multiply_sum
  
  result = find_max_plus_or_multiply
  print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
  print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
  print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

  • 의사코드로 적어보기
    1. 멀티플썸은 영이다.
    2. 어레이 중에 넘버1 넘버2 이렇게 들어가겠지 그렇게 돌아가
    3. 만약 그 넘버가 1보다 작거나 같 또는 멀티플썸이 1보다 작거나 같으면
    4. 멀티플썸은 멀티플썸 더하기 넘버임
    5. 아니면 멀티플썸은 멀티플썸 곱하기 넘버임 돌아돌아
    6. 멀티플썸을 리턴해줘

    ---

  • 로직을 설계

    1. 멀티플썸이라는 변수가 하나 필요
    2. 곱하기와 더하기가 경우가 다르다는 것을 인지
    3. 곱하기의 경우가 나왔을 때는 멀티플썸에서 곱해주고
       1. 곱해주기 위한 조건은 0과 1이 아니어야 한다
    4. 더하기의 경우가 나왔을 때는 멀티플썸에서 더해주고
       1. 더해주기 위한 조건은 0과 1이어야 한다
    5. 분기마다 조건이 다르면 if 써주기
    6. 배열을 돌아야 하니까 for 안에 if
    7. 마지막에 멀티플썸을 리턴

알고리즘 더 풀어보기(2)

• Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
• 문제 코드

  input = "abadabac"
  
  def find_not_repeating_first_character(string):
      # 이 부분을 채워보세요!
      return "_"
  
  result = find_not_repeating_first_character
  print("정답 = d 현재 풀이 값 =", result("abadabac"))
  print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
  print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

• 정답 코드

  input = "kim hee jeong"
  
  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
  
  		[0,0,1,.,1,5,2,6,2]
  
  		not_repeat = []
      for index in range(len(alphabet_occurrence_array)):
  				a,b,c 순서대로
  				0,0,1,.,1,5,2,6,2
          count = alphabet_occurrence_array[index]
  
          if alphabet_occurrence == 1:
  						a 에 있나..? 1이네 그럼 a 추가
  						b 에 있나..? 0이네 그럼 패스
              not_repeating_character_array.append(chr(index + ord("a")))
  						not_ repeat는 알파벳 순서대로 [g h i k m n o] 가 된다
  
  		a,b,c 순서대로라면 무작위 문자열이 아닌 abc 중에서 제일 빠른놈이 나와버렷
  		그걸 방지하기 위해서 무작위 문자열인 인풋을 다시 참조!
      for char in string:
  				char = k i m h e e j e o n g
          if char in not_repeating_character_array:
  						k가 not_repeat 안에 들어있냐? 응! 바로 빼!
              return char
  
      return "_"
  
  result = find_not_repeating_first_character
  print("정답 = d 현재 풀이 값 =", result("abadabac"))
  print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
  print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

  • 코드 한글 번역하기 자 음 뭐라 말해야대징 알파벳 a~z를 집어넣을 [0]*26어레이를 만들어줍니다 포문으로 string안에서 char를 돌려요 if로 char가 알파벳이 아니라면! 진행한다 arr_index 는 ord(char) - ord(”a”) 가 나오죠 ⇒ 아스키코드 숫자-아스키코드숫자 위에 나온것을 아까만든 어레이 배열에 +1해서넣어요 not_repeating_character_array= [] 라는 빈 어레이를 만듭니다 alphabet_occurrence_array 길이만큼 range 안에서 index를 포문을 돌려요 alphabet_occurrence = alphabet_occurrence_array[index] 어음.. 입력한 값의 알파벳이 들어간 빈도 값을 변수로 저장합니다 네 그렇습니다 이제 if문으로 alphabet_occurrence 가 1이라면? not_repeating_character_array 에 chr(index+ord(”a”)) 로 문자로 변환해서 리스트에 넣어줍니다 아 그쳐 chr이니까 문자로 변환해서! 여기까지 하고 for문으로 다시 string안에서 char를 돌려요 if문으로 not_repeating_character_array안에 char 있따면 바로 char를 반환해라! 없다면? “_”를 반환해라
    
  • 로직
    • 빈도 수를 활용하는 알고리즘 코드 사용해서 입력받은 문자열을 반복문을 돌려 빈도 값을 26개 길이의 리스트에 저장하기
    • 저장한 리스트를 반복해서 각 요소의 값이 1인 인덱스에 해당하는 문자를 뽑아서 새로운 리스트에 저장하기
    • 다시 입력받은 문자열을 반복문을 돌려 값이 1인 리스트 안의 문자와 일치하면 바로 리턴해버리기
  • 의사코드