Algorithm37 이분 탐색(Binary Search) 목차 이분 탐색(Binary Search) 이분 탐색(Binary Search)은 정렬된 배열에서 특정한 원소(또는 해당하는 위치의 인덱스)를 찾아내는 탐색 알고리즘입니다. 정렬된 배열의 중간에 있는 원소를 선택하여 찾고자 하는 값과의 크기를 비교하며 원하는 원소를 찾아냅니다. 정렬된 배열의 중앙값과 찾고자 하는 값을 비교합니다. 만약 중앙값이 찾는 값보다 크면, 중앙을 기준으로 왼쪽 부분 배열에서 탐색을 이어갑니다. 만약 중앙값이 찾는 값보다 작으면, 중앙을 기준으로 오른쪽 부분 배열에서 탐색을 이어갑니다. 원하는 값을 찾거나, 탐색할 부분 배열의 크기가 0이 될 때까지 이 과정을 반복합니다. 또는 어떤 연속적인 값의 범위가 주어지고, 그 안에서 임의로 값을 지정해서 찾을 때도 이분 탐색을 적용할 수 .. 2023. 10. 14. 분할 정복(Divide and Conquer) 목차 분할 정복(Divide and Conquer) 분할 정복은 큰 문제를 독립적인 작은 문제들로 나누어 해결합니다. 각각의 작은 문제들은 독립적으로 해결되며, 결합 단계에서 이러한 작은 문제들의 해답을 결합하여 큰 문제의 해답을 얻습니다. 따라서 재귀형태로 구현하는 경우가 많습니다. 대표적인 예시로는 병합 정렬(merge sort), 이분 탐색(binary search) ,거듭제곱 연산(a^n)등이 있습니다. 병합 정렬 이분탐색 거듭제곱 연산 기본적인 거듭제곱 연산의 시간복잡도는 O(n)입니다. 이는 'a'를 'n'번 곱하는 것을 의미합니다. 분할 정복을 사용하면 이를 O(log n)으로 줄일 수 있습니다. 분할정복과 Top-Down 방식의 DP와 차이점 분할정복은 DP의 Top-Down 방식과 유사합.. 2023. 10. 12. 탐욕법(Greedy) 목차 탐욕법(Greedy) 탐욕법 또는 그리디 알고리즘은 문제 해결의 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 방법입니다. 하지만 그리디 알고리즘으로 최적의 해를 구할 수 있는 문제는 많지 않습니다. 그 이유는 항상 눈앞의 가장 큰 이익만을 쫓기 때문입니다. 따라서 그리디 알고리즘을 적용할 때는 잘못된 방향으로 가고 있지 않는지 꼼꼼히 확인이 필요합니다. 문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 취할 수 있을 때만 그리디 알고리즘을 적용할 수 있습니다. 그리디 알고리즘의 대표적인 문제인 동전 문제를 예시로 들어보겠습니다. 그와 동시에 그리디 알고리즘의 한계도 살펴보겠습니다. 동전 문제 : 10원, 50원, 100원, 500원짜리 동전들을 사용해서 어떤 금액을 표현하려고 할 .. 2023. 10. 10. 큐(Queue), 스택(Stack) 목차 큐(Queue) 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식입니다 출처 : 위키피디아 줄 서기 개념을 생각하면 됩니다. (먼저 줄 선 사람이 먼저 나가게 됩니다.) 파이썬에서는 deque를 이용하면 쉽게 구현이 가능합니다. from collections import deque q = deque() for i in range(5): q.append(i) while q: print(q.popleft()) """ 0 1 2 3 4 """ 스택(Stack) 스택(stack)은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO(Last In First Out)으로 되어 있습니다. 출처 : 위키피디아 책 쌓기 개념을 생각하면 됩니다. .. 2023. 10. 10. 이전 1 ··· 6 7 8 9 10 다음
