해시테이블이란?

데이터의 키값을 해시함수를 이용해 인덱스화하고 배열의 해당인덱스에 데이터를 저장하는 자료구조







해시테이블 구조






해시함수는 해당 데이터를 배열의 몇번째 인덱스에 저장할 것인지 정해주는 함수이다. 이름과 연락처를 해시테이블에 저장하고 이름의 첫 번째 글자가 알파벳의 몇 번째 문자인지로 배열의 인덱스를 정하는 해시함수를 사용해보자. 예를 들어 Ann은 첫번째(index=0), Becca는 두번째(index=1)에 저장한다.




해시테이블 충돌해결 방식 (Collision Resolution)

서로 다른 데이터도 같은 인덱스값을 가질 수 있다. 예를 들어 위의 해시테이블에 Rachel의 전화번호를 삽입해보자. Rachel과 Racine 둘다 알파벳 첫글자가 r이기 때문에 인덱스 18을 가질 것이다. 이럴 경우에 충돌이 많이 발생하면 속도가 느려진다. 아무리 좋은 해시 함수라도 해시함수에 인덱스 충돌이 아예 안생기기란 거의 불가능하다(배열을 아주 크게 만들면 충돌이 거의 발생하지 않지만 당연히 메모리 낭비가 심하다 관심이 있다면 Birthday Paradox를 검색해봐라). 가장 많이 알려진 해결법 두가지를 알아 보자.




Linear Probing(선형 탐사)

데이터를 삽입할 때 해당 인덱스에 이미 데이터가 존재하면 그 다음 인덱스(+n)로 이동하는 방식이다. 위의 예시에 대입해 보자. Rachel은 원래 18번째 위치에 저장되어야 하는데 그자리에 이미 데이터가 있으므로 +1을 한다. 19번째에도 데이터가 있으므로 +1을 해주어 20번째에 저장한다. 이 상태에서 Tina의 연락처를 저장한다면 데이터는 21번째에 삽입될 것이다.






Chaining(체이닝)

체이닝은 중복된 인덱스값을 갖는 데이터들을 연결(chain)하는 것이다. 각 인덱스에 링크드리스트로 연결한다.




해시테이블 장단점


장점

데이터를 검색할 때 고유의 인덱스값으로 접근하기때문에 검색속도가 매우 빠르다.


단점

테이블내의 여유공간이 많아야 성능이 유지되기 때문에 저장공간을 상대적으로 많이 사용한다.





해시테이블 구현


아래 코드는 체이닝 해시테이블로 위의 예시를 구현한 것이다. 먼저 이름(key)과 연락처(value)를 가진 연락처(Contact) 클래스로 링크드리스트를 만든다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Contact {
    private String key;        //name
    private String value;     //phone number
    public Contact(String key, String value) {
        this.key = key;
        this.value = value;
    }
    public String getKey() {
        return key;
    }
    public void setKey(String key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}
cs




이름의 첫 문자의 알파벳 순서대로 인덱스를 지정하고 같은 알파벳 때문에 충돌이 생기면 링크드리스트의 맨 뒤에 삽입한다. 연락처 검색시에는 키값을 이용해 해당인덱스의 링크드리스트를 순서대로 탐색한다.


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
import java.util.LinkedList;
 
public class ChainingHashTable {
    
    public LinkedList<Contact>[] data;
    
    public ChainingHashTable(int size) {
        data = new LinkedList[size];
    }
 
    int getHashCode(String key) {
        int hashCode = key.charAt(0)-'a';
        return hashCode;
    }
    
    int convertToIndex(int hashCode) {
        return hashCode % 26;
    }
    
    public void put(String key, String value) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        Contact contact = new Contact(key,value);
        if(data[index] == null) {
            data[index] = new LinkedList();
        }
        data[index].addLast(contact);
    }
    
    public String get(String key) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Contact> contacts = data[index];
        for(Contact c : contacts) {
            if(c.getKey().equals(key)) {
                return c.getValue();
            }
        }
        return null;
    }
}
cs


저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

스택&큐 Stack and Queue 구현 java  (0) 2020.04.19
링크드리스트(Linked List) 구현 Java  (0) 2019.10.26



링크드리스트란?

데이터가 연속한 공간에 저장되는것이 아닌, 데이터와 다음 데이터로의 링크를 가진 노드들이 연결된 선형 데이터구조 





링크드리스트 구조




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LinkedList {
    
    Node head;
}
 
public class Node {
    
    Node next;
    String data;
    
    public Node(String data) {
        this.data = data;
    }
    
}
cs





링크드리스트 장단점


장점

배열처럼 처음부터 크기가 고정되는게 아니라 동적할당을 하기 때문에 선언시 크기를 지정하지 않아도 되어 메모리를 효율적으로 사용할 수 있다.

데이터의 추가/삭제가 용이하다.


단점

배열은 데이터를 찾을 때 인덱스로 접근하고 링크드리스트는 처음부터 순차적으로 접근한다. 그래서 k번째 데이터를 조작할 때 시간이 O(n)으로 오래 걸린다.



링크드리스트 구현


