hodubab

해슁/해싱 Hashing key K를 해시함수값인 h(K)의 위치에 저장하는 자료구조. Direct-Address 테이블에서의 공간 낭비를 줄이면서도, 시간복잡도를 낮추기 위해서 사용하지만 충돌문제가 있으며 이를 해결하기 위한 Chained Hash Table은 시간이 느려질 수 있음. 충돌 다른 Key K인데 해시함수값인 h(K)가 동일한 경우 체인을 이용한 충돌 해결법 중복되는 Key값이 있을 경우 해당 슬롯을 연결리스트로 저장한다. 수행시간 최악의 경우 : O(N) - 모든 Key 값 K가 하나의 해쉬함수 값를 갖는 경우 - 모든 Key 값이 하나의 연결리스트에 저장된 경우 평균의 경우 : O(1+a) - a는 적재율 = 윈소의 개수 / 슬롯(버킷)의 개수 좋은 해쉬 함수란? key가 중복없이 m개..

계수정렬(Counting Sort) 1. 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. 가장 작은 원소와 가장 큰 원소를 구한다. 가장 작은 원소부터 가장 큰 원소까지의 실제 숫자를 key(index)로 가지는 배열을 만든다. 배열에서 실제 숫자의 갯수를 센다. 2. 갯수를 하나씩 줄여가면서 해당 위치에 요소를 넣어준다. 의사코드 수행시간 O(N+K) * k는 입력되는 정수의 범위이다. 계수정렬이 유리한 경우 동일한 숫자가 반복되고, MIN과 MAX 값의 범위가 적을 때 JAVA package algorithm; import java.util.Arrays; public class CountingSort { public int[] countingSort(int[] arr, int min, int..

파티셔닝을 이용한 정렬방법 1. 기준값을 정한다. 2. 첫번째부터 차례로 비교해나가면서 기준값보다 작으면 왼쪽 그룹의 끝자리+1과 위치를 바꾼다. 퀵 정렬의 수도코드 수행시간 Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우 => 높이 logN * 각 층별 N번의 연산을 수행 => O(NlogN) UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우 => 높이 N-1 * 각 층별 N-1번의 연산을 수행 => O(N²) * Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는 Randomized QuickSort가 등장함. JAVA package algorithm; import ..

힙의 형태 완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리 최대힙 Max-Heap 부모 노드 > 자식 노드 Root 노트의 값이 가장 크다. 최소힙 Min-Heap 부모 노드 < 자식 노드 Root 노드의 값이 가장 작다. 힙 배열 저장 방식 Root 노드는 배열의 첫 번째에 저장 각 노드들은 레벨 별로 저장 ▶ 부모 : 현재위치 / 2 ▶ 왼쪽 자식 : 현재위치*2 ▶ 오른쪽 자식 : 현재위치 *2+1 힙의 높이 O(logN) 힙 특성관리 Max-Heapify 노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산 입력값이 흘러내리게 함. 수행시간 : O(logN) 힙 구조 만들기 입력받은 트리에 Max-Heapif..

합병정렬이란? 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병 ⓛ 배열 A의 첫번째 값과 B의 첫번째 값을 비교 ② 비교한 값 중 작은 값을 반환할 배열C에 입력 ③ 배열 C에 넣은 값 다음 값과, 나머지 값을 비교 > 1,2를 반복 사용법 ⓛ 입력된 배열을 나누기 ② 나눠진 배열을 정렬 ③ 배열을 합치기 (합병정렬 사용) 수행시간 O(nlogn) public class MergeSort { static int[] arr; static int[] tmp; public void mergeSort(int start, int end) { if(start

삽입 정렬이란? Key 값과 정렬된 리스트가 주어졌을때, Key값을 정렬된 리스트의 알맞은 위치에 삽입 Key 값을 하나씩 추가하면서 정렬. ① i 위치의 값을 0~(i-1) 위치까지의 값과 비교하여 i위치의 값이 들어갈 위치를 찾음. ② i 위치의 값을 찾은 자리에 삽입 수행시간 최선의 경우 : 0 ~ i-1 배열이 이미 정렬된 경우 > 비교를 1번만 하면 됨 >> n-1 최악의 경우 : 0 ~ i-1 배열이 반대로 정렬된 경우 > 모든 배열 값과 다 비교해야 함. >> n(n-1) 빅오표기 : O(n²) 내가 구현한 소스 (JAVA) public int[] sort(int[] arr) { List list = Arrays.stream(arr).boxed().collect(Collectors.toLis..

선택정렬의 종류 ① 최소값 선택 정렬 (오름차순) ② 최대값 선택 정렬 (내림차순) 최소값 선택 정렬 (오름차순) 1. 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다. 2. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 3. 모든 숫자를 옮길 때까지 반복한다. 최대값 선택 정렬(내림차순) 1. 정렬되지 않은 숫자 중 가장 큰 숫자를 선택한다. 2. 선택한 가장 큰 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 3. 모든 숫자를 옮길 때까지 반복한다. 정확성 증명 i번째 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명 성능분석 n개가 있을 때 가장 큰/작은 수를 구하기 위해서 n-1 번의 비교가 일어남. => n(n-1) / 2 O(n²) 내가..

알고리즘이란 ? 주어진 문제를 효율적으로 풀기위한 방법을 단계별로 기술해놓은 것. 알고리즘 설명 4단계 ① Problem definition (문제 정의) ② Algorithm description (알고리즘 설명) ③ Correctness proof (정확성 증명) ④ Performance Analysis (성능분석) - Running Time (수행시간) - Space Consumption (사용공간) 수행시간 분석 수행연산의 횟수를 비교하는 방식 입력 크기 n에 대한 함수로 표현 : T(n) 성능 분석의 비교대상 산술연산 (Arithmetic Calculation) : Add, Multiply, Exponent, Modular 데이터 입출력 (Data Movement) : Copy, Move, Sa..

1. 십진수 > 이진수 : toBinnaryString 사용 long number = 123; String longbi = Long.toBinaryString(number); int number = 123; String intbi = Integer.toBinaryString(number); ----------------------- 결과값 1111011 2. 십진수 > 이진수 : 함수 구현 String bi =""; int number = 123; while(number>0) { bi = number%2+bi; number /=2; } System.out.println(bi); -------------- 결과값 : 1111011 3. 이진수 > 십진수 : Integer.parseInt, Long.pars..

1. Arrays.sort 사용하기 숫자 > 대문자 > 소문자 순으로 오름차순 정렬 import java.util.Arrays; char[] arr = {'c', 'D', 'e','F','a','B', '1', '0', '3'}; Arrays.sort(arr); System.out.println(arr); --------------------------------- 출력값 : 013BDFace