CS/Datastructure & Algorithm30 다이나믹 프로그래밍(Dynamic Programming) 이란? 동적계획법 (Dynamic Programming) 이란? 최적화 문제를 위해 고안된 기법으로 복잡한 문제보다 간단한 여러 개의 부분 문제로 나누어 해결합니다. 중요한 점은 한 번 계산된 부분 문제의 답을 저장해 두어 나중에 같은 부분 문제의 답을 원할 시, 반복되는 연산 없이 바로 저장해 둔 걸 꺼내 쓸 수 있도록 하는 것이 핵심입니다. 주로 중복되는 부분 문제(Overlapping Subproblem)와 최적 부분 구조 (Optimal Substructure)를 가지고 문제들을 풀 때 사용됩니다. 또한, 동적 계획법을 설계할 때는 가장 중요한 것이 현재 문제의 상태와 문제와 부분 문제 간의 관계 또는 전이를 파악하는 것입니다. 문제들 간의 관계 또는 전이를 정확하게 파악한다면 알고리즘의 정당성을 얻을 .. 2022. 3. 16. 정렬 알고리즘 비교 In-Place ? 입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. Stable ? Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 버블 정렬 선택 정렬 삽입 정렬 셸 정렬 합병 정렬 퀵 정렬 힙 정렬 2022. 3. 13. 힙 정렬 (Heap Sort) 이란? 힙 정렬이란? 자료구조 힙(heap)을 구성하여 정렬하는 방법이다. 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이며 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 이다. 이진트리란? 컴퓨터 안에서 데이터를 표현할 때 데이터를 각(Node)에 담은 뒤 노드를 두 개씩 이어 붙이는 구조이다. 최대 힙트리나 최소 힙트리를 구성해서 정렬하는 방법이다. 내림차순 -> 최대 힙(부모노드가 자식 노드보다 큰 힙)으로 구성 오름차순 -> 최소 힙(자식노드가 부모노드보다 큰 힙)으로 구성 1. 정렬해야할 N 개의 요소들로 최대힙(완전 이진트리 형태)를 만든다. *최대힙이니, 내림차순 기준 2. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. 3. 삭제되는 요소들(최대값.. 2022. 3. 13. 퀵 정렬 (Quick Sort) 란? 퀵 정렬이란? 하나의 배열을 피벗(pivot) 을 기준으로 두 개의 비균등한 배열로 분할하고 분할된 부분 배열을 정렬한 다음 두 개의 정렬된 배열을 합하여 전체 정렬된 배열이 되게하는 방법이다. 퀵 정렬은 3단계로 이루어졌다. 분할 단계 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다. 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들 피벗을 중심으로 오른쪽 : 피벗보다 큰 요소들 정복 단계 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 '순환 호출' 을 이용하여 다시 분할 정복 방법을 적용한다. 결합 단계 : 정렬된 부분 배열들을 하나의 배열로 합병한다. 퀵 정렬 장단점은 ? 속도가 빠르다는 장점을 갖고 있다. 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다. 또.. 2022. 3. 13. 합병 정렬 (Merge Sort) 란? 합병 정렬이란 ? 합병? 병합? 둘 다 사용해도 되는 정렬 이름이다. - 합병 : A와 B가 합쳐져서 C가 만들어진다. - 병합 : A가 B의 일부가 되거나? B가 A의 일부가 됨. 분할을 이용하는 분할 정복 알고리즘이다. 말 그대로인 배열을 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 정렬이다. 합병은 binary tree 형태로 쪼개지기 때문에 가질 수 있는 최대 깊이는 log N이 된다. 병합 정렬의 단계가 존재하는데, '분할, 정복, 결합' 3가지로 나누어 볼 수가 있다. 분할 단계 : 입력된 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 단계 : 부분 배열을 정렬한다. (*여기서 부분 배열의 크기가 충분히 작지 않다면? '순환 호출'을 이용하여 다시 분할 정복법을 적용.. 2022. 3. 13. 셸 (Shell Sort) 정렬 란? 셸 정렬이란 ? 삽입 정렬보다 개선된 정렬이라고 생각할 수 있다. 삽입 정렬은 거의 정렬되어 있다면, 좋은 효율을 보여준다는 장점이 있었지만? 그 반대로 역순에 가까운 수열이 주어진다면 그만큼 좋지 않은 효율을 보여주었다. 그래서 "수열을 어느정도 정렬되게 바꾼 다음에 삽입 정렬을 쓰면 좋지 않을까?" 라는 생각으로 만들어 진 게 셸 정렬이다. 삽입과는 다르게 셸은 전체의 리스트를 한 번에 정렬하지 않는다. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수(gap)의 부분 리스트로 만든 후 이 과정을 반복한다. 셸 정렬 장단점은.. 2022. 3. 13. 삽입 정렬(Insertion Sort) 란? 삽입 정렬이란? 정렬이 되어 있지 않은 '부분'의 데이터를 뽑아 정렬된 '부분'의 적절한 위치에 삽입하는 방법이다. 다시 설명하자면, 자료 배열의 모든 요스를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입하는 정렬이다. 삽입정렬 장단점은? 이미 정렬이 되어있는 배열이 주어지면 자리 바꿈이 일어나지 않고, 딱 한 번씩 앞의 숫자와 비교 검사를 하기 때문에 이러한 Best 상황에서는 O(n)의 시간복잡도를 가진다. 거의 정렬이 되어있는 배열이라면 버블, 선택, 삽입 중에선 삽입 정렬이 가장 중요하다. 하지만, 역순으로 되어있는 배열이나, 배열의 수, 즉 길이가 길다면 그만큼 비교와 자리 바꿈 횟수가 많아지므로 삽입 정렬을 사용하기엔 부적합하다. 시간복잡도는 ? - 데이터가 이미 .. 2022. 3. 13. 선택 정렬 (Selection Sort) 란? 선택 정렬이란? 정렬 방법 중, 버블 정렬 다음으로 느린 정렬이다. 버블 정렬과 비슷하게 구현이 되며, 메모리 공간을 추가로 필요로 하지 않는다. 주어진 배열에서 최소값을 찾아 맨 앞 값과 교체를 한다. 선택 정렬 장단점은? 코드 구현이 쉽고 데이터양이 적을 때, 효율이 좋다 하지만, 데이터 양이 많을 때 효율이 떨어진다 즉, 데이터 양이 적을 때 정렬을 사용하면 좋다. 그리고 버블 정렬보다 빠르지만, 퀵, 삽입 정렬에 비해서는 느리다. 시간 복잡도는? 시간복잡도는 O(n²) 이며, 불안정 정렬(Unstable sort) 이다. 비교 시 같은 값으로 처리하지만, 실제 값이 다른 경우 정렬 후 순가 바뀔 수 있는 정렬이다. 2022. 3. 13. 이전 1 2 3 4 다음
