TIL 1 (03/16)

		@	오늘로 자료구조, 알고리즘 공부를 시작한지 12일차 	@
        		@	항해를 시작한지는 16일차 	@
@	매번 노션에만 정리를 하다가 WIL 기록하고 있는 곳에 기록하면 좋을 것 같아서 velog로 왔다.	   @
		@	     오늘부터는 이곳에 적어보도록 하겠다		@ 

오늘 풀어본 문제

자료구조, 알고리즘 공부는 백준 알고리즘에 올라온 문제들을 풀어보며 새로운 개념들을 공부하고 있다.

• 동전
• ATM
• 약수
• 최대공약수와 최소공배수
• 이향 계수 1
• 다리놓기

새롭게 배운 내용

• 그리디 알고리즘 (탐욕 알고리즘)
  - '가장 큰 순서대로' or '가장 작은 순서대로' 같이 기준 제시함
  - 현재 상황에서 당장! 좋은 것만을 고르는 방법
  - 그래서 항상 최적을 해를 구하는 것은 아님 → 정당성 분석 중요함
  • 동적 계획법과 차이점: 그리디 알고리즘은 각 단계마다 지금 당장 최고의 방법을 선택하여 전체 문제의 답을 구한다

참고1. https://velog.io/@jiffydev/이론파이썬-알고리즘-그리디-알고리즘
참고 2. https://m.blog.naver.com/PostView.nhn?blogId=qpghnv&logNo=221597913108&proxyReferer=https:%2F%2Fwww.google.com%2F
참고3. https://gomguard.tistory.com/119

• 리스트 정렬
  - reversed 함수
  for i in reversed(range(N)) 큰 숫자들이 앞으로 오게 할 수 있다
  - sort 함수
  리스트로 정수들이 섞여서 입력받아질 때 최소값을 알기 위해 sort로 정렬!
  - sort의 key 옵션, key 옵션에 지정된 함수의 결과에 따라 정렬, 원소의 길이에 따라 정렬될 수 있음

      ```python
      ```python
      >>> m = '나는 파이썬을 잘하고 싶다'
      >>> m = m.split()
      >>> m
      ['나는', '파이썬을', '잘하고', '싶다']
      >>> m.sort(key=len)
      >>> m
      ['나는', '싶다', '잘하고', '파이썬을']
      ```
      ```

  자료구조와 순차 자료형 정리가 잘되어있는 곳 https://github.com/psygrammer/psytracker/blob/master/psytracker_2.md

• 유클리드 호제법
  "정수 X 와 Y(X ≥ Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X 로 한다"

• 유클리드 호제법을 이용한 최대공약수 최소공배수

    ```python
    x, y = map(int, input().split())
  
    def gcd(x, y):
        if y == 0:
            return x
        else:
            return gcd(y, x % y)
            
    def lcm(x, y):
        return x*y // gcd(x,y)
        
    print(gcd(x, y))
    print(lcm(x, y))
    ```

• 이항 계수
  - 이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다.
  - ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만이 있기 때문이다.
  - n개 중에서 k개를 간택하는 것은 선택받지 못할 나머지 (n-k)개를 선택하는 것과 같다.

  $\binom{n}{k} = n C k = \frac{n!}{(n-k)!k!} (단, 0 \le k \le n) \quad \cdots 1$

  ```python
  from math import factorial
  factorial(n) // (factorial(n - k) * factorial(k))
  ```

  이항 계수 출처
  https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

• sys.stdin.readline()
  한 라인 입력 받을 떄

• sys.stdin()
  여러 줄 입력 받을 때

고민한 내용

부족한 수학 개념에 관하여...
오늘 공부한 유클리드 호제법 같은 경우 최대공약수와 최소공배수를 구하는데 '더 쉬운' 방법을 알려줘서 아주 좋았다. 사실 유클리드 호제법은 몰라도 최대공약수와 최소공배수를 구할 수 있다. 하지만 문제 이항 계수 1은 어떠한 설명없이 이항 계수를 구하는 프로그램을 작성하는 것이 문제였다. ㅜ ㅜ 고등수학을 거의 몰라서 이렇게 한번씩 철저히 수학 공식에 의존한 문제가 나오면 잠시 아찔해지는 것은 사실이다. 만약 미국에 가지 않았다면? 돌아와서 검정고시를 보지 않고 한국에서 고등학교를 다니며 수학을 공부했으면 달랐을까? 라는 생각까지 했다.
하지만 분명한 것은 이번 알고리즘 주차를 지내면서 수학공식, 혹은 수학적 사고는 공부하면 알 수 있다는 자신감이 붙었다. 이항 계수 말도 어렵고 공식도 어려운 것 같았는데 알고보니 선택하거나 선택하지 않거나에 관한 공식이었다.
단지 지금껏 필요하지 않아서 알지 못했을 뿐이고, 이제 필요함을 느끼니 공부하면 되는 것이다!

오늘 하루 회고

어제까지 문제가 잘 풀리지 않아서 심적으로 힘들었었는데, 오늘은 그래도 수학 개념을 알면 풀어갈 수 있는 문제들 + 전날에 비해 비교적 난이도가 낮은 문제들이 모여있어서 쑥쑥 풀 수 있었다.

지난주 WIL 정리하면서 자료구조, 알고리즘, 파이썬 개념이 혼잡해서 어려웠어서 문제를 볼 때
1. 문제의 데이터들이 어떤 자료구조의 형식인지
2. 어떠한 알고리즘으로 풀어가야하는지
3. 필요한 파이썬 문법/함수는 무엇일지 계속 생각하면서 보자! 했었는데
확실히 문제를 다방면에서 보니 힌트를 얻거나, 해결방향을 정확하게 설정한 문제들이 많아졌고, 적어도 문제를 잘못이해하는 일들은 없어졌다.

진짜 문제는 아직 잘 못풀지만 알고리즘 정말 재미있다... 모르겠다...잘 못 풀면서 왜 재미있는지...
더 잘 풀고 싶다 !

더 공부해야할 것

• 링크드 리스트
• 클래스
• 한줄짜리 반복문