Divide and Conquer(분할 정복)
Divide and Conquer(분할 정복) 분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘 설계 패러다임입니다. 이 패러다임은 문제를 더 작은 하위 문제로 분할한 다음, 각 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해를 얻는 방식으로 동작합니다. 이러한 분할 정복 접근 방식은 문제를 더 작고 관리하기 쉬운 부분으로 나누어서 효과적으로 해결하는 데 사용됩니다. 분할 정복 알고리즘은 보통 다음의 세 단계로 진행됩니다. 분할(Divide): 주어진 문제를 더 작은 하위 문제로 분할합니다. 이때, 하위 문제는 원래 문제와 구조적으로 유사해야 합니다. 정복(Conquer): 작은 하위 문제들을 재귀적으로 해결합니다. 이 단계에서 하..
- Algorithms and Data Structures/Algorithms
- · 2023. 8. 29.
Brute Force
Brute Force(무차별 대입) brute force 방법은 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방식입니다. 이 방식은 일반적으로 효율성이 떨어질 수 있지만, 모든 경우를 체크하기 때문에 정확한 답을 찾을 수 있습니다. 접근 방법: 가능한 모든 조합을 생성하거나 탐색합니다. 효율성: 일반적으로 느리며, 복잡도가 높을 수 있습니다. 대부분의 경우, 시간 복잡도는 O(n!) 또는 O(2^n)입니다. 적용 분야: 정확한 답이 필요하고, 입력 크기가 작은 경우에 사용할 수 있습니다. 예 두 숫자 중 두 개를 선택하여 합이 목푯값과 같은 경우를 찾는 예시 코드입니다. Python def findSumPairBruteForce(nums, target): n = len(nums) for i i..
- Algorithms and Data Structures/Algorithms
- · 2023. 8. 15.
재귀 함수(Recursive Function)
재귀 함수(Recursive Function)이란? 재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. 이를 통해 반복적인 작업을 수행할 수 있습니다. 재귀 함수의 구조 def 재귀함수(): if 종료_조건: return 결과 ... 재귀함수() ... 예 팩토리얼은 재귀 함수의 대표적인 예시입니다. def factorial(n): if n == 1: return 1 return n * factorial(n - 1) factorial(5)를 호출한다고 가정하면, 아래와 같은 과정을 거치게 됩니다. 첫 번째 호출: factorial(5)가 호출됩니다. n = 5이므로, 5 * factorial(4)를 반환해야 합니다. factorial(4)를 호출하기 위해 다음 단계로 넘어갑니다. 두 ..
- Algorithms and Data Structures/Algorithms
- · 2023. 8. 13.
삽입 정렬 알고리즘
삽입 정렬 알고리즘(insertion sort algorithm) 삽입 정렬(insertion sort)은 리스트를 반복하면서 각 항목을 이미 정렬된 부분 리스트의 올바른 위치에 "삽입"함으로써 동작합니다. 리스트의 두 번째 항목에서 시작하여 왼쪽의 항목과 비교합니다. 현재 항목이 왼쪽 항목보다 작으면 왼쪽 항목을 오른쪽으로 이동시킵니다. 이를 현재 항목이 왼쪽 항목보다 크거나 왼쪽에 더 이상 항목이 없을 때까지 반복합니다. 그런 다음 현재 항목을 마지막으로 비어 있는 위치에 삽입합니다. 이 과정을 리스트의 모든 항목에 대해 반복합니다. 이를 파이썬 코드로 구현하면 다음과 같습니다: def insertion_sort(arr: list[int]) -> list[int]: # 배열 전체를 반복하면서 for ..
- Algorithms and Data Structures/Algorithms
- · 2023. 7. 29.
선택 정렬 알고리즘
선택 정렬 알고리즘(selection sort) 리스트 중에서 최소값을 찾습니다. 그 값을 리스트의 맨 앞에 위치한 값과 바꿉니다. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복합니다. Python 코드 def selection_sort(arr: list[int]) -> list[int]: length: int = len(arr) # 배열 전체를 반복하면서 for index_1 in range(length): min_index: int = index_1 # 현재 위치에서 가장 작은 원소를 찾습니다. for index_2 in range(index_1 + 1, length): if arr[min_index] > arr[index_2]: min_index = index_2 # 가장 작은 ..
- Algorithms and Data Structures/Algorithms
- · 2023. 7. 29.