내국인근로자 (정보통신업)

 좋은 해쉬 함수는     - 현실에서는 키들이 랜덤하지 않다.     - 만약 키들의 통계적 분포에 대해 알고 있다면, 이를 이용하여 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어렵다.     - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 것이 바람직하다     -> 예시로 사람 이름이 Z로 시작하는 사람이 적고 A로 시작하는 사람이 많은 것 처럼     : 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 한다. 해쉬함수 Division 기법 h(k) = k mod m (사실 모든 해쉬함수들이 마지막에 하는 일 -> 마지막에 변환하는 일) ex) m = 20 and k = 91 -> h(k) = 11 장점 : 한번의 mod연산으로 계산, 따라서 빠름 단점 : 어떤 m 값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p 이면 키의 하위 p비트가 해쉬 함수값이 된다. 보통 이 전 단계에서 복잡한 과정을 거쳐서 마지막 과정에 division 기법 적용해서 사용하는데, 이전 단계에서 Multiplication 기법이나 기타등등을 통해서 사용 - 0에서 1 사이의 상수 A를 선택 : 0<A<1 (소수) - kA의 소수 부분만을 택한다 - 소수 부분에 m을 곱한 후 소수점 아래를 버린다. Hash code in Java - java의 Object 클래스는 hashCode() 메서드를 가진다. 따라서 모든 클래스는 hashcode()메소드를 상속받는다. 이 메소드는 하나의 32비트 정수를 반환한다. x.equals(y)이면 x.hashcode()==y.hashcode()이다. 하지만 역은 성립하지 않는다. Object 클래스의 hashCode()메소드는 객체의 메모리 주소를 반환하는 것으로 알려져 있다. 필요에 따라 각 클래스마다 이 메소드를 ov...

