이것저것 코딩하는 블로그

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 생각한 풀이: 32 3222 34 3444 라는 예제를 보고, 맨 뒤만 반복하여 4자리로 정렬 기준 수를 만들어준 뒤 (3222 3222 3444 3444) 이 숫자로 정렬하고, 만약 정렬 기준 수가 같을 때는 원래 수가 더 짧은 기준 정렬 수를 a, 긴 기준 정렬 수를 b라고 했을 때 a[0] > a[-1]이면 a를 앞에 두고, 아니면 b를 앞에 두었다. 이럴 경우 위와 같은 예제를..

0. Heap Sort란? 자료구조인 heap을 이용한 정렬이다. 먼저 heap이 무엇인지 살펴보자. 1) Heap heap은 max-heap, min-heap 두 개로 나눌 수 있다. max-heap을 이해하면 min-heap을 이해하기 쉬우니 max-heap을 살펴보자. heap은 이진 트리의 형태를 띈다. 이진 트리란, 트리 구조를 가지고 있으면서 각 노드가 최대 2개의 자식을 갖는 트리이다. max-heap이란, 부모의 값이 자식의 값보다 항상 큰 이진 트리이다. 따라서 루트 노드는 전체의 최댓값을 갖게 된다. min-heap은 부모의 값이 자식의 값보다 항상 작은 이진 트리이다. 따라서 루트 노드는 전체의 최솟값을 갖게 된다. 2) 이진 트리를 배열으로 구현하기 이진 트리 형태를 떠올리면 배열과..

0. Quick Sort (퀵 정렬) 이란? 기준 (pivot)을 잡아 pivot보다 큰 원소는 뒤에, 작은 원소는 앞에 놓으면서 정렬하는 것이다. 마지막엔 가운데에 pivot을 넣어준다. 그러나 pivot보다 작은 원소, 큰 원소끼리는 정렬되어 있지 않을 것이다. 즉, pivot의 왼쪽, 오른쪽에 대해 다시 정렬을 수행해야 한다는 것이다. 따라서 이도 재귀를 이용한다. [1, 4, 3, 5, 2] 를 맨 오른쪽 원소를 pivot으로 삼아 정렬한다고 하자. 한 번의 pivot을 기준으로 한 분할을 이용하면 다음과 같은 결과가 출력될 것이다. [1, 2, 4, 3, 5] 2의 왼쪽에는 1 하나뿐이므로 더 이상 정렬할 필요가 없다. 따라서 우리는 [4, 3, 5]를 정렬해야 한다. 마찬가지로 가장 오른쪽 원..

0. Merge Sort (병합 정렬) 이란? 병합 정렬이란, 배열을 쪼개서 정렬한 후 다시 그 쪼개진 배열들을 정렬하며 합치는 것을 말한다. 예를 들어, [1, 3, 5, 2] 이라는 배열이 있다고 하자. 이 배열을 반으로 쪼개면 [1, 3], [5, 2] 이 될 것이다. 이들을 각각 정렬하면 [1, 3], [2, 5] 가 된다. 이들을 합치며 정렬한다는 것은, 각각의 원소를 비교하여 작은 것부터 새 배열에 입력하는 것이다. 1 2 이므로 2가 두번째, 3 < 5 이므로 3이 세번째, 마지막에 5가 입력될 것이다. 이를 어떻게 코드로 구현할 수 있을까? 지금 든 예제는 4개여서 반으로 갈라 정렬하는 것이 쉬웠지만, 실제로는 그렇지 않다. 따라서 배열의 원소가 하나..

0. Radix Sort (기수 정렬) 이란? 기수 정렬이란, 맨 뒤에 있는 자릿수부터 해당 자릿수를 기준으로 정렬한 뒤, 한 칸씩 (한 자리씩) 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다. 숫자들 간의 자릿수가 다르다면 어떻게 할까? 자릿수가 작은 수의 앞을 0으로 채우면 반드시 작아지게 된다. (ex. 100, 99의 경우 100과 099를 비교하면 마지막에는 가장 높은 자리수와 비교하므로 1과 0이 비교되어 100이 더 크다고 판별된다). 음수가 섞여 있는 경우에는 음수랑 양수를 구분하여 정렬한 후 합치면 된다. 이 때 음수는 절댓값으로 변환하여 비교한 뒤 reverse해주면 정렬된 값을 얻을 수 있다. (ex. -3, -40, -12 ..

0. Insertion Sort (삽입 정렬) 이란? Insertion Sort란, 앞에서부터 순서대로 보면서 앞에 있는 모든 원소가 정렬이 되어있다는 가정 하에 현재 원소의 위치를 적절하게 집어넣는 정렬이다. 앞의 모든 원소가 정렬이 되어있으므로, 현재 위치의 원소가 어디에 들어갈 지 앞의 모든 원소를 한 번만 돌아보면 알 수 있을것이다. 이 과정을 현재 원소가 두번째일때부터 n번째일때까지 반복한다. n개의 원소에 대해 값 삽입을 수행해야 하는데, k번째 원소의 경우 최대 k-1개의 원소를 이동해야 하므로 비교 연산이 1+2+...+(n-1) = n*(n-1)/2번 일어난다. 따라서 시간복잡도는 O(n^2)이다. 1. 구현 n = int(input()) nums = input() num = nums.s..