React Life Cycle

 

컴포넌트 초기 생성

컴포넌트가 브라우저에 나타나기 전,후에 호출되는 API

 

constructor

constructor(props){
  super(props);
}

컴포넌트가 새로 만들어질때 마다 이 함수가 호출 된다.

 

componentWillMount

componentWillMount(){
  
}

컴포넌트가 화면에 나타나기 직전에 호출되는 API. 현재는 사라짐.(v16.3)

 

componentDidMount

componentDidMount(){
  
}

컴포넌트가 화면에 나타나게 됐을때 호출되는 API.

 

 


컴포넌트 업데이트

props의 변화, state의 변화에 따라 결정.

 

componentWillReceiveProps

componentWillReceiveProps(nextProps){
	//this.props는 아직 바뀌지 않은 상태
}

컴포넌트가 새로운 props를 받게 됐을 때 호출된다.

주로, state가 props에 따라 변해야 하는 로직을 작성.

 

static getDerivedStateFromProps()

이 함수는, v16.3 이후에 만들어진 라이프사이클 API이다.

props로 받아온 값을 state로 동기화하는 작업을 해줘야 하는 경우에 사용.

static getDerivedStateFromProps(nextProps, prevState){
  // 여기서는 setState 를 하는 것이 아니라
  // 특정 props 가 바뀔 때 설정하고 싶은 state 값을 리턴하는 형태로
  // 사용됩니다.
  /*
  if (nextProps.value !== prevState.value) {
    return { value: nextProps.value };
  }
  return null; // null 을 리턴하면 따로 업데이트 할 것은 없다라는 의미
  */
}

 

shouldComponentUpdate

shouldComponentUpdate(nextProps, nextState){
  // return false 하면 업데이트를 안함
  // return this.props.checked !== nextProps.checked
  return true;
}

Virtual DOM에 불필요한 리렌더링을 방지하기 위해 작성.

기본으로 true를 반환한다. 만약 false를 반환하면 해당조건에는 render 함수를 호출하지 않는다.

 

componentWillUpdate

componentWillUpdate(nextProps, nextState){
  
}

shouldComponentUpdate에서 true를 반환했을때만 호출.

애니메이션 효과를 초기화하거나, 이벤트리스너를 없애는 작업.

이 함수가 호출되고 난 다음에는, render() 호출.

 

getSnapshotBeforeUpdate()

  1. render()
  2. getSnapshoptBeforeUpdate()
  3. componentDidUpdate

DOM변화가 일어나기 직전의 DOM 상태를 가져오고, 여기서 리턴하는 값은 componentDidUpdate에서 3번째 파라미터로 받아올 수 있게 된다.

 

componentDidUpdate

componentDidUpdate(prevProps, prevState, snapshot){
  
}

render()를 호출하고 난 다음에 발생.

 


컴포넌트 제거

컴포넌트가 더 이상 필요하지 않게 되면 단 하나의 API 호출

 

componentWillUnmount

componentWillUnmount(){
  
}

 



