전체 글16 Comparison Model 에서의 정렬 알고리즘의 시간복잡도 [주의] 이번 주제는 좀 더 수학적인 증명이 가미되어 있습니다. 이번 시간의 주제는 과연 정렬 알고리즘의 Worst Case 시간 복잡도 (Time Complexity) 의 Lower Bound 에 대한 수학적 증명입니다. 이 때, 이번 주제에서 정렬 알고리즘의 경우 Comparison Model, 즉 "임의의 배열 A 내에서 임의의 두 Element 들을 선택해 상수 시간 (Constant Time) 내에 두 element 값의 비교 (Comparsion) 를 통해 한 쪽이 다른 element 에 비해 작거나 크다는걸 결정할 수 있다" 를 전제하고 있습니다. 조금 더 디테일한 전제조건들은 다음과 같습니다. 1. 서로 다른 두 원소들간의 상대적인 순서를 값의 비교를 통해 결정한다 2. 서로 다른 임의의 .. 2022. 8. 5. Dynamic Programming (동적 계획법) - 기본 개념 및 Recursion 을 통한 정의 보다 효율적인 알고리즘을 위해 활용할 수 있는 패턴이 다이나믹 프로그래밍입니다. 많은 분들이 아마 어려워하는 유형일 텐데요, DP 에서는 아래 사항들만 엄밀하게 따져준다면 생각보다 알고리즘 자체는 이해하기 어렵지 않습니다. Dynamic Programming (동적 계획법) 을 통한 문제 해결 1. Subproblem Definition (부분 문제 정의) DP 에서는 Recursion (재귀 호출) 과 마찬가지로 복잡한 큰 문제를 여러개의 작은 문제 (Subproblem) 들로 쪼개어서 생각합니다. 즉, 하나의 큰 덩어리가 아닌 어떤 입력값에 대한 매 순간마다의 작은 덩어리를 생각하는겁니다. 2. Subproblem Relation (부분 문제 연결) Subproblem 에 대한 정의가 끝났다면, 그 .. 2022. 4. 21. Leetcode 문제 풀이 (1) - 합이 k 가 되는 부분 배열 (Subarray) 의 갯수 문제 기술 (Problem Statement) 정수 배열 nums 와 어떤 정수값 k 가 주어질 때, 모든 원소 (Element) 들의 합이 k 가 되는 부분 배열 (Subarray) 의 갯수를 구하여라. 문제 유형 (Category) Prefix Sum 출처 (References) Subarray Sum Equals K - LeetCode 문제 설명 (Explanation) 다소 낮은 acceptance rate 을 보이는 문제로, brute force (주먹구구식) 형태의 솔루션은 생각해내기 쉬우나, 제일 효율적인 (Optimal) 솔루션을 위해서는 DP (Dynamic Programming) 기법과 수학적 직관이 필요한 문제입니다. 우선 문제 분석부터 해봅시다. 주어진 데이터는 integer arr.. 2022. 4. 18. Complexity Analysis (2) - Asymptotic Analysis (점근적 분석) 서문 (Preface) 지난 포스팅에서는 알고리즘의 정의와, 효율성을 분석하는 방법, 그리고 알고리즘의 복잡도를 시간과 공간적인 측면에서 수학적으로 기술할 수 있다는 것에 대해 알아봤습니다. 그리고 이번 포스팅에서의 주제는 이걸 확장시켜서 구체적으로 어떤 방법을 통해 복잡도를 기술할 수 있는지를 다루도록 하겠습니다. 복잡도의 점근적 분석 (Asymptotic Analysis) 점근적 분석이란, 자료의 갯수 \( n \) 값이 커질수록 이에 따라 \( n \) 에 관한 어떤 알고리즘의 복잡도가 어떤식으로 변화해 나가는지를 의미합니다. 이 때, 충분히 큰 \( n \) 에 대하여 주어진 \( n \) 에 관한 함수 \( f(n) \) 을 또 다른 함수 \( g(n) \) 을 통하여 나타낼 수 있는데, (\(.. 2022. 4. 18. 이전 1 2 3 4 다음
