알렉스 페레이라의 격투 블로그

힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 힙정렬에 대해 설명하기 위해서는 트리에 대해서 설명이 필요하다. 트리란?? 트리는 두 지점의 연결 관계로 구성되어 있는데, 계층관계가 존재한다는 것이 특징다. 우리는 하나의 연결 관계에서 위쪽에 있는 점을 부모라고 부르며, 아래쪽에 있는 점을 자식이라고 부를 것 입니다. 이 외에도 추가적인 용어들이 많은데, 아래쪽 사진을 참고하면서 용어를 이해해봅시다. 노드: 각 지점을 의미합니다. 루트 노드: 트리에서 맨 꼭데기를 의미합니다. 위쪽 조직도를 보면, 루트 노드는 회사 대표가 되겠죠? 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미하는데, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고..

퀵소트를 만나기전까지 제일 이해가 안됐던 병합정렬을 기록한다. 병합정렬이란?? 병합정렬은 분할정복(Divide & Conquer)정렬중 하나로, 특정 리스트를 분할하고, 정렬하여, 병합하는 일련의 과정을 거치며 정렬한다. 퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가지지만 병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N*logN)을 보장한다. 합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 하향식 합병 정렬에 대한 자세한 설명과 분석은 1..

정렬을 배우기 시작했다. 버블정렬, 선택정렬, 삽입정렬, 기수정렬, 병합정렬 등 다양한 정렬을 배웠다. (병합정렬이 가장 어려웠음) 코딩테스트 오픈카톡방에서 고수들끼리 하는 퀵 소트를 배울 차례가 됐다. 아무리 읽어도 도~저히 이해가 안되는것이다. 그러던중 유튜브에서 좋은 알고리즘 해석영상을 찾고 바로 이해가 되었다. https://www.youtube.com/watch?v=cWH49IKDIiI&ab_channel=%EC%BD%94%EB%94%A9%ED%95%98%EB%8A%94%EA%B1%B0%EB%8B%88 내가 이해한 퀵소트는 다음 순서를 따른다. pivot을잡는다. pivot이란 퀵소트에서 가장 중요한 개념으로, 쉽게말하면 기준을 잡는것이다. 위 영상과 코드트리에서는 배열 제일 마지막값을 pivo..