알고리즘
-
[백트래킹] Backtracking알고리즘 2023. 2. 14. 15:00
백트래킹 기본개념 탐색 알고리즘의 일종, 모든 경우의 수를 고려하는 알고리즘 트리 탐색 알고리즘 주로 DFS 사용 예시1) 조합(Combination) 길이가 n인 주어진 수열에서 k개를 뽑는 경우의 수 재귀 함수, 백트래킹을 통해 k개만 정확히 선택하며 이미 선택된 경우는 제거 내장 함수 itertools의 combination 함수 사용 # coding = utf-8 from itertools import combinations for choice in combinations([1,2,3,4],2) : print(choice) # 결과 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 재귀 함수를 사용하여 조합을 구현 # coding = utf-8 choice = list()..
-
[분할정복] Divide and Conquer알고리즘 2023. 2. 13. 19:28
Divide and Conquer Top-Down 방식의 알고리즘 Divide : 가장 상위의 문제를 2개의 하위 단계의 문제로 나눈다. Conquer : 최적의 부분 구조까지 문제를 나눈 후 해결한다. Combine : 하위 문제에 대한 결과를 조합한다. 예시1) MergeSort(병합정렬) 기존 Selection sort, Bubble sort, Insertion sort의 시간복잡도 O(N^2) Merge sort의 시간복잡도 O(NlogN) 병합 정렬의 알고리즘 및 분할 정복 개념 적용 데이터 크기가 2 이상일 때, 데이터를 두 집합으로 분할 ( Divide ) 데이터의 크기가 0 또는 1이면 정렬된 데이터 데이터를 모두 분할한 후, 데이터 집합들을 병합 ( Combine ) 병합 과정에서 데이터..
-
[탐색] 이분/이진 탐색알고리즘 2022. 10. 25. 19:06
이분/이진 탐색 Heap에서 binary tree구조의 이점을 활용하여 대소 비교 연산을 줄여 O(logN)의 시간복잡도로 리스트의 반정렬 상태를 유지하면서 값을 삽입하거나 삭제할 수 있었다. 이분/이진 탐색도 위와 비슷하게 탐색 과정에서 절반을 신경쓰지 않으면서 대소 비교 연산을 진행할 수 있어 시간복잡도를 O(logN)으로 줄일 수 있다. 이분/이진 탐색 아이디어 위의 아이디어를 조금 더 구체화해서 보면 다음과 같다. 우선 주어진 리스트를 정렬한다. ( 정렬하는 이유는 절반을 신경쓰지 않고 대소 비교를 진행하기 위해서이다. ) 정렬된 리스트의 중간 Index의 값에 접근하여 탐색하고 싶은 값과 비교한다. 이때, 비교하여 작거나 큰 경우 중간 Index에서 우측 또는 좌측 부분의 값들은 비교할 필요가 ..