22.09.16(금) Today I Learned

9/16 오늘의 시간표

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주차의 내용은 한번 들어보기로 했다. 역시나 알고리즘에 익숙하지 않아 단어부터 생소한 것이 많았고 문제 하나를 푸는데 영상을 3~4번씩은 돌려봐야 할 정도로 문제풀이가 쉽지 않았다.

알고리즘이란?

• 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.
• 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임이다.

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

1. 좋은 개발자가 되기 위해서

• 개발자는 프로그램을 만드는 직업이기 때문에 좋은 개발자가 되려면 좋은 프로그램을 구현할 줄 알아야 한다.
  • 좋은 프로그램이란? 적은 공간을 이용해서 빠른 속도로 수행되는 프로그램이다.
  • 그런 프로그램을 만들기 위해서는 경우에 따라 특정 자료구조나 접근방법을 사용해야 한다. 즉, 프로그램을 잘하기 위해서는 여러 자료구조와 방법들을 배우고 익혀야 좋은 프로그램을 만들 수 있다.

2. 좋은 회사에 취직하기 위해서

• 수많은 회사들이 코딩테스트를 통해 개발자를 구인하고 있다. 카카오, 삼성, 구글 등 국내외 유망 IT 기업들 외에도 많은 스타트업까지 코딩테스트를 개발자의 필수 관문으로 만들고 있다. 하지만 엄청나게 어려운 수준의 문제를 출제하진 않는다. 기초적인 지식과 해결책으로 적절한 사고를 할 수 있는지에 대해 검증하기 위해 필수 관문을 만드는 것이다.

최댓값 찾기

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

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

