알고리즘 (4) 썸네일형 리스트형 그리디 알고리즘 그리디 알고리즘이란 그리디 알고리즘이란 전에 선택했던 것과 미래에 다가올 선택에 관계없이 현재 가장 최고의 것을 선택하는 알고리즘이다. 직접적으로 명시된 제약조건을 빠르게 해결하는데 사용하고 순간순간 최적의 선택으로 솔루션에 도달한다. 그리디를 사용할 때는 항상 지금 사용하는 그리디 해결법이 최적인지 생각해야 한다. 그 순간에만 최적의 방법일 수 있고 다른 부분 문제에서는 최적의 방법이 아닐 수 있기 때문이다. 다음은 그리디 알고리즘으로 접근하는 것이 항상 옳은 해가 아니라는 예이다. 그리디 설계법 1. 그 순간에 최적 상태를 고려하여 원소들을 뽑아낸다. 2. 현재 사용한 방법이 다른 부분 문제에 대하여 최적인지 고려한다. 예제 다음은 정해진 시간동안 최대로 들을 수 있는 강의 수를 찾는 문제이다. 주어.. 3. 분할정복 - 퀵 정렬 퀵 정렬이란? 퀵 정렬은 병합 정렬과 마찬가지로 분할정복을 이용하여 정렬을 한다. 퀵 정렬은 피벗을 이용한 정렬 방식이다. 피벗은 두 개의 집합을 나누기 위해 생성된 기준으로 피벗보다 작은 것은 왼쪽으로 피벗보다 큰 것은 오른쪽으로 정렬이 된다. 피벗은 어떤 수가 되어도 상관이 없다. 피벗을 기준으로 두 개의 집합을 나누는 분할의 과정을 거치면 다시 피벗을 기준으로 정렬을 한다. 다음은 퀵 정렬을 표현한 예이다. 시간복잡도 퀵 정렬은 두 개의 집합으로 분할하는 것과 피벗을 기준으로 정렬하는 것으로 정렬을 수행한다. 두 개의 집합으로 분리하는 시간은 항상 O(n)을 유지한다. 피벗을 기준으로 정렬하는 시간은 자료의 배치에 따라 평균적으로 O(logn)을 유지하고 최악의 경우는 O(n2)까지 시간이 걸린다... 2. 분할정복 - 병합정렬 병합정렬이란? 주어진 수열을 범위를 나누어 정렬하는 방법이다. 우선 모든 수열을 잘게 쪼개는 분할의 과정을 거치고 나누어진 수열을 차례대로 정렬한 뒤 합친다. 다음은 병합정렬을 표현한 예이다. 위에서 설명한 것 처럼 가장 작은 단위로 분할한 뒤에 큰 쪽으로 합쳐가는 것을 알 수 있다. 따라서 알고리즘을 설계할 때, 분할하는 부분과 정렬하여 합치는 부분 두가지로 나누어 설계해야한다. 시간복잡도 병합정렬은 항상 시간 복잡도 O(nlogn)을 유지한다. 따라서 데이터 분포에 영향을 받지 않는다. 구현 병합정렬 구현은 다음과 같다. #include #include using namespace std; int cnt = 1; //정렬이 진행된 횟수 void merge(vector &v, int low, int m.. 1. 분할정복 - 이분 탐색 이분탐색이란? 이분탐색은 어떤 기준으로 정렬이 된 수열에서 원하는 원소를 찾을 때 사용하는 방법이다. 주어진 수열에서 중간 값을 기준으로 찾는 값이 중간 값보다 작으면 처음 ~ 찾는 값까지 탐색하고 찾는 값이 중간 값보다 크면 중간 값 ~ 끝 값을 탐색하는 형태로 진행한다. 이것은 분할-정복 알고리즘을 사용한 형태로 큰 문제에서 작은 문제로 결과를 줄여나가 원하는 값을 얻어내는 형태이다. 예시는 다음과 같다. ex.) 주어진 값 : 1 3 4 5 8 12 15 20 24 30 49, 찾는 값 : 30, 1. 1 3 4 5 8 12 15 20 24 30 49 -> 중간 인덱스는 11/ 2 = 5이고 중간 값은 12이다. 12 중간 인덱스.. 이전 1 다음
