정렬 알고리즘 정리 정렬은 쉽게 간단히 구현할 수 있는 간단한 정렬과 복잡하게 구현하는 복잡한 정렬이 있다. 당연한 이야기지만 간단한 정렬은 그만큼 성능이 떨어지며, 복잡한 정렬은 구현이 쉽지 않지만 그만큼 성능이 좋다. 이번 포스팅에서는 정렬 알고리즘에 대해 정리해보고자 한다. 버블정렬 버블정렬은 말 그대로 물방울이 터지듯이 하나씩 정렬이 되어가는 정렬이다. 예를 들어 가장 큰 것을 가장 오른쪽으로 보내고, 그 다음 두번째로 큰 것을 오른쪽에서 두번째로 보내는 방식으로 반복되는 정렬이다. 아래 그림을 통해 예시로 설명한다. 위 이미지는 초기 값으로 3,2,1,5,4가 정렬된 배열을 버블 정렬로 정렬하는 과정을 보여주는 그림이다. 왼쪽 그림은 좌측에 가장 큰 값을 가장 오른쪽으로 옮기는 경우, 오른쪽의 ..
Heap이란 무엇인가? Heap은 우선순위 큐를 구현하기 위해 고안된 자료구조다. 우선순위 큐는 일반적인 큐의 선입선출 동작과는 다른 동작을 한다. 늦게 들어온 값이라도, 우선순위가 높으면 먼저 나오는 기능이 구현된 자료구조다. Heap은 어떻게 구현하는가? Heap은 크게 배열, 링크드리스트, 트리로 구현할 수 있다. 그렇지만 트리로 구현하는 것이 가장 좋은 것으로 알려져 있다. 위처럼 배열로 구현된 Heap이 있다고 가정해본다. 이 때, Heap에 삽입을 할 때, 자기가 들어가야 할 자리를 탐색해야하기 때문에 탐색에만 O(n) 시간이 필요하다. 중간에 삽입 시, 뒷쪽에 있는 배열들을 늘려주고 한 칸씩 이동해주어야 한다. 삭제를 할 경우, 가장 앞에 있는 인덱스를 삭제할 경우 한 칸씩 땡겨야 하기 때문..
1. 스케쥴링 - 가장 먼저 있는 것을 처리하는 경우 - 뒤에 있는 것부터 처리하는 경우 - 스케쥴이 짧은 것을 먼저 처리하는 경우 - 스케쥴이 짧고 빠르게 오는 것을 먼저 처리하는 경우.
테이블은 무엇인가? 딕셔너리는 Key, Value 형식으로 주어진 자료형을 이야기한다. 우리 주변에는 이런 형식을 아주 흔하게 찾을 수 있는데, 예를 들면 아래 표와 같은 것이다. 사번 이름 20160829 김영희 20160830 김철수 20160840 김선생 우리가 엑셀에서 흔히 보는 데이터 테이블인데, 이런 형식으로 주어지는 자료를 차곡차곡 모은 것을 딕셔너리라고 한다. 유사한 말로는 테이블, 맵이 있을 수 있다. 이런 자료구조 형식의 장점은 O(1)의 시간복잡도로 자료를 찾고, 추가할 수 있다는 점이다. 테이블은 어떻게 만들까? 기본적으로 테이블은 배열을 기반으로 구현하는 것으로 알고 있다. 배열을 기반으로 구현한다면, 당연히 배열 범위는 필요한만큼만 선언이 되어야 메모리의 최소화가 가능하다. 이런..
세그먼트 트리의 Lazy Propagation 이번 포스팅에서는 세그먼트 트리의 Lazy Propagation에 대해서 알아보겠습니다. Lazy Propagation은 구간 Query에 대한 시간 복잡도를 O(mnlogn)에서 O(nlogn) 수준으로 개선하는 방법입니다. 그 전에 세그먼트 트리 공부가 필요하신 부분은 아래 글 참고 부탁드립니다. 파이썬, 세그먼트 트리 구현 세그먼트 트리는 무엇인가? 세그먼트 트리는 완전이진트리를 기반으로 주워진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조입니다. 제가 이 자료구조를 사용해서 문제를 풀었을 때는 대부 ojt90902.tistory.com 세그먼트 트리의 단점 세그먼트 트리는 기본적으로 특정 구간 내에 쿼리를 처리할 때, logn만에 처리할 수 있는 자료..