싱글톤(Singleton) 패턴 이란? 싱글톤 패턴이란 클래스가 최초 인스턴스화 할때에 한번만 메모리에 객체를 생성하고 이 객체를 사용하는 디자인 패턴이다. 즉 클래스를 여러번 인스턴스화 하더라도 새로운 객체를 생성하는것이 아닌 기존의 객체를 공유한다. 싱글톤(Singleton) 사용 이유? 위에 설명한것과 같이 한번만 객체를 생성하기 때문에 메모리 낭비를 방지할 수 있다. 또한 한번만 생성된 객체는 전역성을 띄기 때문에 공유가 용의하다. 싱글톤(Singleton) 문제 싱글톤의 전역성은 장점인 동시에 단점으로 작용된다. 몇가지 케이스에서는 객체를 공유한다는것이 큰 장점으로 작용하지만 다른 객체관의 결합도가 높아져 객체 지향 설계 원칙에 어긋난다. 또한 사이드 이팩트, 멀티 쓰래드 환경에서 동기화 처리 ..
알고리즘
지금 까지 했던 merge 퀵, 선택, 삽입, 흡 등 비교 정렬은 아무리 빨리도 nlogn의 수행시간이 나온다. 계수 정렬 알고리즘은 카운트 베열이 필요하다. 무슨 숫자가 몇개 있는지 확인 하기 위해 계수 정렬의 특징 - 입력 후에도 배열이 유지된다. 기수정렬
Dicide-and-Conquer qaradigm을 사용 즉 풀기 어려운 정렬을 계산하기 쉽게 나누어 진행하는것 partition을 이용 Pivot을 정해서 작은것은 왼쪽 큰것은 오른쪽으로 위치시킨다. 재귀호출을 통해 계속 반복한는것 퀵 정렬의 수행시간은 Pivot을 어떨게 설정하냐에 따라 달라진다. Merge sort 는 nlogn이지만 공간은 사용해야 한다는 단점이 있다. HeapSort는 max-heap구조를 만들어야 한다는 어려움이 있다. Quicksort는 nlogn이지만 최악의 경우 시간이 많이 늘어난다.
힙 정정 (Heap Sort) - 힙 구조의 특성을 이용한 정렬 - 수행시간은 합병정렬과 동일한 O(nlon) - 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙의 형태 (The chape of a heap) - 완전 이진 트리(Complete binary tree)에 가까운 형태 (트리는 부모노드와 자식 노드로 구성되어있는 그래프) - 이진트리(Binary tree)는 각 노드의 자식수가 2 이하인 경우 - 완전 이진트리는 Root노드부터 Leaf노드까지 빠짐없이 채워져 있는 트리 최대힙 특성 (Max-Heap Property) - 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다. - 따라서 전체 트리의 Root 노드값이 가장크다. - 또한 각 하위 트리 구조의 Root 노드가 가..
정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명할 수 있다. 문제정의, 알고리즘 설명, 정확성 증명, 성능 분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3......... an) - 출력 (output) 입력된 숫자 위 배열이 오름차순 조건을 만족하도록 재 배열하는 것 합병 정렬(Merge Sort) - 합병을 이용한 정렬 알고리즘 - 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병 - 각 배열의 가장 왼쪽에 있는 값을 비교해보면 가장 작은 수를 알 수 있다. 정렬을 하기에는 너무 큰 배열을 쪼개어 정렬한 후 합병한다. 이를 위해 합병 정렬을 필요한 것이다. A divide-and-conquer approach 크기가 커서 풀기 어려운 하나의..
정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 선택정렬 알고리즘 선택정렬(Selection sort) - 선택하여 정렬하는 알고리즘 - 최소값 선택 정렬 (Min-Selection sort) 가장 작은 값을 선택(오름차순) - 최대값 선택 정렬 (Max-Selection sort) 가장 큰 값을 선택(내림차순) - 정확성 증명 수학적 귀납법을 이용 i번쨰 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명 - 성능분석 최선 최악의 경우 수행..
정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 삽입정렬(Insertion sort) - 삽입을 이용한 정렬 알고리즘 Key 값과 정렬된 리스트가 주어졌을 때 , Key 값을 정렬된 리스트의 알맞는 위치에 삽입 Key가 3이고 정렬된 배열이 일때 키를 알맞은 위치에 삽입한 배열은 이다.
선택정렬 가장 작은 값은 찾는다. (첫 번째 값과 두 번째 값을 비교해서 작은 값을 찾고 그 값과 3번째 값과 또 비교하고 이렇게 차례차례 비교해서 가장 앞에 가장 작은 수를 넣는다.) 무조건 모든 것을 비교해 봐야 한다. 즉 최선과 최악의 경우의 수행 시간이 같음 따라서 선택 정렬은 전체의 배열에서 최솟값을 찾아 맨 앞에 위치시키고 인덱스를 하나씩 증가시켜 그다음 작은 값을 위치시킨다. - 최선 최악 경우 시간 : 무조건 n^2 삽입 정렬 - 삽입을 이용한 정렬 알고리즘 - Key 값과 정렬된 리스트가 주어졌을 때, Key값을 정렬된 리스트에 알맞은 위치에 삽입 key 값을 정렬된 배열에 넣으면서 정렬 배열을 하나씩 늘려가는 정렬 방식 최선과 최악의 경우가 다르다. for문 2개가 아닌 while 문을..