링크드리스트의 오퍼레이션들을 직접 구현해보자. 먼저 아래와 같은 링크드리스트 맨 앞에 데이터를 삽입하는것을 생각해보자.



순서는 다음과 같을 것이다.


1 노드 생성

2 1에서 만든 노드의 링크를 기존 링크드리스트의 head로 연결

3 링크드리스트의 head를 1에서 만든 노드로 변경


그림으로 보면 이해가 더 쉽다.


코드로 구현하면 다음과 같다.


1
2
3
4
5
6
7
8
9
public void addFirst(String data) {
    if(head == null) {
        head = new Node(data);
        return;
    }
    Node newHead = new Node(data);
    newHead.next = head;
    head = newHead;
}
cs



이번엔 링크드리스트의 마지막 값을 삭제해보자.


1 현재노드를 링크드리스트의 head로 지정

2 현재노드를 다음노드로 변경

3 다음노드를 가리키는 링크가 없을때까지 2를 반복

4 현재노드의 이전노드의 링크 삭제


previous : 이전노드 / current : 현재노드



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void removeLast() {
    if(head == null) {
        return;
    }
    if(head.next == null) {
        head = null;
        return;
    }
    Node current = head;
    Node previous = null;
    while(current.next != null) {
        previous = current;
    }
    current = current.next;
    previous.next = null;
}
cs




처음값 삭제, 특정 값 삭제 등도 구현해보자.


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
public class LinkedList {
    
    Node head;
    
    public void addFirst(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node newHead = new Node(data);
        newHead.next = head;
        head = newHead;
    }
    
    public void addLast(String data) {
        if(head == null) {
            head = new Node(data);
            return;
        }
        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = new Node(data);
    }
    
    public void removeFirst() {
        if(head == null) {
            return;
        }
        head = head.next;
    }
    
    public void removeLast() {
        if(head == null) {
            return;
        }
        if(head.next == null) {
            head = null;
            return;
        }
        Node current = head;
        Node previous = null;
        while(current.next != null) {
            previous = current;
        }
        current = current.next;
        previous.next = null;
    }
    
