바른생활해보자

Two-Pointers Algorithm 두 개의 포인터로 특정 조건의 목표를 탐색하자 투포인터 알고리즘은 동작원리가 간단하며 배열에 두개의 위치값 = 투포인터(start,end)로 특정 값을 탐색할 수 있는 알고리즘이다. 좀더 길게 이야기하면, 배열 또는 리스트와 같은 선형 데이터 구조에서 특정한 조건을 만족하는 부분 구간이나 원소들을 찾는 데에 유용한 알고리즘이다. 이름에서 유추하듯 두 개의 포인터(Index)를 조작하여 원하는 값을 얻어낸다. 투포인터 알고리즘은 두 번의 탐색을 두 개의 포인터로 대처하기 때문에 시간복잡도가 O(N²)이 아닌 O(N)이된다. 투 포인터 알고리즘의 주요 사용법은 크게 2가지로 나뉜다. 두 개의 포인터를 배열의 양 끝에서 시작해서 서로 다가가며 움직이는 것 두 개의 포인..

선택 문제 (Quick-Select) 💡 크기가 n인 배열에서 k번째로 작은 수를 찾는 문제이다. 간단한 해결책 선택문제는 크기가 n인 배열에서 몇 번째로 작은 수를 찾는 탐색을하는 알고리즘을 말한다. 이런 문제는 다음과 같은 간단한 방법도 있다. 최소 숫자를 k번 찾는다. (배열을 순차적으로 다 찾는다는 말이다.) 단, 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다. O(kn) 크기가 10인 배열에서 3번째로 작은 수를 찾는다. 10개의 배열을 다 확인하여 최소 수를 찾고 배열에서 제외한다. 2번 작업을 3번 반복하여 3번째 최소 숫자를 찾는다. 숫자들을 오름차순으로 정렬(O(nlogn))한 후, k번째 숫자를 찾는다. O(nlogn) 크기가 10인 배열에서 3번쨰로 작은 수를 찾는다. 배열을 ..

퀵 정렬 (Quick Sort) 💡 피봇(Pivot)을 기준으로 왼쪽에 작은 수, 오른쪽에 큰수를 놓는 정복 후 분할하는 알고리즘이다. 퀵 정렬은 정확하게는 정복 후 분할을 하는 알고리즘이다. 퀵 정렬은 문제를 2개의 크기가 일정하지 않은 부분문제로 분할한다. 그리고 하나의 중점이 되는 원소(Pivot)를 두고 중점 기준 왼편에는 더 작은수, 오른편에는 더 큰 수를 위치하도록 분할한다. 피봇은 어느 쪽에서든 부분에 포함되지 않아야한다. 시간복잡도 퀵정렬의 성능은 피봇 선택에 좌우된다. 피봇이 가장 작은 수 or 가장 큰 수로 선택되면 한 부분이 치우치는 분할을 야기한다. 최악의 경우 퀵 정렬의 최악의 예제로 항상 가장 작은/큰 숫자를 선택하게 된다면 발생하는 시간복잡도에 대해 알아보자. 피봇 1 : 남아..

분할 정복 알고리즘 주어진 문제의 입력을 분할하여 부분문제(subproblem)로 만들어 해결하는 방식 대부분 분할 정복 알고리즘은 단순 분할이 아닌, 분할된 부분문제들로 부분해를 찾아야 한다. 분할 정복 알고리즘 예제 예제로 크기가 n인 입력값이 있을때, n을 2개로 분할때 각 부분문제의 크기가 n/2이면 각 입력 크기의 반은 n/2라고 할수있다. 이제 입력 크기가 1이 되어 분할할 수 없는 k번째까지 간다면 아래와 같은 순서가 성립된다. 이때, 입력크기가 1이되는 총 횟수를 k는 n/(2^k) 이므로 다음 시간 복잡도가 성립된다. 분할 정복 알고리즘의 분류 💡 분할 정복 알고리즘은 분할되는 "부분문제의 수 / 크기에 따라 분류"가 될 수 있다. 단순하며 비효율적 : 삽입, 선택, 버블 복잡하며 효율적..