22.09.19(월) Today I Learned

9/19 오늘의 시간표

09:00 ~ 10:00 [원격] 자료구조와 알고리즘
10:00 ~ 11:00 [원격] 자료구조와 알고리즘
11:00 ~ 12:00 [원격] 자료구조와 알고리즘
12:00 ~ 13:00 [원격] 자료구조와 알고리즘
13:00 ~ 14:00 점심식사
14:00 ~ 15:00 [원격] 자료구조와 알고리즘
15:00 ~ 16:00 [원격] 자료구조와 알고리즘
16:00 ~ 17:00 [원격] 자료구조와 알고리즘
17:00 ~ 18:00 [원격] 자료구조와 알고리즘
18:00 ~ 19:00 저녁식사
19:00 ~ 20:00 [실습] 실무적용 알고리즘 실습
20:00 ~ 21:00 [실습] 실무적용 알고리즘 실습

저번주 금요일과 동일한 시간표이다. 하지만 저번주에 비해서 학습의 갈피를 못잡고 헤메었던 부분이 약간이나마 해소가 되어서 이번주는 더 집중해서 공부할 수 있을 것 같은 기분이 들고 있다.

자료구조와 알고리즘 원격강의

저번 주는 1주차 내용의 절반 정도밖에 학습을 하지 못했다. 당장 내용을 따라가기에도 버겁기도 했고 파이썬 문법공부가 더 중요하다는 강박관념때문에 집중에서 강의 영상을 보지 못했다. 이번 주는 방향성이 어느정도 잡혔긴 하지만 그래도 역시 알고리즘 강의를 오래 잡고 있기 보다는 눈 앞의 목표를 우선적으로 처리하기로 했다. 그래서 1주차의 내용을 끝내는 것을 목표로 하였다.

08. 점근 표기법

• 점근 표기법이란?

  • 알고리즘의 성능을 수학적으로 표기하는 방법이다.

  • 알고리즘의 “효율성”을 평가하는 방법이다.

  • 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다.

  • 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다.

    • 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지를 표기한다.
    • 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지를 표기한다.

• 배열에서 특정 요소 찾기

  • Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.
  • A.

        def is_number_exist(number, array):
            for element in array:
                if number == element:
                    return True
            return False
        
        result = is_number_exist
        print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
        print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
        print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))

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

• 곱하기 or 더하기

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

             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]))
    			```
             

  • A.

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

10. 알고리즘 더 풀어보기 (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"))
            ```
            

  • A.

    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
    
        return "_"
    
    result = find_not_repeating_first_character
    print("정답 = d 현재 풀이 값 =", result("abadabac"))
    print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
    print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

11. 1주차 끝 & 숙제 설명

소수 나열하기

• Q1. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. (소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)

• A1.

input = 20


def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i * i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

풀이

소수는 약수가 자기자신과 1 밖에 없는 수를 뜻하기 때문에 소수를 구하는 함수를 우선 만들어준다. range의 범위를 2부터 number까지로 설정하기 위해 for문을 만들어주고 여기서 나온 n이라는 값을 2부터 n-1까지 나누어보고 이 때 나누어 떨어지지 않으면 소수이기 때문에 prime_list에 append해준다. 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다. 이를 이용해서 i * i ≤ n 일 때까지만 비교하면 된다.

문자열 뒤집기

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

      input = "011110"


      def find_count_to_turn_out_to_all_zero_or_all_one(string):
          # 이 부분을 채워보세요!
          return 1


      result = find_count_to_turn_out_to_all_zero_or_all_one(input)
      print(result)

-A2.

      input = "011110"


      def find_count_to_turn_out_to_all_zero_or_all_one(string):
          count_to_all_zero = 0
          count_to_all_one = 0

          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_one, count_to_all_zero)


      result = find_count_to_turn_out_to_all_zero_or_all_one(input)
      print(result)

풀이

"뒤집는 횟수"는 0에서 1로 변하는 순간 혹은 1에서 0으로 변하는 순간이다.

0에서 1로 변한다는 소리는, 0으로 다시 뒤집어야 하니 전체를 0으로 만들기 위한 숫자가 +1 된다.
1에서 0으로 변한다는 소리는, 1로 다시 뒤집어야 하니 전체를 1로 만들기 위한 숫자가 +1 된다.

