개발자식

최대공약수(Greatest Common Divisor) - 두 수 혹은 그 이상의 여러 수들의 공통인 약수 중 최대인 수 최소공배수(Least Common Multiple) - 두 수 혹은 그 이상의 여러 수들의 공통인 배수 중 최소인 수 코드 구현 a = 10 b = 12 #최대 공약수 구하기 for i in range(min(a,b), 0, -1): if a % i == 0 and b % i == 0: print(i) #2 break #최소 공배수 구하기 for i in range(max(a,b), (a*b) + 1): if i % a == 0 and i % b == 0: print(i) #60 break 유클리드 호제법 - 최대공약수를 쉽게 구할 수 있는 방법으로 최대공약수를 알면 최소공배수는 간단..

이진 탐색(Binary Search) - 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하여 원소 하나씩 확인해야 하는 순차 탐색보다 빠르다. - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. (데이터가 무작위일 때는 사용할 수 없음) 이진 탐색(Binary Search) 과정 - 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점을 사용해서 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아간다. 1. 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. (중간점이 실수일 때는 소시점 이하를 버린다) 2. 찾으려는 데이터와 중간점 데이터를 비교하여 중간점의 데이터가 더 크다면 끝점을 중간점의 위치 이전으로 옮긴다. 중간점의 데이터가 더 작다면 시작점을 중간점..

누적 합(Prefix Sum, Cumulative Sum) - 말 그대로 나열된 수의 누적된 합을 말한다. - 수열 An에 대해서, 구간 [1,1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다. An 1 2 3 4 5 Prefix Sum 1 3 6 10 15 누적 합의 사용 - 목적에 따라 다양한 문제에 활용이 가능하다. - 대표적으로 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다. 단순 반복을 이용한 구간 합 구하기 - 모든 입력마다 구간 합을 일일히 구해주는 경우 구간의 길이가 M이라고 하면 매 구간합을 구할 때마다 O(M)이라는 시간이 걸리게 된다. N개의 구간에 대해 구간의 길이가 M인 구간합을 구하는 경우 O(NM..