하...너무 어렵다.
오늘 강의 진도를 다 나갈 수 있을까 걱정이다.
20분짜리 강의 하나 이해하고 넘어가는 데 1시간이 넘게 걸리는 듯 하다ㅠㅠ
어려워요 알고리즘
알고싶어요 알고리즘
이해할 때까지 해버리고 싶지만 잠은 자야되니까..ㅎ
일단 오늘은 하는 데까지 해보자~!
오늘 다 못하면 내일 다 하고 내일 다 못하면 주말까지 다 해버리고 그러면 되지 뭐
다 이해하고 끝내는 게 중요한 것 아니겠는가ㅎㅎㅎㅎ

들어가기에 앞서

오늘 강창민 튜터님이 그러셨는데
코딩테스트에서 다른 언어도 선택이 가능하지만 파이썬을 사용하는 이유는
숏코딩이라 그렇다.
코테는 제한시간이 있기 때문에 짧은 코드를 이용해서 쓰는게 오타를 줄이기에도 좋다

• 프로그램의 본질
  : 주어진 문제를 얼마나 쉽고 빠르고 간결하게 해결하는가

• 공부를 할 땐
  자기객관화가 중요하다~!

본격 알고리즘과 친해지기

알고리즘이 나한테 낯 가리는 중 너무 어려워 친해지기

최대값 찾기

• 1) 대조군을 고정하고 다른 숫자를 모두 비교하며 대조군이 다른 숫자보다 제일 클 때 결과를 반환한다.
• 2) 변수 하나를 지정한 후 다른 숫자와 비교할 때 다른 숫자보다 크면 변수 값을 교체한다.

  for문을 두 개 만드는 것보단 한 개로 만드는 게 알아보기도 쉬울 것 같다

알파벳 최빈값 찾기

• str.isalpha(): 파이썬 내장함수로 문자열이 알파벳인지 확인 가능
• ord(): 문자열을 아스키코드로 변환해주는 함수
• chr(): 아스키코드를 문자열로 바꿔줌
  
  

빈도수 리스트로 만들어 저장하기

• [특정값] * 숫자: 숫자만큼의 길이에 특정값을 요소로 갖는 리스트를 만들어준다.
  기본값을 0으로 설정한 이유.. 3으로 바꿔보니 함수에 포함되지 않은 다른 요소들이 다 3으로 바뀌더라.. 그래서 0으로 한 게 아닐까..

• if not을 사용한 이유: 가독성이 크지 않을까..
  if를 사용해도 코드는 잘 작동되지만 필터링의 본질적인 목적에 부합하지 않기 때문에 if not 사용.
  *필터링: 특정 조건에 부합하지 않는 것을 걸러내는 과정.
  슬랙에 튜터님의 답변을 공유해주신 분이 계셨다!!😆

• 알파벳의 아스키코드에서 a의 아스키코드를 빼면 인덱스 값이 나오게 됨
  ex) d의 아스키코드(==100) - a의 아스키코드(==97) = 3
       알파벳 배열에서 d의 인덱스 = 3 // [a, b, c, d, ...]

최빈값 찾기

• chr(): 아스키코드를 문자열로 바꿔줌
• 1) 알파벳 배열을 모두 지정해서 for문을 활용해 해당 알파벳이 있으면 occurrence값을 올려주고 그렇게 max값을 찾는다.
• 2) input값에 알파벳이 아닌 띄어쓰기도 포함되어 있기 때문에 제외조건을 만들어준다.
  빈도수 리스트 만든 for문을 사용한다.
  max값 변수를 설정하고 다시 for문을 이용하여alphabet_occurrence_array의 길이를 범위로 가지는 리스트에 속한 요소를 변수index로 설정하고 돌린다.
  그리고 alphabet_occurrence는 alphabet_occurrence_array[index]니까 결국 빈도수리스트의 요소들이 되는거지. 그렇게 max값을 찾고 알파벳 최빈값의 인덱스를 다시 문자열로 바꿔주면 결과값이 나온다.

