에르미타쥬 에르미타쥬

지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort였습니다. 두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn)보다 큽니다. 예를 들어서 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있습니다. 하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘입니다. - counting sort 예를 들어, 다음과 같은 input array에 대해 counting sort를 수행한다면, inp..

힙이라는 자료구조는 무엇일까. 한 노드(node)가 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리구조를 말한다.모든 노드의 값이 각자의 자식 노드의 값보다 크거나 같은 것을 최대 힙(Max heap)이라한다.모든 노드의 값이 각자의 자식 노드의 값보다 작거나 같은 것을 최소 힙(Min heap)이라한다.힙은 최대 힙이거나 최소 힙이어야 한다.또한, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 완전이진트리(complete binary tree)이다. 이러한 힙 속성(최대 힙, 완전이진트리)를 만족하면 다음 그림처럼 트리구조가 완성된다.힙은 완전이진트리 성질을 만족하기 때문에 1차원 배열로도 표현이 가능하다. [100, 19, 36, 17, 3, 25, 1, 2, 7]..

https://www.acmicpc.net/problem/1021 큐를 움직일 함수를 먼저 정의한다. 포인터를 어디로 이동할지 결정하기 전에 예비로 포인터를 인덱스 0에 두고 뽑아내려는 수와 인덱스0의 수가 같아질 때까지 포인터를 오른쪽 이동해본다.수가 같아지면 right에 담긴 숫자를 확인해 얼만큼 오른쪽으로 이동했는지 확인한다. 그리고 큐의 전체 길이에서 오른쪽으로 이동한 횟수를 뺴 왼쪽으로 이동해야할 횟수를 구한다. 그리고 오른쪽으로 이동한 횟수, 왼쪽으로 이동한 횟수를 비교해 이동횟수가 적은 방향을 선택해 실제로 포인터를 이동한다.정의한 함수는 이동 후 포인터가 큐에 위치한 인덱스, 이동횟수를 반환한다 for문을 활용해 뽑아내려고하는 수를 차례로 함수에 넣는다. for문이 돌때마다 함수가 반환한 ..

https://www.acmicpc.net/problem/5639전위 순회(Preorder traversal)는 기존의 트리구조를 그대로 보존해 다른 곳으로 옮길 수 있다는 장점이 있다. 이 문제에선 그 장점을 이용한다. 전위 순회 값을 받아 그대로 투입하면 온전한 트리구조를 만들 수 있다. 그 트리를 다시 후위 순회로 뽑아내기만 하면 된다. 하지만 보다시피 '실패' 예제 입력과 예제 출력을 충실하게 반영하므로 잘못 짠 것 같진 않다. 하지만 미세한 반례가 있는지 계속 틀리다고 한다. 내 생각엔 지금까지 풀어본 문제에 비해 이 문제의 입력 조건이 특이해서 그런 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142..

삽입 정렬(Insertion Sort) 123456789def insertionSort(x): for size in range(1,len(x)): val = x[size] i = size while i > 0 and x[i-1] > val: x[i] = x[i-1] i-= 1 x[i] = val return xcs버블 정렬(Bubble Sort)123456def bubbleSort(x): for size in reversed(range(len(x))): for i in range(size): if x[i] > x[i+1]: x[i], x[i+1] = x[i+1], x[i] return xColored by Color Scriptercs선택 정렬(Selection Sort)123456789def selec..