우선 approxmiate median 에 대해 알아보기 전에, Quick Sort에 대해 간단히 짚어보자. Quick Sort 저번 포스팅에서 Quick Sort의 평균 시간복잡도가 왜 O(nlogn) 인지 증명해보았다. 시간복잡도 Average : O(nlogn) Worst : O(n^2) 피벗이 중간에 위치해 있다 -> Best Case 피벗이 한쪽 방향으로 계속 쏠려있다. -> Worst Case 정말 운이 안 좋게도 재귀적으로 따라 들어갈 때마다 pivot 이 한쪽 끝이라면 시간복잡도가 O(n^2) 이다. Quick Sort를 쓰는 의미가 없음. 시간복잡도 (최악의 경우) T(n) = n + T(n-1) T(n) = O(n^2) 이렇게 pivot의 위치에 따라 성능에 크나큰 차이가 발생한다. 따..

MergeSort 알고리즘의 시간 복잡도는 O(NlogN) 이다. MergeSort는 매우 준수한 정렬 알고리즘이지만 추가적인 배열 하나가 더 필요하기 때문에 memory allocation이 일어난다. 그리고 새로운 메모리를 할당하는 과정은 꽤 비싸다. 이번 포스팅에서는 퀵정렬에 대해 알아보고, 시간복잡도에 대한 증명도 하고자 한다. Quick Sort 대표적인 divide & conquer 알고리즘. 평균 시간복잡도: O(NlogN) 인 아주 훌륭한 알고리즘이다. 퀵 정렬은 조금 특이한 특징을 가지고 있는데, 바로 피벗(Pivot)을 사용한다는 점이다. 대략적인 소스코드는 다음과 같다. int qsort(int a[], int n){ // pivot int p = a[0]; int i = 1; int..

앞서 최단거리 알고리즘으로 Prim, Kruskal 을 다뤄보았다. 이번 포스팅에서 다룰 Shortest Path 알고리즘은 다익스트라(dijkstra)이다. 다익스트라 알고리즘이 왜 정확한지 정확성 증명을 해보고, 코드로 구현을 해보겠다. Dijkstra Algorithm 정확성 증명 Source 노드에서 시작 각 노드에 적힌 숫자는 source 노드와의 최단거리를 나타낸다. 정답을 찾아가면서 이 노드들의 숫자를 update 하면 된다. 다익스트라의 특징 모든 노드에서 시작점까지의 최단 거리를 구할 수 있다. 단순히 거리만 구하는 것이 아니라, 지나온 경로도 알 수 있다. (백 트래킹) 진행 방법 위처럼 노드들이 있고, 노드마다 적힌 숫자는 시작 노드와의 최단거리를 나타낸다. 빨간 영역은 알고리즘에 의..

스프링 컨테이너 스프링 컨테이너를 이용해 객체를 스프링 빈으로 등록하고 컨테이너에서 스프링 빈을 찾아 사용할 수 있다. 스프링 컨테이너는 다음과 같은 이점을 제공해줌으로써 개발자가 객체 지향적인 개발을 할 수 있게 도와준다. 의존관계 주입 (DI) 컨테이너가 의존관계를 자동으로 주입 제어의 역전 (IoC) 객체는 자신의 로직만 실행하고 프로그램의 제어흐름을 외부(스프링 컨테이너) 에서 실행. 싱글톤 패턴 객체를 빈으로 등록해 찾아 사용할 수 있어 싱글톤 패턴을 보장해준다. 스프링 컨테이너를 만드는 방법 1) XML 기반으로 생성 XML 파일에 beans 태그로 설정, bean 태그를 이용해 스프링 빈을 등록할 수 있다. bean 태그의 속성값인 id로 빈 이름, class 로 구현 클래스를 지정해줄 수 ..

싱글톤 패턴이란? 클래스의 인스턴스가 한개만 생성되는 것을 보장하는 디자인 패턴. 생성자가 여러 차례 호출되더라도 실제로 생성되는 객체는 하나이고, 최초 생성 이후에 호출된 생성자는 최초의 생성자가 생성한 객체를 리턴한다. 싱글톤 패턴은 같은 클래스의 인스턴스를 한개만 생성되게 하는 패턴이다. 말 그대로 같은 타입의 생성자가 여러차례 호출돼도 원래 생성되어있던 동일한 객체만이 리턴된다. 프로그램 내에 하나의 객체만 존재해야 할 때나, 프로그램 내에 해당 객체를 공유하며 사용해야 할 때 필요하다. 스프링 컨테이너 스프링 컨테이너(DI, IoC 컨테이너)는 객체 인스턴스를 싱글톤으로 관리해준다. 컨테이너는 @Bean이 붙은 어노테이션을 스프링 빈으로 관리한다. 이는 싱글톤으로 관리된다. Application..

Shortest Path 를 찾는 알고리즘으로 Prim 알고리즘을 살펴보았다. prim 은 그리디 알고리즘으로, MST(최소 신장 트리)를 만들기 위해 힙, 즉 우선순위큐를 사용했다. 두 정점 사이의 edge 거리가 작은 것 우선순위가 높도록 정했다. 이번 포스팅에서 다룰 Kruskal 알고리즘도 Shortest path를 찾는 문제다. 연결 그래프가 주어지고 MST를 구하면 되는 문제이다. Prim 알고리즘과 목적이 같지만, 구현 방법에 약간의 차이가 있다. Prim 알고리즘 포스팅: https://matt1235.tistory.com/51 문제) 다음과 같은 연결그래프가 있다. 모든 정점을 연결하는 Minimum Spanning Tree를 구하라. Prim 알고리즘은 T라는 해집합을 점차 늘려나가는 ..