This is Mi

참고 「Rosen의 이산수학 8th Edition」 (Kenneth H. Rosen 지음) 내용 구성 소인수분해 방식의 문제점 유클리드 알고리즘이란? 파이썬 코드 관련 문제 최대공약수: gcd (greatest common divisor) 최소공배수: lcm (least common multiple) 1. 소인수분해 방식의 문제점 소인수분해 방식은 일반적으로 많이 사용되지만, 비효율적인 방법이다. 두 정수가 커질수록 소인수분해를 구하는 데 시간이 오래 걸리기 때문이다. 2. 유클리드 알고리즘이란? a = bq + r (a ＞ b)일 때, gcd(a, b) == gcd(b, r)라는 성질을 이용한다. 소인수분해 방식보다 더욱 효율적으로 최대공약수를 찾을 수 있는 알고리즘이다. 위 그림은 유클리드 알고리즘으..

참고 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음 「Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편」 시바타 보요 지음 https://yabmoons.tistory.com/250 콘텐츠 개념 파이썬 구현 코드 시간 복잡도 장단점 퀵 정렬과 병합 정렬 선택 기준 대부분의 프로그래밍 언어에서 정렬 라이브러리는 속도가 빠른 퀵이나 병합 정렬을 기반으로 한다. 퀵 정렬 (Quick Sort) 개념 피벗pivot이라는 기준에 의해 리스트 내 큰 숫자와 작은 숫자를 교환한다. 피벗을 설정하는 기준은 다양하지만, 리스트의 첫 번째 원소를 피벗으로 설정하는 "호어 분할 방식"이 가장 대표적이다. 초록색이 피벗이고, 노란색 화살표는 5 다음 숫자에서부터 피벗보다 큰 값을 찾고, 파란색 화살표..

참고 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음 모두를 위한 컴퓨터 과학 (CS50 2019) https://www.boostcourse.org/cs112/joinLectures/41488?isDesc=false 구성 요소 개념 파이썬 구현 코드 시간 복잡도 장단점 버블 정렬(Bubble Sort) 개념 데이터 내 인접한 두 요소를 비교하여 자리를 교환하거나 그대로 유지하는 정렬 방법이다. 위 그림은 버블의 각 단계를 나타낸 것으로, 파란색이 인접한 두 요소이다. 오름차순 정렬 기준, 왼쪽에 있는 값이 오른쪽에 있는 값보다 크다면 둘이 자리를 바꾼다. 이미 정렬되어 있는 상태(왼쪽 요소 < 오른쪽 요소)라면 그대로 다음 인덱스로 넘어간다. 데이터의 마지막 요소까지 비교가 끝나면, 가장 ..