1) 뒤집어 질 경우
2) 첫 번째 원소가 0인지 1인지
에 대해서 계산하면, 모두 0으로 만드는 횟수와 모두 1로 만드는 횟수를 만들 수 있다. 그리고 0으로 만드는 횟수와 모두 1로 만드는 횟수 둘 중 최솟값을 반환해주면 답을 구할 수 있다.

입력값의 첫번째 숫자가 0일 경우 문자열을 모두 1로 만드는 최소 뒤집는 횟수를 +1 해주고 반대로 첫번째 숫자가 1일 경우 문자열을 모두 0으로 만드는 최소 뒤집는 횟수를 +1 해준다.

for문을 만들어 두번째 세번째 ~ input값의 자릿수 만큼 계산해 0이냐 1이냐에 따라 뒤집는 횟수를 1씩 더하는 함수를 만든다. 그렇게 해서 뒤집는 횟수를 구했을때 모두 0일때와 모두 1일때 중 뒤집는 횟수가 더 적은쪽을 구하도록 min함수를 이용해 값을 return해준다.

마지막으로 해당 결과값을 print해주도록 코드를 작성해준다.

이렇게 알고리즘 1주차까지 끝을 냈는데 상상 이상으로 시간이 많이 쓰여서 놀랐다. 괜히 알고리즘 원격강의를 억지로 듣고 이해하려 하지말라고 하셨는지 확실하게 이해할 수 있었다. 아무래도 내일부터는 2주차 알고리즘 강의를 듣는 것보다는 당장 할 수 있는 것들을 다 끝내고 그 뒤에 여유가 생기면 그때 가서 알고리즘에 손을 대 보는 쪽으로 해야 시간을 효율적으로 사용할 수 있을 것 같다.

거북이반 study내용

오늘은 어제 과제로 내어주신 가위바위보 게임 만들기 과제에 대한 해설이 우선 있었다.

import random

option = ["가위", "바위", "보"]
computer = random.randint(0, 2)
computer_value = option[computer]

while True:
    user_value = input("가위 바위 보?")
    if user_value in option:
        break
    else:
        print("값을 정확히 입력해주세요!")

print(f"플레이어는 {user_value}를 선택, 컴퓨터는 {computer_value}를 선택했습니다")


if computer_value == user_value:
    print("비겼습니다")
elif user_value == "가위":
    if computer_value == "바위":
        print("졌습니다")
    else:
        print("이겼습니다")
elif user_value == "바위":
    if computer_value == "보":
        print("졌습니다")
    else:
        print("이겼습니다")

elif user_value == "보":
    if computer_value == "가위":
        print("졌습니다")

    else:
        print("이겼습니다")
else:
    print("예상치 못한 경우입니다")

풀이
랜덤함수를 활용하여 컴퓨터의 가위바위보 값을 랜덤으로 받아오도록 한다. 그리고 input값을 입력했을 때 입력값이 가위바위보에 해당하지 않을 경우 재입력 메세지를 출력하고 올바로 입력했을 경우 나의 입력값과 컴퓨터가 랜덤으로 받아온 값을 비교하여 승패를 결정하는 조건문 함수를 만든다. 그리고 그 결과값을 출력하도록하고 오류발생시 오류메세지를 출력하도록 설정한다.

여기까지가 가위바위보게임 만들기 기본과정이었고 이제 여기서 모듈화를 하는 것이 내일까지 해야하는 과제가 될 것이다.

오늘 할 일을 끝내고

알고리즘 강의가 어제에 비해 시간이 너무 오래 걸려 막상 TIL을 작성하니 분량이 생각보다 안나와서 오늘의 공부량이 적게 느껴진다. 하지만 그 안에서 영상을 4번 5번씩 돌려보며 문제를 이해하고 확실하게 풀려는 노력이 있었으니 괜찮다. 대신 이런 공부방식은 시간효율이 많이 떨어지므로 내일부터는 다른 효율적인 학습방법을 찾아서 시간을 조금 더 효율적으로 사용해야 캠프의 진도에 늦춰지지 않고 따라갈 수 있을 것 같다.