끵뀐꿩긘의 여러가지

◎해시(hash)란 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다. 해시값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)으로 검색과 저장이 매우 빠르다. (검색할 때 사용하는 값(key)이 해시함수에 의해서 배열의 인덱스로 바로 변환되기 때문에 그 인덱스의 값(value)을 아주 빠르게 찾을 수 있다.) ◎해싱(hashing), 해시함수(hash function), 해시 알고리즘, 해시 코드(hashcode), 해시 테이블(hashtable) 키에 대한 hashcode값을 구하는 과정을 hashing이라고 하며 이때 사용하는 함수(알고리즘)를 hashfunction라고 한다. 구한 hashcode값을 hashtable이라는 배열에 저장..

◎ 순열(permutation)이란 서로다른 n 개의 값 중에서 r 개의 숫자를 선택 후 나열하는 것이다. ex) [1,2,3,4]인 4개의 원소로 이루어진 배열에서, 2개의 숫자를 뽑아 나열하는 경우는 (1,2)(1,3)(1,4)(2,1)(2,3)(2,4)(3,1)(3,2)(3,4)(4,1)(4,2)(4,3) 로 12개이다. ◎ 순열의 알고리즘적 구현 1 - swap을 이용한 구현 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap한다. depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고 depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행합니다. 한 줄씩 내려갈때마다 새로운 재귀함수로 들어간것이고 새로운 재귀함수에 들어갈 때마다 dept..

◎소수의 정의 소수는 자신보다 작은 1 이상의 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ex) 17은 17보다 작은 1이상의 두 개의 자연수를 곱하여 만들 수 없는 수이므로, 소수이다. => 즉, 1과 자신만을 약수로 갖는 수이다. ◎소수 판별 알고리즘 1 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 안 나온다면 소수로 정의 public class Main { public static boolean isPrime(int num){ //num>3 for(int i=2; i3인 자연수) N의 약수가 가질 수 있는 최솟값이 2이므로, N의 약수가 가질 수 있는 최댓값은 N/2이다. 그러므로, 2~N/2까지 중에 num의 약수가 있는지 판별하면 된다. 시간복잡도: Olog(N/2) p..

Set이란? 우리에게 익숙한 List처럼 데이터를 저장하는 자료형 중 하나이다. set의 특징: - 요소의 저장 순서를 유지하지 않는다 - 같은 요소의 중복 저장을 허용하지 않는다 set을 구현한 클래스: HashSet: 데이터를 해쉬 테이블에 담는 클래스, 순서가 정해지지 않는다. TreeSet: red-black이라는 트리에 데이터가 담아지며, 값에 따라서 순서가 정해진다. HashSet보다 성능상 느리다. LinkedHashSet: 해쉬 테이블에 데이터를 담는데, 저장된 순서에 따라서 순서가 결정된다. ※Hash 테이블과 red-black트리는 나중에 포스팅하면, 링크를 첨부하겠습니다. HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다. HashS..

String은 불변(immutable)하기 때문에 값을 변경할 수 없다. 그러므로, .concat이나 +연산을 할 때 기존의 값을 버리고 새로 값을 할당하는 과정을 거친다. 이러한 과정이 반복적으로 일어나면, 속도저하가 심각해진다. String str = new String("hello"); // String 참조변소 str이 "hello"라는 메모리 영역을 가리킴 str = str + " world"; //String 참조변수 str이 "hello world"라는 새로 생긴 메모리 영역을 가리키도록 바뀜 //"hello"가 저장된 메모리 영역은 그대로 있다가 Garbage Collection에 의해 삭제됨 String 클래스는 불변하기 때문에 문자열을 수정하는 시점에 새로운 String 인스턴스가 생성..