• A1.

  • 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인한다. 만약 다른 모든 값보다 크다면 반복문을 중단한다.

  • python 의 for ~ else 문은 for문에서 break가 발생하지 않았을 경우의 동작을 else문에 적어주는 것이다.

    def find_max_num(array):
        for num in array:
            for compare_num in array:
                if num < compare_num:
                    break
            else:
                return num
    
    print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
    print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
    print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• A2.
  배열 내에서 가장 큰 수를 찾아야 한다. 그러면, 가장 큰 수를 저장할 변수를 만들고, 배열을 돌아가면서 그 변수와 비교한다. 만약 값이 더 크다면, 그 변수에 대입한다.

    def find_max_num(array):
        max_num = array[0]
        for num in array:
            if num > max_num:
                max_num = num
        return max_num
    
    print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
    print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
    print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))
    ```

최빈값 찾기

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

"hello my name is sparta"

• A1.
  각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인한다. 만약 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장한다. 이 과정을 반복하다보면 가장 많이 나왔던 알파벳을 알 수 있다.

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

• A2. 각 알파벳의 빈도수를 alphabet_occurrence_list 라는 변수에 저장한다. 그리고 각 문자열을 돌면서 해당 문자가 알파벳인지 확인하고, 알파벳을 인덱스 화 시켜 각 알파벳의 빈도수를 업데이트 한다. 이후, 알파벳의 빈도수가 가장 높은 인덱스를 찾는다.

        
        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

여기까지 했으면, 가장 높은 빈도수의 인덱스를 알아낼 수 있다. 이제 chr() 함수를 사용하면 아스키 코드 번호를 실제 문자로 변환할 수 있다.

        chr(97) == 'a'
        chr(0 + ord('a')) == 'a'
        chr(0 + 97) == 'a'
        chr(1 + 97) == 'b'

최종 답안

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

시간 복잡도 판단하기

• 시간 복잡도란?

  • 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
  • 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다.

• Q. 최댓값 찾기 알고리즘의 시간 복잡도 판단해보기

  • A1.

        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("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
        print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
        print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• 이 해결 방법은 각 숫자마다 모든 다른 숫자와 비교해서 최대값인지 확인한다. 만약 다른 모든 값보다 크다면 반복문을 중단한다. 이제 이 함수가 시간이 얼마나 걸리는지 분석하려면 각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산한다.
  

            for num in array:              # array 의 길이만큼 아래 연산이 실행
                for compare_num in array:  # array 의 길이만큼 아래 연산이 실행
                    if num < compare_num:  # 비교 연산 1번 실행
                        break
                else:
                    return num

• 위에서 연산된 것들을 더해보면,
  • 1. array의 길이 X array의 길이 X 비교 연산 1번만큼의 시간이 필요하다. 여기서 array(입력값)의 길이는 보통 N이라고 표현한다. 그러면 위의 시간을 다음과 같이 표현할 수 있다.
       

그러면 이제 이 함수는 $N^2$ 만큼의 시간이 걸렸다고 표현 할 수 있다.

• A2.
  

        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("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
        print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
        print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

• 이 해결 방법은 리스트를 하나씩 돌면서 num 과 max_num 값을 비교하는 함수이다.
  

            max_num = array[0] # 연산 1번 실행

        		for num in array:      # array 의 길이만큼 아래 연산이 실행
        		    if num > max_num:  # 비교 연산 1번 실행
        		        max_num = num  # 대입 연산 1번 실행

위에서 연산된 것들을 더해보면,
1. max_num 대입 연산 1번
2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)
만큼의 시간이 필요하다. 첫 번째 방법에서 했던 것처럼 array 의 길이를 N이라고 하면 다음과 같이 표현할 수 있다.

그러면 우리는 이제 이 함수는 $2N+1$ 만큼의 시간이 걸렸음을 알 수 있다.

공간 복잡도 판단하기

• 공간 복잡도란?

  • 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
  • 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다.

• Q. 최빈값 찾기 알고리즘의 공간 복잡도 판단해보기

  • A1.
    

        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"]
            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_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_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"]
        # -> 26 개의 공간을 사용합니다
            max_occurrence = 0 # 1개의 공간을 사용합니다
            max_alphabet = alphabet_array[0]   # 1개의 공간을 사용합니다.
        
            for alphabet in alphabet_array:
                occurrence = 0  # 1개의 공간을 사용합니다

위에서 사용된 공간들을 더해보면,
1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3

만큼의 공간이 필요하다.

• A2.
  

        def find_max_occurred_alphabet(string):
            alphabet_occurrence_list = [0] * 26
        
            for char in string:
                if not char.isalpha():
                    continue
                arr_index = ord(char) - ord('a')
                alphabet_occurrence_list[arr_index] += 1
        
            max_occurrence = 0
            max_alphabet_index = 0
            for index in range(len(alphabet_occurrence_list)):
                alphabet_occurrence = alphabet_occurrence_list[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"))

이 해결 방법은 각 알파벳의 빈도수를 저장한 다음에, 빈도 수 중 가장 많은 알파벳의 인덱스 값을 반환한다.

        		alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다
        
            for char in string:
                if not char.isalpha():
                    continue
                arr_index = ord(char) - ord('a')  # 1개의 공간을 사용합니다
                alphabet_occurrence_list[arr_index] += 1
        
            max_occurrence = 0                   # 1개의 공간을 사용합니다
            max_alphabet_index = 0               # 1개의 공간을 사용합니다
            for index in range(26):
                alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
                if alphabet_occurrence > max_occurrence:
                    max_occurrence = alphabet_occurrence
                    max_alphabet_index = index

위에서 사용된 공간들을 더해보면,
1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4

만큼의 공간이 필요합니다.

그러면 우리는 이제 이 함수는 $30$ 만큼의 공간이 사용되었음을 알 수 있다.

파이썬 거북이반

오늘부터 장고를 본격적으로 배울 때 까지 파이썬 문법에 익숙하지 않은 사람들을 위한 파이썬 거북이반이 개설되었다. 나는 당연히 신청했고 나 말고도 우리 A11팀 전원이 거북이반 추가 강의를 듣기로 했다. 생각보다 거북이반에 신청한 사람이 많았고 권기현튜터님의 주도하에 거북이반 첫 수업이 시작되었다.

파이썬의 가장 기초적인 부분들부터 차근차근 설명해 주셨고 오늘의 주된 설명은 for문의 이해, list와 dictionary였다.

• for문
  • list, tuple, set 자료형의 요소들로 반복문을 사용할 수 있다.
  • enumerate()를 사용해 반복되는 요소가 몇번째인지 확인할 수 있다.
  • dictionary 자료형의 key 혹은 value로 반복문을 사용할 수 있다.
  • range() 함수를 활용하면 원하는 만큼 반복문을 사용할 수 있다.
  • continue를 활용해 특정 상황에서 아무런 동작도 하지 않고 넘어갈 수 있다.
  • break를 활용해 특정 상황에서 반복문을 중지시킬수 있다.
• list
  • list 자료형 선언 시 list 안에 들어있는 각 요소는 0부터 시작해 순서대로 index 번호를 가지며, indexing과 slicing 기능을 활용해 활용해 원하는 값을 가져올 수 있다.
  • list 자료형에서는 값을 원하는대로 추가(append), 수정, 삭제(remove)할 수 있다.
  • list 자료형의 요소에는 숫자나 문자 이외에도 다양한 자료형을 사용할 수 있다.
  • len() 함수를 사용해 list의 길이를 구할수 있다.
• dictionary
  • dictionary 자료형은 key: value로 구성되며, key를 사용해 value를 가져올 수 있다.
  • 만약 존재하지 않는 key로 value를 가져오려 시도할 때에는 에러가 발생한다.(.get을 사용한다면 key가 없을 때 사용될 값을 지정하여 에러가 발생하지 않도록 할 수 있다.)
  • dictionary 자료형에서는 자유롭게 값을 추가, 수정, 삭제(del)할 수 있다.

이미 한번 정리한 내용을 개념이해를 위해 차근차근 다시 설명해 주신 것이기 때문에 추가적인 학습 내용이 있다기 보다는 기존내용을 확실히 상기시키는 쪽을 중점으로 강의를 진행해 주셨다.

오늘 할 일을 끝내고

확실히 매주 금요일은 조금 분위기가 어수선해지는 감이 없지않아 있는 것 같다. 수업의 집중도도 떨어져서 많은 학습을 하지는 못했지만 알고리즘이라는 것이 무엇을 하는지 정도는 알아볼 수 있었고 거북이반 강의를 통해 파이썬 문법을 다시 한 번 짚고 갈 수 있는 유익한 시간이었고 다음 주 부터는 다시 집중해서 강의를 들을 수 있도록 노력해야겠다.