Study-Note

원소간 비교하지 않고 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방법. 모든 원소는 양의 정수여야 한다. 시간복잡도는 O(n+k) 로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다. 정렬을 위한 길이 n의 배열 하나, 계수를 위한 길이 k의 배열 하나. 총 2개의 별도 배열을 필요로한다. O(n+k) 의 공간복잡도를 가진다. * 카운팅 정렬 단계 배열 안에 있는 원소 종류만큼의 새로운 배열을 생성하고 0으로 초기회시킨다. 만약 배열에 [0, 1, 3, 1, 3]이 있다면 0~3 크기의 배열 생성 각 원소의 갯수를 계산하여 배열 안에 담는다 0은 1개이므로 c[0]=1, 1은 2개이므로 c[1] = 2, 2는 존재하지 않으므로 0 누적합을 이용하여 계산한다. (배열에 값이 들어갈 위치를 선정하는 것) 따..

(1) 힙정렬 * 힙(heap) 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조 * 완전이진트리 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리 * 힙의 종류 부모노드의 키값이 자식노드의 키값보다 항상 큰 '최대 힙' 부모노드의 키값이 자식노드의 키값보다 항상 작은 '최소 힙' * 완전이진트리 배열로 구현하기 한 노드를 알면 그 노드의 부모, 자식들을 인덱스로 바로 접근 가능 노드 i의 부모 노드 인덱스 : i/2, (단, i > 1) 노드 i의 왼쪽 자식 노드 인덱스 : 2 x i 노드 i의 오른쪽 자식 노드 인덱스 : (2 x i) + 1 * 최대힙에서 힙 정렬하기 최대힙 직계관계에서는 무조건 부모는 자식(..

순환 = 재귀 자기 자신을 호출하는 함수 = 재귀함수 = 순환 * 예시 int main() { int result = func(4); } int func(int n) { if (n==0) return 0; else return n + func(n-1); } 1~n까지의 합을 구한다. 무한루프에 빠지지 않으려먼 조건(base case)을 걸어주어야 함. 하지만 base case가 있다고 하여 모든 재귀함수가 종료되는 것은 아님. => recursion을 반복하다보면 결국 base case로 수렴해야 한다. (이 조건을 함께 만족해야 무한루프에 빠지지 않는다.) return하여 재귀를 빠져나오게 되면 마지막으로 실행했던 문장으로 돌아간다. int func(int n) { if (n0) int factoria..

알고리즘의 분석 - 시간복잡도 알고리즘을 어떻게 평가 할 것인가? 어떠한 자료구조, 알고리즘이 적합한 것인가를 판단하기 위해 필요한 기준과 방법론 * 알고리즘의 분석, 좋은 알고리즘이란 무엇인가? - 알고리즘의 자원(resource) 사용량을 분석 (보편적) - 자원이란 실행 시간, 메모리, 저장장치, 통신 등 - 여기서는 실행시간의 분석에 대해서 다룸 * 시간복잡도(time complexity) - 실행시간은 실행환경에 따라 달라짐 (하드웨어, 운영체제, 언어, 컴파일러 등) - 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 => 어떠한 환경에서 실행하더라도 동일 - 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 => n에 관한 함수로 - 데이터의 크기가 같더라도 실제 데이터에 따라..

문자열 함수 정리하기 - valueOf(number) 해당 number를 String으로 변환하여 반환 String.valueOf(number); - length() 문자열의 길이를 반환 - charAt(index) 해당 문자열의 index에 위치한 문자를 char형으로 반환 - startWith() 문자열이 지정한 문자로 시작하는지 판단 (대소문자 구분) 같으면 true 다르면 false String str = "apple"; boolean startsWith = str.startsWith("a"); //true - equals() String값을 비교해서 같으면 true, 다르면 false 반환 - indexOf() 문자가 문자열 어디에 위치하는지 index 값 반환 (0부터 시작) String st..

Math 정리 기본 수학적 함수들을 제공하는 클래스이다. 대부분 실수형(double)을 반환함에 주의 - abs 절대값 반환 (int 반환) Math.abs(-4) //4 - ceil 올림 수 반환 Math.ceil(55.5) //56.0 Math.ceil(55.3) //56.0 - floor 소수점 버림 Math.floor(55.5) //55.0 Math.floor(55.3) //55.0 - round 반올림값 반환 Math.round(55.5) //56.0 - exp(x) 승 된 값을 반환(x를 인수로 하는 e^x 값을 반환) - pow(x, y) 누승한 값을 반환, x의 y승 - sqrt(x) x의 제곱근, 루트 - min(x, y) 작은 수 반환 - static int min(int a , int..