Algorithm/Concepts18 동적 계획법(DP, Dynamic Programming) 목차 동적 계획법(DP, Dynamic Programming) 동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 풀고, 그 결과를 저장하여 큰 문제를 풀어나가는 것입니다. 문제에서 규칙 또는 점화식을 발견한다면, 동적 계획법(DP)를 사용하여 문제를 해결할 수 있습니다. 중복되는 계산 과정을 저장하여 시간을 절약할 수 있습니다. DP는 너무나도 많은 유형이 있고, 직접 다양한 문제들을 경험하며 실력을 키워나가야 합니다. 어떤 것을 메모이제이션(memoization)해서 이용할 것인가가 가장 중요합니다. (큰 문제를 작은 문제로 나눠서 풀때 중복되는 부분을 찾아야 합니다.) 예시 예시 1 (피보나치 수) 가장 대표적인 예시인 백준 2748 피보나치 수 2 문.. 2023. 10. 15. 이분 탐색(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. 이전 1 2 3 4 5 다음