코드는 2번이 더 복잡하지만 (지금 내가 이해하는 면에서도) 리스트 요소를 다 지정할 수 없을만큼 많을 때는 확실히 2번 방법이 효과적이다.

시간복잡도

: 입력값 & 문제를 해결하는 데 걸리는 시간 의 상관관계

• 시간이 적게 걸리는 알고리즘이 좋다

수식으로 판단하기

• 함수의 시간이 얼마나 걸리는지 분석한다
  • 각 줄이 실행되는 것을 1번의 연산으로 하고
    함수에서 크기가 변경될 수 있는 값(입력값)의 길이를 N이라고 표현한다.

1. <최댓값 찾기> 코드 비교

• 상수는 무시하고 지수만 비교해 입력값에 비례해서 증가 정도를 파악해서 판단
  • 1)$N^2$만큼의 연산량 / 2) $N$만큼의 연산량

2. <최빈값 찾기> 코드 비교

• 상수를 무시하면 둘 다 N만큼의 시간이 필요하다
  but 계수도 중요함-!!! 계수가 엄청 크면 성능 차이가 있다고 함
  $N^2$에 비하면 상수N은 별로 차이가 없음

공간복잡도

: 입력값 & 문제를 해결하는 데 걸리는 공간 의 상관관계

• 역시 공간이 적게 걸리는 알고리즘이 좋다

수식으로 판단하기

• 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산

• <최댓값 찾기> 코드비교

  • 29 / 30 모두 상수라 알고리즘 성능에 큰 상관이 없음

공간복잡도 보다 시간복잡도를 더 신경 써야 한다.

점근표기법

: 알고리즘의 성능을 수학적으로 표기하는 방법 == 알고리즘 효율성 평가 방법

• 복잡도 분석 시 'N정도 걸리겠구나' 분석한 게 점근표기법의 일종
• 종류: 빅오(Big-O) 표기법,빅 오메가(Big-Ω)표기법

예제) 배열에서 특정 요소 찾기

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


def is_number_exist(number, array):
    for element in array:  #array길이 연산
        if number == element: #비교연산 1번
            return True

    return False


result = is_number_exist(3, input)
print(result)

• $N*1$만큼의 시간복잡도를 가짐
• but 입력값의 분포에 따라 성능이 변할 수 있음
  • 현재 input의 경우 1번의 연산을 통해 결과값을 찾을 수 있지만 3이 배열 끝에 위치하게 되면 N번의 연산을 해야 결과값을 찾을 수 있음
  • 이를 점근표기법으로 표기하면
    빅오(Big-O) 표기법(최악의 성능을 표기) -> $O(N)$
    빅 오메가(Big-Ω)표기법(최고의 성능을 표기) -> $Ω(1)$
• 우리는 항상 최악의 경우를 생각해야하기에
  모든 알고리즘은 빅오로 표기
  
  

---

---

---

마무리

아아아아아아아아아 멘붕이다
알고리즘 너무 어렵다
코드를 어떻게 짤까 생각하는데
생각도 안나고
생각은 나도 이걸 코드로 옮기질 못하겠다
코드 하나 이해하는 데 시간이 많이 걸린다..
얼마나 코드를 보고 써보고 생각해야 익숙해지고 빨라질까
그래도 코드 분석하면서 하면 재밌긴 한데...ㅎㅎ
생각이 잘 안나니까 답답하다ㅎ
앗
오늘 동기분이 디버깅을 알려주셨다
진짜 너무 감탄했다.
여태 혼자 분석하고 생각하고 했는데 이걸 대신 해주는 느낌!!
디버깅 최고다
내일 또 열심히 알고리즘을 이해하기 위해 달려보자-!!

[스파르타코딩클럽] <쉽게 배우는 알고리즘 KDT 실무형 스프링 백엔드 엔지니어 양성과정 1회차>