자료구조 & 알고리즘8 [정렬 알고리즘] 힙 정렬 2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬 📎 힙 정렬 힙 정렬은 힙(heap)을 사용해 정렬하는 선택 정렬 응용 알고리즘이다. 힙 Heap 힙이란 차곡차곡 쌓아올린 더미라는 뜻으로 완전이진트리 구조를 가진다. 완전 이진 트리 형태는 부모 노드 밑에 자식노드가 2개 이하로 제한된 구조로 가장 기본적이고 간단한 트리 형태를 말한다. 힙의 특성 최대힙 Max Heap : 부모 노드 값은 항상 자식 노드 값보다 크다 (=Root 노드 값이 가장 크다) 최소힙 Min Heap : 자식 노드 값은 항상 부모 노드 값보다 크다 (=Root 노드 값이 가장 작다) 기본적으로 힙정렬은 최대힙의 특성을 가지고 정렬을 구현한다. 힙의 배열 저장은 위의 사진 2)를 참고해서 보면 쉽다. 부모는 A.. 2021. 10. 1. [알고리즘] 다이나믹 프로그래밍 (동적 계획법) 동적 계획법 Dynamic Programming (DP) 동적 계획법은 주어진 문제를 하위 문제로 나눠 풀고 그 결과를 저장해 다음 문제를 푸는데 사용하는 알고리즘이다. 이는 분할 정복 Divide and Conquer과 비슷해보이지만 동적계획법에서는 하위문제가 서로 종속성을 가진다는 점이 다르다. 즉 문제를 풀고 그 답이 다른 문제에 영향을 끼칠 수 있다는 것이다. (= 메모이제이션) 동적 계획법의 핵심은 같은 문제의 중복 호출을 피하자는 것이다. 동빈나님의 설명으로는 '하나의 문제를 단 한번만 풀도록 하는 알고리즘' 이라는 것이다. 동적계획법을 사용하기 적절한 문제의 특징은 이렇다. 최적화 문제이다 재귀적 구조를 가져 재귀 구현했을 때 중복 호출로 비효율이 발생한다. 최적화 문제라는 것은 하나의 문제.. 2021. 9. 9. [정렬 알고리즘] 병합 정렬 (합병 정렬) 2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬 📎 병합 정렬 Merge sort 병합 정렬은 정렬을 앞부분과 뒷부분으로 나눈 후 정렬하고, 병합하는 과정을 반복하는 정렬이다. 성능은 퀵정렬보다 떨어지는 편이고 메모리도 많이 쓰지만 안정형 정렬이라는 장점을 가지고 있다. 먼저 이 배열을 앞부분과 뒷부분으로 나눠준다. 그리고 또 앞부분과 뒷부분을 나눠줬다. 여기서 더 이상 나눠지지 않으니 정렬을 시작한다. 앞부분에서 정렬, 뒷부분에서 정렬해준다. 그리고 앞부분 모두를 다시 정렬한다. 뒷부분도 위와 같은 과정을 반복한다. 앞부분과 뒷부분이 잘 정렬이 되었다. 이제 이 두 부분을 가지고 비교, 합병을 한다. 두 부분에서 가장 작은 값끼리 비교를 한다. 0이 작으니 0의 위치는 정해졌고 0.. 2021. 9. 9. [정렬 알고리즘] 삽입 정렬 2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬 📎 삽입 정렬 삽입 정렬은 선택한 요소를 앞쪽의 알맞은 위치로 삽입해 정렬하는 알고리즘이다. 이는 사람들이 생각하는 가장 일반적인 정렬이다. 선택 정렬과 비슷해보이지만 선택 정렬은 먼저 가장 최솟값을 선택하고 앞쪽 요소와 SWAP하는 방식이고 삽입 정렬은 두번째 위치한 요소부터 앞쪽 요소들과 비교, 정렬해 알맞은 자리로 삽입하는 방식이다. 삽입정렬의 과정 배열의 두번째 요소부터 선택 선택한 요소보다 앞쪽에 위치한 요소들과 비교해 알맞은 자리로 삽입 마지막 요소까지 반복 자바 코드로 구현해보면 이렇게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2.. 2021. 9. 8. 이전 1 2 다음
