단어 정렬 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 92851 38585 28821 40.388% 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 예제 입력 1 13 but i wont hesitate no more no more it cannot wait..
알고리즘
싱글톤(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이고 정렬된 배열이 일때 키를 알맞은 위치에 삽입한 배열은 이다.
