✍️오늘 공부한 내용

• 힙소트,힙 만들기
• heapq
• 백준 문제
  • 1655 뱁 아직 100% 이해가 가지는 않음
  • 1629 곱셈
    

📋새로 배우게 된 내용

• heapq에서 heapify로 있던 배열을 힙으로 만들어주면 시간복잡도가 O(n)이 된다.
  • 빈 리스트에 원소 개수만큼 append해주는 거라서
• 힙소트는 자식과 부모간의 대소비교만 있을뿐, 형제와의 대소비교는 되어있지 않다.
• 나머지 분배법칙은 덧셈, 뺼셈, 곱셈에는 적용되지만 나눗셈은 페르마의 소정리를 이용해야한다.

🤯어려웠던 점

1. 1629 곱셈 : 규칙은 발견했는데 식으로 짜는데 어려움이 있었다.

😸어려움을 해결한 방법

1. 찾아보니까 지수법칙과 나머지 분배법칙을 통해 분할정복할 조건들을 쉽게 만들 수 있다는 걸 알게 되었다.

• 지수 법칙 = A^(m+n) = A^m*A^n
• 나머지 분배법칙= (AB)%C= (A%C)(B%C)%C

😝느낀점

• 직접구현했을때는 리스트로 만들면 시간복잡도를 알 수 있는데, 내장된 기능들은 내가 기대했던 거와는 다른 조건들이 있을 수 있었다.
• 라이브러리를 사용할 떄는 공식문서를 확인하고 제대로 알고 사용하도록 하자!

👊다짐

• 힙정렬 다시 복습해서 참고없이도 힙 만들 수 있도록 하자!

🚀오늘의 한줄평

• 힙소트와 한 노드 가까워지기 day1🗓️