문제보기 >> [BOJ] 2146 : 다리 만들기


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_2146_다리만들기 {
    static int N;
    static int[] dy = { -1100 };
    static int[] dx = { 00-11 };
    static int[][] map;
    static int[][] boundary;
    private static boolean[][] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        boundary = new int[N][N];
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } ////// input
 
        int chk = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visit[i][j] || map[i][j] == 0)
                    continue;
                bfs(i, j, chk);
                chk++;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (boundary[i][j] <1)
                    continue;
                int b = bridge(i, j, boundary[i][j]);
                min = min > b? b:min;
            }
        }
 
        System.out.println(min);
    }// end of main
 
    static void bfs(int y, int x, int chk) {
        Queue<pair> que = new LinkedList<>();
        que.add(new pair(y, x));
        visit[y][x] = true;
        boundary[y][x] = -1;
        while (!que.isEmpty()) {
            pair p = que.poll();
            int py = p.y;
            int px = p.x;
 
            for (int i = 0; i < 4; i++) {
                int ny = py + dy[i];
                int nx = px + dx[i];
                if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx])
                    continue;
                if (map[ny][nx] == 1) {
                    que.add(new pair(ny, nx));
                    visit[ny][nx] = true;
                    boundary[ny][nx] = -1;
                }
                if (map[ny][nx] == 0) {
                    boundary[py][px] = chk;
                }
            }
        }
    }
 
    static int bridge(int y, int x, int me) {
        int[][] visit2 = new int[N][N];
        Queue<pair> que = new LinkedList<>();
        que.add(new pair(y, x));
        visit2[y][x] = 1;
        int len = 0;
        while (!que.isEmpty()) {
 
            len++;
            int qSize = que.size();
            for (int q = 0; q < qSize; q++) {
                pair p = que.poll();
                int py = p.y;
                int px = p.x;
 
                for (int i = 0; i < 4; i++) {
                    int ny = py + dy[i];
                    int nx = px + dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit2[ny][nx] != 0 || boundary[ny][nx] == -1 || boundary[ny][nx]==me)
                        continue;
                    if (boundary[ny][nx] != 0 && boundary[ny][nx] != -1 && boundary[ny][nx] != me) {
                        //System.out.println("("+ny+","+nx+")");
                        return len-1;
                    }
 
                    if (boundary[ny][nx] ==0) {
                        que.add(new pair(ny, nx));
                        visit2[ny][nx] = len;
                    }
                }
            }
        }
        return len;
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
}
 
cs


'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17144 : 미세먼지 안녕!  (1) 2019.06.20
[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
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
package basic;
 
import java.util.ArrayList;
import java.util.Arrays;
 
public class NumberOfCases {
    static char[] arr = { 'a''b''c''d' };
    static int r = 2;
 
    public static void main(String[] args) {
 
        set = new char[r];
        // System.out.println("==조합==");
        // nCr(0,0);
        //comb(r,arr.length);
        // System.out.println("==중복조합==");
        // nHr(0,0);
        //System.out.println("==중복순열==");
        //nPir(0);
        setList = new ArrayList<>();
        //subset(0,0);
        
        visit = new boolean[arr.length];
        nPr(0);
    }
 
    static char[] set;
 
    public static void nCr(int len, int k) { // 조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nCr(len + 1, i + 1);
        }
    }
 
    public static void comb(int depth, int idx) {
        if (depth==0) {
            System.out.println(Arrays.toString(set));
        } else if (idx < depth) {
            return;
        } else {
            //System.out.println(depth + " " + idx );
            set[depth-1= arr[idx-1];
 
            comb(depth - 1, idx - 1);
            comb(depth, idx-1);
        }
 
    }
 
    public static void nHr(int len, int k) { // 중복조합
        if (len == r) {
            System.out.println(Arrays.toString(set));
            return;
        }
 
        for (int i = k; i < arr.length; i++) {
            set[len] = arr[i];
            nHr(len + 1, i);
        }
    }
    static boolean[] visit;
    public static void nPr(int len) {// 순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            if(!visit[i]) {
                set[len]=arr[i];
                visit[i]=true;
                nPr(len+1);
                visit[i]=false;
            }
        }
    }
 
    public static void nPir(int len) {// 중복순열
        if(len==r) {
            System.out.println(Arrays.toString(set));
            return;
        }
        
        for(int i=0;i<arr.length;i++) {
            set[len]=arr[i];
            nPir(len+1);
        }
    }
 
    static ArrayList<Character> setList;
    public static void subset(int len, int k) {// 부분집합
        System.out.println(setList);
        if(len==arr.length) {
            return;
        }
        for(int i=k;i<arr.length;i++) {
            setList.add(arr[i]);
            subset(len+1,i+1);
            setList.remove(setList.size()-1);
        }
    }
}
 
cs

'Computer Science > Algorithms' 카테고리의 다른 글

[java] Dijkstra 다익스트라 알고리즘  (0) 2019.02.19
Kruskal 크루스칼 알고리즘  (0) 2019.02.18
DisjointSets  (0) 2019.02.18
[java] Insertion Sort 삽입정렬  (0) 2019.01.28
Permutation 순열  (0) 2019.01.17



