CS/알고리즘&문제풀이 (21) 썸네일형 리스트형 최대 공약수, 최소 공배수 https://mathbang.net/206#gsc.tab=0 최대공약수와 최소공배수의 관계 최대공약수와 최소공배수를 구하는 방법을 이해했나요? 대부분의 경우에 최대공약수와 최소공배수는 소인수분해를 이용하는 방법으로 구해요. 이 방법은 초등학교 때 많이 해봤던 방법이니까 mathbang.net 최대 공약수(Greatest Common Divisior, GCD): 두 수 이상의 여러 수의 공통된 약수 최소 공배수(Least Common Multiple, LCM): 둘 이상 수들의 공통된 배수 중 가장 작은 수 두 수 A, B가 존재할 때 LCM(A,B) = A * B / GCD(A,B)의 관계가 성립한다. GCD(A,B)는 A 및 B를 구성하고 있는 값이므로 A와 B 각각을 GCD(A,B) * n의 꼴로 .. [알고리즘] 분포기반 정렬 분포 기반 정렬 규칙에 따라 입력된 배열 원소를 여러개의 중간 구조로 분산한 후 결과 배열에 배치하는 정렬 방식. 배열 내 값들 사이에서 비교가 발생하지 않는다는 특징이 있다. 보통 비교 기반 정렬의 시간 복잡도는 O(log n) 이하로 떨어질 수 없다고 알려져 있는데 비해 분포 기반의 정렬을 이용하면 해당 수치 이하로 정렬 시간을 줄일 수 있어 속도가 중요한 경우 사용을 고려할 수 있다. 다만 탐색 기반의 알고리즘에 비해 공간 복잡도가 높을 수 있으며, 입력이 일정한 범위 내에서 고르게 분포해야 좋은 성능을 보인다. 계수 정렬 배열 내 특정 원소가 등장하는 횟수를 다른 공간에 저장해두고, 이를 누적 합 형식으로 변경하여 가진 후(Idx 배열), 배열을 탐색하면서 특정 원소가 등장할 때마다 Idx 배열을.. [알고리즘] 비교 기반 알고리즘 비교 기반(Comparison-based) 알고리즘 selection sort ( 선택 정렬 ) bubble sort ( 버블 정렬 ) insertion sort ( 삽입 정렬 ) shell sort ( 쉘 정렬 ) quick sort ( 퀵 정렬 ) merge sort ( 합병 정렬 ) heap sort ( 힙 정렬 ) Selection Sort 주어진 리스트 내에서 최솟값을 찾은 후, 가장 앞에 있는 값과 교체하면서 정렬하는 알고리즘으로, 각 정렬 단계가 마치 현재 단계에 들어가야 할 값을 리스트 내에서 찾아가는 과정처럼 보인다. 각 단계마다 배열의 좌측에서 배열의 정렬이 일어난다. 코드 def selection_sort(array: list[any]): for i in range(len(array).. [알고리즘] 정렬 00 : 정렬 개요 정렬(Sorting) 주어진 일련의 데이터( 보통 배열 )를 순서대로 재배치하는 것. 물건을 가격별로 세워두기 위해 조사하거나, 유통기한이 임박한 순서대로 제품을 출고해야 하는 등 정보의 순서가 의미 있는 분야라면 어디든지 사용될 수 있다. 알고리즘의 효율성은 데이터 및 데이터가 가진 특성에도 영항을 받지만, 해당 알고리즘을 구동하는 환경( 메모리, CPU 파워, 지원되는 소프트웨어 등 )과 같은 요소에도 영향을 받을 수 있다. 알고리즘 성능 측정 수단 시간 효율(Time Complexity) Big-O, Big-Ω, Big-Θ 의 표현법을 이용. best-case, worst-case, average-case 을 나타낼 수 있음. 공간 효율(Space Complexity) 제자리성(In-place al.. [알고리즘] 알고리즘 이해 알고리즘 특정 문제를 풀거나 계산을 수행하는 데 사용되는 잘 정의된 명령의 유한 절차로, 어떠한 문제에 대한 해결 절차를 체계적으로 나타낸 후, 해당 절차에 따라 어떤 입력을 어떤 출력으로 변환하는 일련의 계산과정을 의미한다. 알고리즘의 대상이 되는 문제는 입력 및 출력의 형태로 요구조건을 나타낼 수 있어야 한다. ex) 도서관의 책을 ISBN에 따라 정렬하세요. 문제 : ISBN에 따른 도서관 책 정렬 입력 : 도서관의 책 & ISBN 출력 : 정렬된 책 리스트 알고리즘이 가져야 할 특성 명확성 : 최대한 이해하기 쉽고 간명하게 서술해야 한다. 명확하게 나타낼 수만 있다면 알고리즘을 나타내는 수단은 상관없음. 효율성 : 동일 문제 해결에 있어 최대한 시·공간적으로 효율적이어야 한다. ex ) for 문.. 이전 1 2 3 다음
