정의 - 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용하는 알고리즘 - 투 포인터와 비슷하지만 고정 사이즈를 사용하는 겅우를 윈도우로 정의한다 - 정렬 여부에 상관없이 활용 - 시간복잡도는 O(N)으로 해결 가능 예시 코드 list1 = [5,6,8,9,1,3] n = len(list1) result = list[0] + list[1] + list[2] for i in range(1,n-2): result = max(result, result - list1[i-1] + list1[i+2]) print(result)

정의 이름 그대로, 해를 찾는 과정에서 막히면 처음으로 돌아가는 방법이다. (= 가지치기) 재귀를 이용한 완전 검색을 하고 가지치기를 추가하는 기법 결론적으로, 불필요한 계산낭비를 방지하는 방식이라고 생각하면 된다. 주로 최적화문제와 결정문제를 해결하는데에 사용된다. ex_ 미로찾기, n-Queen 문제, Map coloring, 부분집합의 합 문제 코드 예시 N, M = map(int, input().split()) ans = [] def back(): if len(ans) == M: # 배열의 길이를 확인 print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해 return for i in range(1, N+1): # 1 ~ N 까지 if i not in an..

재귀 함수 - 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. - 재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 - 수행되지 않는다는 사실과 종료조건이 꼭 포함되어야한다는 부분을 인지해야 한다. 순열 def permutation(arr, r): arr = sorted(arr) used = [0 for _ in range(len(arr))] def generate(chosen, used): if len(chosen) == r: print(chosen) return for i in range(len(arr)): if not used[i]: chosen.append(arr[i]) used[i] = 1 gener..

Quick Sort의 정의 1. 분할 정복 알고리즘의 하나로, 평균적으로 빠른 시간 복잡도를 지닌다. 2. Pivot의 개념을 활용한다. Quick Sort 과정 1. 리스트 안에 있는 한 요소를 선택한다.(임의로) 2. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 옮긴다. 3. 피벗을 제외한 왼쪽, 오른쪽 리스트를 위와 같은 방법(1~2)으로 재정렬한다. 4. 분류된 리스트가 더 이상 분할되지 않을 때까지 반복한다. - 리스트의 크기가 0 or 1일 경우 Quick Sort 코드 1(기본) def quicksort2(arr, start, end): if start >= end: return pivot = start left = start + 1 right = end whil..