문제보기 >> [BOJ] 17281 :: ⚾ 야구


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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//BOJ:: 17281 야구 
public class Main17281_야구 {
    static int N;
    static int[][] rst;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine()); // 이닝
        rst = new int[N][10];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 1; j < 10; j++) {
                rst[i][j] = Integer.parseInt(st.nextToken());
            }
        } //////// input
 
        visit = new boolean[10];
        player = new int[10];
        player[4= 1;
        max = -1;
        perm(1);
        System.out.println(max);
    }// end of main
 
    static boolean[] visit;
    static int[] player;
    static int max;
    public static void perm(int len) { // 선수 배치하기
        if (len == 4) { // 4번째 타자는 1번.
            perm(len + 1);
            return;
        }
        if (len == 10) {
            // 선택완료
            int score = playGame();
            max = max<score? score:max;
            return;
        }
 
        for (int i = 2; i < 10; i++) {
            if (visit[i])
                continue;
            player[len] = i;
            visit[i] = true;
            perm(len + 1);
            visit[i] = false;
        }
    }
 
    public static int playGame() {
        int score = 0;
        int out;
        boolean[] roo = new boolean[4];
        int hitter = 1;
        
        for (int inning = 0; inning < N; inning++) {
            out = 0;
            Arrays.fill(roo, false);
            while(true) {
                int now = rst[inning][player[hitter]];
                if(hitter==9) hitter = 1;
                else hitter++;
                if (now == 1) { // 안타
                    if(roo[3]) {
                        score++;
                        roo[3]=false;
                    }
                    for(int r=2;r>=1;r--) {
                        if(roo[r]) {
                            roo[r]=false;
                            roo[r+1]=true;
                        }
                    }
                    roo[1]=true;
                } else if (now == 2) { // 2루타
                    if(roo[3]) {
                        score++;
                        roo[3]=false;
                    }
                    if(roo[2]) {
                        score++;
                        roo[2]=false;
                    }
                    if(roo[1]) {
                        roo[1]=false;
                        roo[3]=true;
                    }
                    roo[2]=true;
 
                } else if (now == 3) { // 3루타
                    for(int r=1;r<=3;r++) {
                        if(roo[r]) {
                            score++;
                            roo[r]=false;
                        }
                    }
                    roo[3= true;
                } else if (now == 4) { // 홈런
                    for(int r=1;r<=3;r++) {
                        if(roo[r]) {
                            score++;
                            roo[r]=false;
                        }
                    }
                    score++//타자도 홈으로.
                } else if (now == 0) { // 아웃
                    out++;
                    if (out == 3) {
                        break;
                    }
                }
            }
        }// end of for
        return score;
    } //end of playGame
}// end of class
 
cs

 

Comment

정말 귀찮은 문제다~

 

순열로 타자를 뽑아준다. 여기서 1번 타자가 4번째 순서는 고정인 것에 주의해야 한다!

타자를 뽑은 후에는 주어진 조건대로 게임을 진행하고, 최대 점수를 갱신한다.

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17144 : 미세먼지 안녕!  (1) 2019.06.20
[BOJ] 2146 : 다리 만들기  (1) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09

 

 

문제보기>> [BOJ] 16236 : 아기상어

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
//2019-06-01
//BOJ 16236 아기상어
 
/*
 * 아기상어의 초기 크기 : 2
 * 자신보다 큰 물고기가 있는 칸은 지날 수 없다. 나머지 칸은 지날 수 있다.
 * 자신의 크기보다 작은 물고기만 먹을 수 있다. 
 * ==> 크기가 같은 물고기는 먹을수는 없지만, 지나갈 수는 있다.
 * 
 * 더 이상 먹을 수 있는 물고기가 공간에 없으면. 엄마 상어에게 도움을 요청한다.
 * 먹을수 있는 물고기가 1마리면 먹으러 간다.
 * 1마리보다 많으면,가장 가까운 물고기를 먹으러 간다 .
 *  지나야하는 칸의 개수의 최솟값.
 *  가까운 물고기가 많으면 : 가장위 -> 가장 왼쪽 
 *  이동과 동시에 물고기를 먹는다. 
 *  물고기를 먹으면, 그 칸은 빈칸이된다.
 *  
 *  자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가.
 *  크기가 2인 아기 상어는 물고기를 2마리 먹으면 이됨.
 *  
 */
