# Merge sort
병합 정렬 (Merge Sort ) 알아보기 !
재귀 용법을 사용한 알고리즘.<원리>1) 특정 리스트를 두개로 쪼갠다.2) 쪼개진 각각의 리스트를 합병 정렬을 이용해 정렬시킨다.3) 정렬된 리스트를 다시 합병 시킨다.크게 2가지로 나눠보자.우선 리스트를 쪼개는 기본 원리를 익히기 위해 다음과 같이 medium이
[알고리즘] 합병 정렬, 퀵 정렬
지난번에 포스팅한 정렬들은 통상적으로 Θ(n\*\*2)의 복잡도를 가지는 정렬이였다면이번에 포스팅할 정렬들은 쉽게말해 더 고급(?)정렬이라 볼 수 있다.여기서부터는 재귀 개념이 사용된다.책에서는 합병이 아닌 병합이라 표현하지만 통상적으로 합병이라 많이 쓰기 때문에 표현
알고리즘 강의 정리7 : 합병정렬
합병 정렬은 빠르지만 조금 더 어렵다. 아주 유명한 방식이다.1948년 폰 노이만이 최초의 합병 정렬 프로그램을 작성했다.합병정렬은 두 가지 조합으로 되어 있다.합병정렬0개나 1개의 요소로 된 배열은 이미 정렬되어 있다는 점을 이용한다.배열을 더 작은 하위 배열로 나눈
Divide & Conquer
하... 실수로 작성했던 글이 날아가버렸...네요.Merge sort에 대한 핵심적인 그림은 위와 같습니다. Sorting을 하는데 array를 원본그대로(in-place) sorting 하는게 아니라 작은 단위로 쪼개서 작은 array부터 sorting 하는 알고리즘
Leetcode - 315. Count of Smaller Numbers After Self 풀이 [H]
주어진 배열에서 자기 자신의 오른쪽에 있는 값들중 자신보다 작은 값의 갯수를 구하라.numsl > numsr 일 때는 그 횟수를 cnt를 누적해서 더하다가. 크기가 반대가 되는 순간 (그동안 누적해서 더한 값이 l 의 오른쪽에있는 작은값의 갯수다)cnt값은 현재까지의
Leetcode - 912. Sort an Array
주어진 배열을 정렬하라. 단 내장 정렬함수는 사용할 수 없다.merge sort는 절반으로 계속해서 나누는 재귀함수 파트그리고 다시 merge하는 동작 두가지로 나뉘어있다.merge 동작은 합치면서 정렬( 작은값부터 배열에 넣으면) 된다. 합치기 전의 배열은 이미 정렬
[Algorithm] 합병 정렬
지금까지 배운 정렬 알고리즘(버블, 선택, 삽입 정렬)은 큰 규모에 맞지 않는 알고리즘이다.우리가 이제부터 알아볼 빠른 알고리즘 집합은 시간 복잡도를 O(n^2)에서 O(n log n)으로 향상시킬 수 있는 알고리즘이다.그중 합병 정렬(Merge Sort)에 대해 먼저
[Node.js]백준 24060: 알고리즘 수업 - 병합 정렬 1
백준 선생님께서 서준이 아빠 어쩌고 하면서 쉬운 척하면서 어려운 문제를 내주셨다.
병합정렬 알고리즘(merge sort algorithm)
병합정렬 알고리즘은 천재만재 폰 노이만 선생님께서 1948년에 최초로 작성하신 알고리즘이다.
Merge sort에 관하여..
merge sort는 quick sort 와 비슷하게 분할 정보 알고리즘의 하나이며 quick sort는 피벗의 값에 따라 편향되게 분할 될 수 있지만 merge sort는 안전하게 반절씩나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간 복잡도를 보장함. 병
Leetcode - 148. Sort List
주어진 링크드 리스트를 오름차순 정렬하라.각 노드를 heap에 넣고 하나씩 pop하면서 새로 링크르 리스트를 생성.기존 노드를 재조합해서 새 링크드 리스트를 생성할때는 마지막 노드부터 시작해서 head로 만들어야함. 아래 코드 참고따라서 heap은 max heap이어야
[알고리즘] 합병정렬(Merge Sort)
|시간복잡도|O(N)| |------|---| |Best|O(nlogn)| |Average|O(nlogn)| |Worst|O(nlogn)|
42 push_swap (5)
push_swap에서 merge sort를 구현한 과정입니다.merge sort알고리즘은 아래의 노션을 참고했습니다.Push Swap 병합정렬로 해결하기위의 노션을 읽고 나서 코드를 작성하려고 하면 몇 가지 의문이 생깁니다.그래서 지금 만들어야 하는 삼각형의 크기는?그
[Algorithm] Divide and Conquer
1. 분할정복(Divide and Conquer) > - 대표적인 알고리즘 설계 기법 중 하나 > - 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시