CS/Data Structure
heap 정렬 구현하기
Heap Sort 힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 아래 그림과 같이 부모 보다 작거나 큰경우 한가지의 경우만 고려하여, 계속해서 boundary를 늘려가는 형식이라고 볼 수 있겠다. 최소힙의 경우 root에 min value가 있고, 최대힙의 경우 root에 max value가 있기때문에, 오름차순 정렬의 경우 min 힙의root를 계속 추출하면 오름차순 힙 정렬이 되고, 내림차순 정렬의 경우 max힙의 root를 계속 추출한다면 내림차순 힙 정렬이 된다는 것을 알 수 있다. 주의할 점으로 이진탐색트리(BST)와 혼동 할 수 있는데, 힙은 이진탐색트리와는 다르게 자식간의 위치가 대소관계를 반영하지는 않는 다는 점..
병합정렬 (python으로 구현하기)
Merge Sort 병합정렬? 정렬되어 있지 않은 배열을 1/2씩 재귀적으로 나누어 준 다음에, 다시 요소 끼리 차례로 합칠때 정렬을 하면서 합치는 과정을 말한다. 그런식으로 마지막에 전부 합쳐질 경우 정렬된 상태가 된다. 예를들어 2개의 정렬된 배열이 있다고 하자. [1,2,3,5] # A [4,6,7,8] # B [] # C 각각 0번 인덱스를 비교하여, 더 작은 요소를 C로 넣어주고, 넣어 준 쪽의 cursor만 한 칸 이동한다. [1,2,3,5] # A [4,6,7,8] # B [1] #C 이런식으로 되고, 반복적으로 각 cursor에 있는 값끼리 계속해서 비교하여 C에 넣어준다면 결과적으로 C=[1,2,3,4,5,6,7,8] 이 된다. merge sort의 기본 아이디어인 주어진 랜덤 배열을 하..
퀵정렬 python으로 구현하기
Quick sort 퀵 정렬? 무작위로 정렬되어있는 리스트에서 기준이 될 원소를 고르고, 그 기준보다 작은 집합과 큰 집합으로 나눠준다. 그 후에 피벗을 나뉜 두 그룹 사이로 넣어주고, 다시 작은 집합과 큰 집합에 대하여 재귀적으로 data를 swap하면서 결과적으로 모든 값이 정렬되게끔 해주는 알고리즘이다. 위 그림과 같이 정렬을 해나간다. 처음 loop구간을 구현해 보았다. pivot을 lst[-1]로 정하고 [smaller] [pivot] [bigger] 의 형태로 만들었다. pivot 을 기준으로 더 작은 수의 갯수 만큼 swap이 일어났고, 마지막에 pivot의 위치를 옮겨주었지만, 현재 pivot 만이 오름차순으로 정렬 되었을때 본인의 자리임이 확실하고, 나머지 요소들은 정렬이 된것인지 알 수..
버블정렬 + python으로 구현해보기
Bubble sort --정렬하는 여러가지 방법이 있는데 그 중에 버블정렬에 대해 공부해보았다. 보편적인 오름차순으로 정렬하였다. 버블 정렬? 버블 정렬은 랜덤으로 주어진 리스트에서 자료0과 자료1을, 자료1와 자료2 이런식으로 자료a-1과 자료a를 비교하며 자료를 비교하여, data[a-1]>data[a] 일경우 value의 swap이 일어나게 하는 생각으로 부터 시작한다. 만약 [4,1] 의 리스트를 정렬 한다면 [1,4]가 될 것이다. 하지만 다음과 같이 list의 길이가 길어질 경우에는 무언가가 더 필요한것을 알 수 있다. 코드만 생각해 보자면 현재 lst[-1] data를 제외하고는 어떤 data도 검증이 안되었기 때문에 정렬이 잘 이루어 지지 않았다. 그렇다면 버블정렬은 어떻게 완성 되었을까?..
Linked list (python으로 구현 해보기)
자료구조/알고리즘 강의 1주차 연결리스트란? 각 원소(node)의 head에는 data를 저장하고, next에는 원소가 연결되어 있다면 다음 원소의 head 주소를 저장하여 접근 할 수 있게한 일종의 비엔나 소시지 같은 느낌이라고 보면 되겠다. [출처-파이썬알고리즘 인터뷰] # 노드 선언 class Node: def __init__(self, val): self.val = val self.next = None # 리스트 선언 class L_List: def __init__(self): self.head = None self.length = 0 이런식으로 node=[val][next] 꼴로 구현해 주었고, next = None인 이유는 연결하지 않은 노드 상태이기 때문. 만약 node를 n개 생성하여 no..