오래 못 할 짓 하지 않기

Hashing : 저장하려는 Key값에 따라 위치를 정하는 것 용어 Hash table : key값이 들어갈 연속적인 저장공간 ( array ) Hash Function : Hash table상의 위치를 mapping 하는 함수 Collision : 서로 다른 key값이 같은 bucket주소로 mapping ( ex: 화장실 칸에 한 명 있는데 거기에 들어간다는 느낌 ) → 3명들어갈 칸이면 사실 들어가도 되긴 함 overflow : bucket이 꽉찼는데, slot 수보다 많이 저장되려고 할 때 → collision이 발생하다가는 결국 overflow가 발생함 → 구현할 때 고려해야하는 issues : 1. Hash fuction / 2. overflow handling method 요건 : 계산이 쉬..

Graph 5문제 Sort 5문제 AVL 2문제 Huffman 1문제 Hash 1문제 STL 1문제 --> stack이나 vector 둘 중에 하나 선택해서 하는 문제 Selection -- >가장 작은 놈 찾아서 가장 앞으로 Insertion -- > 1번부터 n번까지 한 명 한 명 가면서 앞에 애들이랑 비교해서 가야할 위치에 Insert Bubble -- > 앞 뒤로만 비교해서 가장 뒤로 보 1) 각 사이클 첫 원소 = 최솟값으로 박아놓고 시작. 2) 첫 원소 빼고 돌면서 작은 애가 나오면 걔가 최솟값으로 됨. ( 2)는 사실 첫 원소보다 작은 애가 있는지 보려고 하는 거 ) 3) for int j 사이클에서 항상 마지막에는 첫 원소와 가장 작다고 나온 원소의 위치를 교환한다 (중간에 첫 원소보다 작..

Huffman tree two-way merge = 정렬된 2개의 리스트를 1개로 병합 ex) {1,3} {2,6} --> {1,2,3,6} merge sort라고 생각해도 될 듯 Hufffman tree는 이렇게 하나의 list를 만들 때, 최적의 순서를 찾는다. 이으려고 할 때, 작은 원소들을 먼저 결합시킨다 작은 원소의 후보는 두 개를 합쳐서 만들어진 원소도 후보가 될 수 있음. 예시로 [ 2 4 5 7 9 12 ] 이 원소들로 트리를 만들어보자. 우선 가장 작은 두 개를 먼저 결합 --> 2,4 이 떄 2,4를 6으로 바꿔줘도 될 것 같다. 리스트에 남은 원소는 [ 6 5 7 9 12 ] 가장 작은 6 5를 합쳐준다. 이런 형태가 되고 다시 리스트를 보면 [ 11 7 9 12 ] 가 된다. 여기에..

Radix sort 여러 Key에 대해 sort한다. 각 Key에 따라 우선 순위가 다르다. ex) 학생 명단을 sort할 때, 학부 > 성명 > 학번으로 sort한다고 생각해보자. 가장 먼저 학부 순으로 sort --> 같은 학부에서는 이름 순으로 sort --> 이름까지 같다면 학번순으로 sort Most significant key --> 학부 Least significant ket --> 학번 예 ) 학부 > 학번 2개로 sort한다고 생각해보자 방법 1) Most significant key 에 대하여 먼저 sort -- > 전체 명단을 학부별로 분리 -- > 각 학부별 명단을 학번 순으로 sort --> 각 파일(array)을 순서대로 한 개로 결합. 방법 2) Least significant..

Selection Sort --> 매 사이클마다, 범위에서 [ 가장 작은 값의 위치 ] 와 해당 사이클 [ 가장 앞 원소 위치 ] 와 와 교환 가장 작은 놈 찾아서 제일 앞으로 보냄 void selection_sort(s_record a[], int n){ for (int j = 0 ; j 둘 다 멈춰서 밑으로 나왔을 때, (ij) 이면 (=교차했으면) while을 탈출했을거고 swap( a[left], a[j] ) 한 뒤에 오른쪽 왼쪽 파트에서 Quick sort 진행. : Worst case 이미 sort가 되어있는 array면 효율은 최악이다. --> 매 사이클마다 큰 쪽 / 작은 쪽이 아니라. 그냥 끝만 숭덩숭덩 썰고 있기 때문에 검색 대상이 왼쪽으로 잘려야 일이 빨리빨리 줄어드는데, 오른쪽이면 ..

AOE Network Active On Edge Edge가 Ativity를 의미 Weighted(=cost) edge Vertex = 작업이 완료된 상황 분석 ) Critical Path = The Longest Path - cost가 가장 큰 path 여기에서 crtical path를 보면 a3 -> a6 -> a8 -> a10 6 + 7 + 7 + 4 = 21 이다. 전체 성능에 영향을 준다는 이유는, 군대 밥먹는 거라고 생각하면 됨. 마지막 사람이 올 때까지는 출발 못 하듯 8상태가 되기 위해서는 a10와 a11을 지나야 함. Earliest start time = 해당 Activity 가 시작되려면 필요한 시간 = 마지막 주자까지 와야 그게 기록 종료임. 빨리 오는 애들은 영향없음. or a8 도..

Spanning Tree 시작하기 전에 tree = 그래프의 일종 = cycle이 없는 그래프 Edge는 n-1개가 만들어진다. Edge 개수 = Vertex 개수 -1 이니까 ※ 원래 그래프에 있는 Edge만 사용 가능하다. 위 그래프 같은 경우엔 C -B 이런 건 안 됨 DFS , BFS 루트대로 만드는 Spanning tree도 있음 Biconnected Component --> articulation point 를 갖지 않는 connected graph + articulation point ==> 해당 vertex가 삭제되면 원래 하나의 그래프가 두 개 이상으로 나눠지는 vertex. 위 사진에서는 C가 Articulation point임. C가 삭제되면 나머지 그래프가 둘로 나눠짐 Minmum ..

Selection Trees 전체에서 가장 작은 걸 가져가 Tree에 넣고, 그 다음 원소를 위로 올림. 가장 작은 값을 반환하는 걸로 구현되어있음 , 큰 거로도 가능함. 정확히는 토너먼트 식으로 구현함. 1) Winner trees : 원소 2개씩 대진표를 짜고, 이기는 원소가 계속 올라감. Loser trees : 패배한(더 큰) 원소의 정보를 올리고, 실제로 올라가는 건 이긴 쪽 (참고용) 왼쪽 그림을 보면 2 vs 8했을 땐 2가 이기는데 진 8의 정보를 올려놓고, 그 뒤에도 그렇게 진 원소의 값을 올려놓는다. 그렇게 해서 Root 에 3까지 올라가있다는 건 3이 마지막에 졌고, 3한테서 이긴 놈은 그 위로 나갔다. 장점 ) 옆에 애랑 비교하는 게 아니라, parent랑 비교하면 되니까 정말 조금..

Sum 알고리즘 (Recursive 로 구현) Overall : root 를 입력받아 그 이하 n개의 원소의 값을 합함. 1) 입력받은 root 가 empty면 (=원소 개수(n)보다 root가 크면) return 0; 2) empty가 아니면, return(root 값 + 왼쪽 subtree합 + 오른쪽 subtree합) Delete_node_by_name 우선 1. 힙 노드의 개수를 맞추는 함수 2. 찾아서 삭제하는 함수 3. 다시 tree의 구조를 조정하는 함수 1. 힙 노드의 개수를 맞추는 함수 (입력은 tname을 받음) 1) 노드가 없으면 => csize==0 이면 return 0; 2)하나를 삭제하면 노드 개수 하나 -1 if( 찾아서 삭제하는 함수 ==1) csize --; return 1..