분류 전체보기102 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘이란? 매 순간 현재의 기준으로 최선의 답을 선택해나가는 기법 빠르게 근사치를 계산할 수 있지만 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 적용 조건 탐욕적 선택 특성 (Greedy Choice Property) 지금 선택이 다음 선택에 영향을 주지 않을 경우 최적 부분 구조 (Optimal Substructure) 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐 그리디 알고리즘 예제 Activity Selection Problem import java.util.ArrayList; import java.util.Collections; class Activity { String name; int start; int end; public Activity(String name, i.. 2022. 5. 10. Binary Search (이진 탐색) import java.util.Arrays; /** * Binary Search (이진 탐색) * 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법 * 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 * - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 * - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 * 시간 복잡도 : O(logn) * * 자바에서 기본적으로 제공하는 BT가 있다. Arrays.binarySearch(); */ public class BinarySearch { // 반복문 사용 public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - .. 2022. 4. 30. EC2 서버 접속하기 (Windows 버전) 우선 putty라는 SSH 클라이언트를 다운 받아준다. Download PuTTY: latest release (0.76) This page contains download links for the latest released version of PuTTY. Currently this is 0.76, released on 2021-07-17. When new releases come out, this page will update to contain the latest, so this is a good page to bookmark or link to. Alternativel www.chiark.greenend.org.uk 여기서 Package Files 카테고리에서 자신의 컴퓨터 환경에 맞는 파일을 다.. 2022. 4. 30. EC2 서버 만들기 EC2란? Elastic Compute Cloud의 약자 AWS에서 제공하는 클라우드 기반의 가상 서버 (클라우드 컴퓨팅) 아마존이 가지고 있는 전세계 데이터 센터의 서버용 컴퓨터들의 자원을 원격으로 사용하는 서비스 아마존에게 사용한 만큼의 비용을 지불하고 임대하는 컴퓨터 라고 간단하게 생각하면 될 것 같다. 장점으로는 용량을 늘리거나 줄일 수 있다. (탄력성) -> 오토 스케일링과 연결해서 트래픽이 몰리면 인스턴스를 자동으로 늘리고 트래픽이 줄어들면 인스턴스를 없애면 된다. 사용한만큼 지불하므로 저렴하다. -> 이 부분은 인스턴스의 성능별로 가격이 달라지기 때문에 성능좋은 인스턴스를 쓰면 비용이 기하급수적으로 늘어난다. 작은 서버 여러대로 분산처리 하는게 좋고, 고성능 연산이 필요하면 필요할 때 잠깐 .. 2022. 4. 30. 정렬 알고리즘별 복잡도 정리 2022. 4. 30. Shell Sort (셸 정렬) /** * Shell Sort(셸 정렬) * - 삽입정렬은 오름차순 정렬 기준으로 내림차순으로 이미 정렬되어 구성된 데이터에 대해서는 * - 앞의 데이터와 하나씩 비교하며 모두 교환해야한다. * - 이러한 약점을 보완하는 방식이 Shell sort * - 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교 * - 간격 설정에 따라 worst case가 O(n^2) 지만 일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다. */ public class ShellSort { public static void shellSort(int[] arr) { // 보통 간격은 배열 길이의 절반으로 시작함. int gap = arr.length / 2; // 절반씩 줄여나가면서 진행 for (int g = .. 2022. 4. 30. Counting Sort (계수 정렬) import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; /** * Counting Sort(계수 정렬) * - 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식 * - 카운팅을 위한 카운팅 테이블이 필요 * - Un-Stable sort * - 시간 복잡도 = O(n+k) (k는 정렬 대상 데이터 중 최대 값) * - * - [1,3,2,4,5] 이런 배열처럼 수의 분포가 좁다면 배열을 이용하는게 좋고 * - [1,24005,4,3] 이런식으로 수 자체는 적은데 수의 분포가 넓다면 해시맵을 이용하는게 좋다. */ public class CountingSort { /.. 2022. 4. 30. Radix Sort (기수정렬) 가장 작은 자릿수부터 정렬해나가다보면 결국에는 정렬이 되는 신기한 기수정렬 1의 자리 -> 10의 자리 -> 10의 자리 -> ,,,, 순으로 정렬을 해나가다보면 정렬이 되어있다. - 첫번째 자리수로 정렬(1의 자리) - 두번째 자리수로 정렬(10의자리) import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /** * Radix Sort(기수 정렬) * - 낮은 자리 수부터 정렬하는 방식(1의자리 -> 10의자리 -> 100의자리) * - 각 원소 간의 비교 연산을 하지 않아 빠르지만, 기수 테이블을 위한 메모리가 필요하다. * - 시간 복잡도 = O(dn) (d는 최대자릿수) * - Stable sort * - .. 2022. 4. 30. Heap Sort (힙 정렬) /** * Heap Sort(힙 정렬) * - Heap 자료구조 기반 정렬 방식 * * - 이진 tree 자료구조 성질 이용 (0번 인덱스부터 시작한다는 기준) * - 1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1 * - 2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2 * - 3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2 * - * - 장점 * - 부분 정렬을 할 때 효과적 * - 최악의 경우에도 시간 복잡도 = O(nlogn) * - * - 단점 * - 일반적인 O(nlogn) 정렬 알고리즘에 비해 성능이 조금 떨어진다. * - Stable sort 가 아니다. */ public class HeapSort { public static void heap.. 2022. 4. 30. Merge Sort(합병 정렬, 2-ways 합병 정렬) /** Merge Sort(합병정렬) - 배열을 절반으로 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식 (Divide & Conquer) - 장점 - 동일한 값의 경우, 들어온 순서대로 정렬되므로 Stable Sort 이다. - 최악의 경우에도 시간 복잡도 = O(nlogn) - 단점 - 추가적인 배열이 필요하므로 in-place Sort가 아니기 때문에 메모리 사용량이 많다. - 원본 배열에 추가적인 배열의 값을 복사하는 과정이 많은 시간을 소비하기 때문에 데이터가 많을 경우 시간이 많이 소요된다. */ public class MergeSort { public static void mergeSort(int[] arr, int[] tmp, int left, int r.. 2022. 4. 29. 빅오 표기별 커버 가능한 크기 알고리즘 별로 시간복잡도가 있는데 이 복잡도 별로 어느정도의 데이터량을 처리할 수 있는지 대략적으로 적어둔 것 이다! O(NlogN) -> 100,000 정도 O(N^2) -> 1,000 O(2^N) -> 100 이것보다 적은 시간복잡도는 언제써도 어느정도는 괜찮다고 한다. 2022. 4. 26. 이진 탐색 트리 (BST,Binary Search Tree) 규칙 왼쪽 자식 노드 한쪽으로 편향되어 있는 경우 In-order 순회를 하면 오름차순으로 된다. 탐색 (Search) 찾고자 하는 데이터를 root 노드부터 대소 비교 데이터가 작으면 왼쪽 이동 데이터가 크면 오른쪽 이동 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾더라도 최대 트리의 높이 만큼의 탐색이 이루어짐 삽입 (Insert) 균형 고려하지 않을 시 삽입할 데이터를 root 노드부터 비교 (search와 동일) leaf 노드에 도달.. 2022. 4. 25. 트리 (Tree), 이진 트리 (Binary Tree) 트리(Tree) 노드와 링크로 구성된 자료구조 Cycle이 없는 그래프의 일종 계층적 구조를 나타낼 때 사용 트리의 구조 Node : 트리 구조의 단위 Edge : 노드 간의 연결선 (= link, branch) Root Node : 부모가 없는 최상위 노드 Leaf Node : 자식이 없는 최하위 노드 (= 단말 노드) Internal Node : Leaf를 제외한 모든 노드 Parent Node Child Node Sibling Node : 같은 부모를 가지는 형제 노드 Depth : Root 에서 어떤 노드까지의 간선 수 Level : 트리의 특정 깊이를 가지는 노드 집합 Height : 트리에서 가장 큰 레벨 값 Size : 자신을 포함한 자식 노드의 개수 Degree : 각 노드가 지닌 가지의 .. 2022. 4. 24. 조합 계산 정리 조합 계산 공식 (이항계수) 조합의 점화식 점화식에 따른 재귀함수 작성 public static int cur(int n, int k) { if(n == k || k ==0) return 1; return cur(n - 1, k - 1) + cur(n - 1, k); } * 공식에 따라 n 과 k가 동일할 때와 k가 1일 때는 값이 1뿐이 안나온다. * 이러한 공식말고 쉽게 생각해보면 예를 들어 4C3이라 할 때 4개 중 3개를 고르는데 경우의 수가 4 * 3 * 2 이다(순열). 이걸 순서를 없애고자 3! 로 나눠주면 바로 답이 나온다. (4*3*2) / (3*2*1) = 4 여기서 위의 곱하는 횟수와 아래의 곱하는 횟수가 같기 때문에 같은 for 문 내에서 분자와 분모를 계산할 수 있다. public.. 2022. 4. 19. 정렬 메소드 관련 이야기 흔히 아는 정렬 메소드로는 Arrays.sort Collections.sort 이 두 개가 있다. 두개의 특징은 아래와 같다. Arrays.sort dual-pivot QuickSort 알고리즘 사용 평균 시간 : O(NlogN) 최악 시간 : O(N^2) Stable 하지 않다 Collections.sort TimeSort ( merge sort + insertion sort) 시간복잡도 : O(N) ~ O(NlogN) 보장 -> insertion의 최선 O(N) + 합병정렬의 최악 O(NlogN) Stable 하다 간혹 알고리즘 문제 풀다가 보면 Arrays.sort로 풀면 안풀리는데 Collections.sort로 풀면 풀리는 경우가 있다. 그런 경우는 테스트 케이스에 O(N^2)가 걸리도록 하는 .. 2022. 4. 18. 이전 1 2 3 4 5 6 7 다음
