거누의 개발노트

정렬? 엑셀이나 문서작성 프로그램을 사용한 사람이라면 데이터를 오름차순 혹은 내림차순으로 정렬 해본적이 있을 것이다. 정렬이란 데이터의 집합을 어떠한 기준(핵심항목, key)으로 기준의 최소값이면 최대값까지 최대값이면 최소값까지 일정한 순서로 줄지어 세우는 것이다. [4, 6, 2, 9, 1] # 정렬되지 않은 배열 [1, 2, 4, 6, 9] # 오름차순으로 정렬된 배열! [9, 6, 4, 2, 1] # 내림차순으로 정렬된 배열! 버블정렬? 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 소스코드 def bubble(lst): for i in range(l..

힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가기때문에 최대의 값들을 빠르게 구할 수 있다. 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다! 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다! 8 Level 0 6..

이진 탐색 트리란? 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가진다. 평균적으로 탐색의 시간복잡도는 O(logN), 치우친(skewed) 경우 O(n) 따라서 균형이 중요하다. 아래 그림에서 균형잡힌 경우와 치우친 경우를 확인할 수 있다. 이진 트리의 검색, 삽입, 삭제 검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 ..