    public void removeValue(String data) {
        if(head == null) {
            return;
        }
        if(head.data.equals(data)) {
            head = head.next;
            return;
        }
        Node current = head;
        while(current.next != null) {
            if(current.next.data.equals(data)) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
}
cs


저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

스택&큐 Stack and Queue 구현 java  (0) 2020.04.19
해시테이블이란? Hash Table 구현 Java  (0) 2019.10.27



<보험 호갱 안되는법 시리즈>

· 보험 가입시 유의사항 1편(클릭)

· 보험 가입시 유의사항 2편(현재글)

· 보험 가입시 유의사항 3편(예정)



1탄에서 보험은 나에게 필요한 보장을 조합해서 설계해야 한다는 얘기를 했다. 아직 안읽었다면 위의 링크에서 보고 오시라..

보험에 가입하려고 상품을 알아보다 보면 모든 경우를 다 보장해주었으면 좋겠고 보험금도 많이 나왔으면 좋겠다는 생각을 한다. 설계사가 이 특약은 안넣으면 손해라며 부추기면 팔랑팔랑 넘어가버리기도 한다. 당연히 보장도 더 많이 해주면서 보험료도 저렴하면 좋겠지만 그런보험은 없다. 고객이 낸 보험료에 비해 자주 보험금이 지급되는 보장은 보험사 입장에서는 손해이다. 보험사는 매년 손해율을 계산하고 해당 보장의 보험료를 올리거나 없애버린다.



암보험에 암만 포함되는 게 아니라 보통 6대질병/8대질병 등으로 각종암+뇌관련+심혈관 질환에 대한 보장을 묶어서 판매한다. 이글에서는 편의상 전부 암보험이라고 칭하겠다.



2탄을 이해하기 위한 용어들을 먼저 보고 가자.


진단비 : 특정 질병에 걸렸다고 진단받으면 수술이나 치료 여부에 상관 없이 보험사가 나에게 즉시 지급해주는 보험금

수술비 : 암 진단 확정 후, 암 치료를 목적으로 수술을 받으면 지급된다

치료비 : 암 진단 확정 후, 암 치료를 목적으로 방사선,항암,약물 등의 치료를 받을 때 지급되는 금액

입원비 : 암 진단 확정 후, 암 치료를 목적으로 입원했을 때 지급되는 입원 1일당 금액

부담보 : 피보험자의 과거 병력이나 특정 질환에 대해 일정 기간 각종 보장에서 제외해 조건부로 가입하는것

청약철회 : 보험 가입 후 30일 이내에는 낸 보험료를 전액 돌려받고 취소 가능



한가지 유의해야 할점은 진단비는 내가 암이라고 진단을 받기만 하면 나오는 보험금이다. 하지만 수술비, 치료비, 입원비 등은 다르다. 극단적인 예로 암을 발견했는데 말기라서 손도 쓰지 못한채 사망했다. 그러면 받지 못하는 돈이다. 보통 '암의 직접치료 목적으로 ~하면 지급' 이런식으로 써놓는데, 암치료를 위한 목적으로 하는 수술을 받았을 경우에만 해당한다. 그리고 신기술을 이용한 수술(예를 들면 로봇을 이용한 최신 수술법)은 인정이 안되는 경우도 있다. 확실히 보험료를 받기 위해서는 암 진단금을 높이고 수술비나 치료비 입원비 등은 상황에 따라 받지 못할수도 있다는 점을 염두하자.


수술비는 암수술비 보다는 일반수술비(질병에 상관없이 수술하면 보험금 지급, 1~5종 등으로 분류) 특약을 넣는 것이 낫다.


입원비특약은 추천하지 않는다. 보통 며칠 이상 입원시 n일째부터 조건이 붙어 있는 경우도 있고 요즘은 입원을 길게 시키는 추세가 아니라 입원일당은 내가 낸 보험료에 비해 타먹을 일이 많지 않다.



그럼 암에 걸리기만 하면 진단금이 나올까? 아니다. 어떤 암들은 사망률이 매우 낮고 수술도 굉장히 간단한 경우(예:제자리암)가 있다. 이런 암들을 보험사에서는 '소액암'으로 분류한다. 갑상선암,생식기암,기타피부암,유방암 등이 여기에 해당한다. 보험사별로 소액암의 분류가 약간씩 다르다.


보험사는 아픈 고객을 싫어한다. 보험금을 지급할 확률이 높으니 당연한 이치이다. 보험 가입 전 병력이 있다면 그부분은 일정기간동안/또는 영원히 보장해주지 않는 조건으로 보험을 가입시켜 준다. 예를 들어 자궁근종으로 수술을 받은 이력이 있어 자궁 부위가 부담보로 정해졌다면 피보험자가 자궁 부위에서 질병이 발생해도 보험회사가 정한 기간(1~5년) 동안 보상받지 못하는 것이다.



보험 약관을 보면 '보험 가입후 91일 이후에 보장' 등의 문구를 보게 된다. 오늘 암보험에 가입했는데 내일 암진단을 받았다고 보험금을 받을 수 있는 건 아니다. 만일 그렇다면 사람들이 몸이 이상하다 싶으면 보험에 가입하고 병원에 갔다가 이상이 없으면 청약철회를 할 것이다.




아래는 내가 보험에 가입할 때 따르는 순서이다. 


1 암 진단금을 설정한다. 내 연봉이 실수령액으로 3000만원 정도 된다고 치자. 내가 만약에 중대한 병에 걸려서 1년동안 일을 쉬어야 한다고 치면 3000만원의 기회비용이 생긴다. 암보험이 없어도 수술하는데 든 병원비는 실비에서 어느정도 보장받을 수 있다. 하지만 1년동안 돈을 벌지 못하더라도 적금,공과금 등 소비는 멈출수가 없다. 진단금은 암에 걸렸을 때 내 생계유지를 위한 보험이다. 보통 3~5000만원 정도로 설정하고 연봉에 따라, 부양가족 여부 등에 따라 적절하게 조절하면 된다.


2 꼭 보장받아야겠다 싶은 병을 체크한다. 기본적으로 6대질병/8대질병 등으로 암·뇌·심장에 관한 보장들을 묶어서 판매하긴 하나, 그중에서 내가 가장 걱정되는 부분이 있을 것이다. 보험사별로 보장범위나 진단금이 다르다.  주로 생명보험사에서는 뇌출혈만, 손해보험사에서는 뇌혈관질환(더 넓은 범위)를 보장한다.

예를 들어 나는 직계 가족중에 유방암 진단자가 2명이나 있다. 뇌 관련질환은 한명도 없다. 그럼 나는 뇌 관련 보장이 더 넓은 보험보다는 유방암을 일반암으로 보장해주거나 유방암특약조건이 좋은 보험사를 선택할 것이다. (물론 둘다 최고로 보장해주면 좋지만 위에서 말했듯이.. 전부다 보장해주면서 보험료가 저렴한 보험은 없다^^)


3 위의 1&2에서 정한 조건을 가지고 최소 2명 이상의 설계사와 상담한다. 친구나 직장 동료에게 보험 들었으면 설계사 소개시켜달라고 하면 시켜준다. 한명의 설계사에게 상담받고 바로 가입하지는 말자. 적어도 2명 이상은 상담해보자.



만약에 보험이 아예 없는데 암에 걸렸다. 그러면 돈이 없어 치료로 못 하는가??


아니다. 정부에서 일정부분 의료비를 지원해준다. 자세한 내용은 아래 링크에서 확인 해라.

http://www.ncc.re.kr/main.ncc?uri=manage01_5





이 포스팅이 도움이 되었다면 아래 공감♡ 버튼을 누르자.

저작자표시 비영리 변경금지

'꿀팁뿌시기' 카테고리의 다른 글

핸드폰 싸게사는법 2편 - 자급제폰과 알뜰요금제  (0) 2020.05.11
직장인 연말정산 하는 이유  (0) 2020.03.29
보험 가입시 유의사항 1편 - 보험 호갱 안되는법  (4) 2019.05.26
핸드폰 싸게사는법 호갱 안당하는법 - 1편  (9) 2019.05.07

+ Recent posts

티스토리툴바