public class Main_16236_아기상어 {
    static int N, ans;
    static int[][] map;
    static int[] dy = { -1100 };
    static int[] dx = { 00-11 };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        int sy = -1, sx = -1;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    sy = i;
                    sx = j; // 아기상어 위치 
                }
            }
        } // input
        bfs(sy, sx);
        System.out.println(ans);
    }// end of main
    
    
    public static void bfs(int sy, int sx) {
        int sharksize = 2//초기크기 
        int sharkeat = 0;
        Queue<pair> q = new LinkedList<>();
        ArrayList<pair> fish = new ArrayList<>();
        boolean[][] visit = new boolean[N][N];
        q.add(new pair(sy, sx)); // 아기상어의 초기위치
        visit[sy][sx]=true;
 
        int time = 0;
        while (!q.isEmpty()) {
            
            int qSize = q.size();
            int y=-1, x=-1;
            for (int s = 0; s < qSize; s++) { //1초 단위로 순회 
                
                pair p = q.poll();
                y = p.y;
                x = p.x;
                for (int i = 0; i < 4; i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];
 
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx] || map[ny][nx]>sharksize)
                        continue;
                    
                    q.add(new pair(ny, nx)); //방문할 수 있는 모든 곳 (빈 곳, 상어 이하 크기의 물고기 )
                    visit[ny][nx] = true;
                    if(map[ny][nx]!=0 && map[ny][nx]<sharksize) { //그 중, 먹을 수 있는 물고기 
                        fish.add(new pair(ny,nx));
                    }
                }
            } // 1초
            time++;
            
            if(fish.size()!=0) { //먹을 물고기가 있다.
                Collections.sort(fish); //조건에 맞는 물고기 찾기. 
                pair meal = fish.get(0);
                fish.clear(); 
                sharkeat++;
                if(sharksize==sharkeat) {
                    sharksize++;
                    sharkeat=0;
                }
                
                map[sy][sx]=0//이전 상어 위치 초기화 
                sy=meal.y;
                sx=meal.x; //상어 위치 변경 
                map[sy][sx] = 9//이동후 상어의 위치 
                
                q.clear(); 
                q.add(meal); //이동 후 상어의 위치부터 다시 bfs 순회. 
                ans+=time; //****** 시간을 더해준다. ******
                time = 0//시간 초기화 
                for(int i=0;i<N;i++) { //visit initialize
                    Arrays.fill(visit[i], false);
                }
                visit[meal.y][meal.x]=true;
            }
            
        } // end of while
    }// end of bfs
 
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
        @Override
        public int compareTo(pair o) {
            if (this.y == o.y) {
                return this.x - o.x;
            } else {
                return this.y - o.y;
            }
        }
    }
}// end of class
 
cs

 

< Comment >

5번만에 해결한 아기상어..

이 문제에서 주의해야할 부분은 "더 이상 먹을 수 있는 물고기가 공간에 없으면. 엄마 상어에게 도움을 요청한다." 이다.

 

더이상 먹을 수 있는 물고기가 있는지 없는지 어떻게 알 수 있을까?



나는 ans 와 time을 분리함으로서 해결했다.

상어를 직접 이동시켰을 때, 갈 수 있는곳을 모두 순회해보고 그제서야 먹을 수 있는 물고기가 없다는걸 깨닫는다면 답을 얻을 수 없다.

따라서 나는 물고기를 탐색할때 time을 증가시켜주고,