아웃룩 기본 설정 시 리본 메뉴에서 파일 탭이 없을 때 설정을 찾는 것이 아니다. 여기서 보면 우측 상단 위쪽의 이 버튼이 있다. [ ... ] 옆의 저 접기 버튼을 눌러서 리본 메뉴를 펴면 된다. 그러면 폴더 탭이 활성화되어 정상 사용 가능하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import  org.json.simple.JSONObject; import  org.json.simple.parser.JSONParser; import  org.json.simple.parser.ParseException;   public   class  jsonSample {               public   static   void  main( String [] args) {                String  jsonString  =                        "{"                      +   "    \"resultcode\":\"200\","                      +   "...

 Open Addressing에 의한 충돌 해결      - 모든 키를 해쉬 테이블 자체에 저장      - 테이블의 각 칸(slot)에는 1개의 키만 저장           ㄴ 충돌이 생기면 다른 slot에 저장해야 한다.      - 충돌 해결 기법          : linear probing (기본적인 해결책)          : Quadratic probing          : Double hashing Linear Probing - probing은 먼저 해싱을 해서 그 칸이 비어 있으면 저장하고, 이미 다른 키에 의해 차 있을때 순서대로 검사를 해서 빈 슬롯에 저장하는 기법이다. h(k), h(k)+1, h(k)+2,... 순서로 검사하여 처음으로 빈 슬롯에 저장 테이블의 끝에 도달하면 다시 처음으로 circular 하게 돌아감 찾을 때도 자리 가서 보고 없으면 다시 순서대로 검사를 해야 한다. 이 Linear Probing의 단점은 clustering인데, 키들이 연속해서 뭉쳐져 있는 현상을 말한다. 그러면 cluster의 끝에 더덕더덕 붙을 확률이 커져서 cluster가 눈덩이처럼 길게 늘어나는 현상이 생길 수 있다. 그러면 cluster에 길이에 비례하여 속도가 저하되고, 원래 있어야 할 위치보다 멀리 저장되기 때문에 속도도 저하되고 cluster가 점점 커져서 더 느려지고 하는 현상이 발생한다. primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미 Quadratic probing     : 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2 + h(k)+3^2 ... 순서로 시도한다.     - 리니어와 비슷하...

Https랑 Http랑 사용 하는 방식은 같은데 URL에 따라 사용 하면 된다. GET이랑 POST도 어짜피 동일해서 HttpURLConnection 만 GET 예제 만들었음. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 import  java.io.BufferedReader; import  java.io.DataOutputStream; import  java.io.IOException; import  java.io.InputStreamReader; import  java.net.HttpURLConnection; import  java.net.MalformedURLException; import  java.net.URL; import  java.nio.charset.Charset;   import  javax.net.ssl.HttpsURLConnecti...

 Hashing Hash Table - 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법의 하나 : 적절한 가정하에서 평균 탐색, 삽입, 삭제시간 O(1) : 보통 최악의 경우 O(n) -> Red-Black 에서는 O(logN) 이었었음... - Hash 함수 h를 사용하여 키 k 를 T[h(k)] 에 저장 h : U -> {0,1...m-1}, 여기서 m은 테이블의 크기, U는 모든 가능한 키(양의 정수)들의 집합 - 키 k가 h(k)로 해슁되었다고 말함. 해쉬테이블은 일반적으로 하나의 배열 index = h(k) k는 그냥 하나의 키 : 각 키에 대한 해쉬함수값을 그 키를 저장할 배열 인덱스로 사용한다. 해쉬 함수의 예 - 모든 키들을 자연수라고 가정. (어떤 데이터든지 자연수로 해석하는 것이 가능) - 예 : 문자열 ASCII 코드 : C=67, L=76, R=82, S=83 문자열 CLRS는 (67 * 128^3) + (76+128^2) + (82*128^1) + (83*128^0) = 141764947 해쉬 함수의 간단한 예 : : h(k) = k%m  - 즉 key를 하나의 자연수로 해석한 후 테이블의 크기 m 으로 나눈 나머지 - 항상 0~m-1 사이의 정수가 됨 충돌 (collision) - 두 개 이상의 키가 동일한 위치로 해싱되는 경우 - 즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2) 인 상황 - 일반적으로 |U| >> m 이므로 항상 발생 가능 (즉 단사함수가 아님) ㄴ 단사함수는 매칭 되는게 일대일인 함수를 뜻함.  정의역의 서로 다른 원소를 공역의 서로 다른 원소로 대응시키는 함수다. -만약 |k|>m이라면 당연히 발생, 여기서 k는 실제로 저장된 키들의 집합 - 충돌이 발생할 경우 대처 방법이 필요 - 대표적인 두 가지 충돌 해결 방법 : chaining 과 open addressing chaining에 의한 충돌 해결 방법 : 동일한 장소로 해슁된...

DELETE - 보통의 BST 에서처럼 DELETE 한다. - 실제로 삭제된 노드 y가 red면 종료. - y가 black이었을 경우 RB-DELETE-FIXUP 을 호출한다. * 수도 코드내 삭제되는 x는 y가 자식이 있었을 경우 그 자식노드로 대치,  없었을 경우 NIL 노드로 대치 RB-DELETE-FIXUP(T,x) x가 NIL 노드일 수도 있다. 그리고 x가 red일 경우 쉽게 해결할 수 있다. 이 두가지를 기억한다. 실제로 DELETE에서 문제는 x가 BLACK인 경우다. 각 노드는 red 혹은 black이다. : 문제 없음. 루트노드는 black이다. y가 루트였고, x가 red인 경우 위반된다. 하지만, 심각한 문제는 아니다. 모든 리프노드(즉, NIL 노드)는 black이다. : 문제 없음 red노드의 자식노드들은 전부 black이다.(즉, red노드는 연속되어 등장하지 않고) p[y]와 x가 모두 red일 경우 위반 x가 레드인 경우 red를 black으로 바꾸어 주면 되기 때문에 심각한 문제는 아니다. 모든 노드에 대해서 그 노드로 부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다. 원래 y를 포함했던 모든 경로는 이제 black노드가 하나 부족하다. 노드 x에 "extra black"을 부여해서 일단 조건5를 만족시킨다. 색을 두개 가지고 있게 하는 임시 방법이다. 그렇게 되면 노드 x는 "double black" 혹은 "red & black"이 된다. 앞으로 해결해야하는 문제가 이 것을 블랙노드로 바꾸는 것이다. 수정 아이디어 - extra black 을 트리위쪽으로 올려보낸다. - x가 red&black 상태가 되면 black 처리하고 끝냄 - x가 루트가 되면 그냥 extra black을 제거 Loop Invariant - x는 루트가 아닌 double-black 노드 - w는 x의 형제노드 - w는 NIL 노드가 될 수 없음 ---...