먹을 물고기를 찾아 먹을 때 ans+=time; time=0; 작업을 해줬다 !

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 2146 : 다리 만들기  (1) 2019.06.05
[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05


물회보다 육전이 더 맛있읍니다,,❤️❤️❤️


나잇값 못하는 두분과..
4차 산업혁명을 사랑하는 호 🥺


여기가 제주도인줄 아는 취객 셋 😺😺😺;;;

'Diary' 카테고리의 다른 글

역삼동 맛있는 제주  (2) 2019.03.01
선릉 착한고기  (4) 2019.01.31
역삼 민들레떡볶이  (3) 2019.01.30
역삼 호타루  (2) 2019.01.25
역삼 전봇대  (2) 2019.01.23

해시테이블 HashTable

 

Concepts

해싱함수(hash function)

  • 해싱함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길의의 데이터로 매핑하는 함수.
  • 매핑 전 데이터 값을 Key, 매핑 후 데이터 값을 해시값(Hash value), 매핑하는 과정을 Hashing이라고 한다.
  • 해시함수는 언제나 동일한 해시값을 리턴

  • 해당 index만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있다.

  • index는 계산이 간단한 함수(상수시간)로 작동한다.

    —> 데이터 엑세스(삽입,삭제,탐색)시 O(1)을 지향한다.

 

해시테이블(HashTable)

  • 해시함수를 사용하며 키를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터를 키와 함께 저장하는 자료구조
  • 데이터가 저장 되는 곳을 bucket 또는 slot 이라고한다
  • 장점

    • 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
    • ex) 하드디스크나 클라우드에 존재하는 무한에 가까운 key들을 유한한 개수의 hash value로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다.
  • Direct-address table : 키의 개수와 동일한 크기의 버킷을 가진 해시테이블

    • 해시 충돌 문제가 발생하지 않는다.
    • 전체 키에 대한 공간을 만들어 놓는다
    • 실제 사용하는 키보다 전체 키가 훨씬 많은 경우 메모리 효율성이 떨어진다.

 

 

Problem

  • 해시함수는 해쉬값의 개수보다 대게 많은 키 값을 해쉬값으로 변환(many-to-one)하기 때문에,

  • 해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 나타내는 해시충돌(collision)이 발생하게 된다.

  • 현재까지 개발된 거의 모든 해싱함수는 해시충돌을 일으킨다.

  • 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는것이 중요하다.

 

 

Solve

Chaining

  • 하나의 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다.
  • 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가르키는 방식으로 구현(연결리스트)
  • 메모리 문제를 야기할 수 있다.

  • 시간복잡도

    hashtable size : m , keys : n

    버킷 하나당 n/m = x개의 데이터 이라 가정.

    • 탐색

      매핑 O(1) + 버킷요소 x 탐색 O(x) => O(1+x)

    • 삽입

      매핑 O(1) + 추가 O(1) => O(1)

    • 삭제

      매핑 O(1) + 탐색 O(x) + 삭제 O(1) => O(1+x)

 

open addessing

  • 한 버킷당 들어갈 수 있는 엔트리가 하나쁜인 해시테이블
  • 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용
  • 메모리 문제는 발생하지 않지만, 해시충돌이 생길 수 있다.
  • 특정 해시값에 키가 몰리게 되면 효율성이 크게 떨어진다.

ex) 해시함수가 '키 값을 8로 나눈 나머지' 10, 18, 26 순으로 해시테이블에 삽입해보자.

세 숫자 중 첫번째 값 10 을 제외한 18, 26인 원래 버킷(2) 말고 각각 다음 (3) , (4)에 저장된다.

[2] 10

[3] 18

[4] 26

—선형탐사

 

probing

  • open address의 효율성 감소 문제를 해결한다.
  • 삽입,삭제,탐색을 수행하기 위해 해시테이블 내 새로운 주소를 찾는 과정

 

  • 선형탐사(Linear probing)

    • 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼있으면 해시값에서 고정폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스한다.
    • 여기에 데이터가 있으면 또 고정폭 만큼 옮긴다.
    • 특정 해시값 주면 버킷이 모두 채워져 있는 primary clustering 문제에 최약하다

 

  • 제곱탐사(Quadratic probing)

    • 이동 폭이 제곱수로 늘어난다.
    • 예를들어, 데이터 엑세스할때 충돌이 일어나면 1^2 칸을 옮긴다. 여기서 또 충돌이 일어나면 2^2 만큼, 그다음엔 3^2 만큼 옮긴다.
    • 여러 개의 서로 다른 키들이 동일한 초기 해시값을 갖는 secondary clustering에 취약하다.

  • 이중 해싱(double hashing)

    • 탐사할 해시값의 규칙성을 없애서 clustering을 방지한다.
    • 2개의 해시함수를 준비해 하나는 최초의 해시값을 얻을 때, 하나는 해시충돌이 일어났을때 탐사 이동폭을 얻기 위해 사용.

'Computer Science > Data Structure' 카테고리의 다른 글

Merge Sort 병합정렬  (4) 2019.01.29
[Java] 배열과 List / Set / Map  (0) 2019.01.22

+ Recent posts