공대생 도전 일지

연습문제 아래 주어진 키를 해시테이블 A[0..M-1], M =11 에 해시함수 h(k) = (2k + 5)%M 을 사용하여 해싱한 결과를 보여라 키(주어진 순서로): 12,44,13,88,23,94,11,39,20,16,5 충돌이 다음 전략에 의해 해결된다고 가정하고 각각의 경우에 대해 답하라 분리 연쇄법 : 리스트 선형 조사법 : 옆에 옆에 2차 조사법 :a[(h(k)+f(i))%m], f(i) = $i^2$ , i = 0,1,2,3,4,5,, 이중해싱,h'(k) = t-(k%7)을 사용하라 : a[(h(k)+f(i))%m], f(i) = $i^2*h'(k)$ , i = 0,1,2,3,4,5,,,,, 아래의 해시테이블을 새로운 해시함수 h(k)= 2k%m 을 사용하여 크기 M = 19의..

심층문제 n개의 정점과 m개의 간선으로 이루어진 그래프 G를 간선리스트 구조로 표현한다고 가정한다. 이 경우 왜 insertVertex 메쏘드는 $O(1)$시간에 수행되지만 removeVertex 메쏘드는 $O(m)$시간에 수행되는가? 간선을 찾고 만드는데 시간이 오래 걸리기 때문에...? 삽입시에는 만들어서 제일 앞에 넣으면 되기 때문에 GPTinsertVertex 메서드 (시간 복잡도: O(1)): 새 정점을 추가하는 작업은 그래프의 간선 리스트 구조에 직접적인 영향을 주지 않습니다. 새 정점이 추가되면, 이 정점의 간선 리스트는 초기에 비어 있으며, 이를 그래프의 정점 배열에 추가하는 것은 단순한 작업입니다. 새 정점을 추가할 때, 기존의 간선 리스트를 수정하거나 탐색할 필요가 없기 때문에, 이 작..

연습문제 무방향그래프와 관련된 method만을 가지며 갱신 메쏘드를 포함하지 않는, 단순화한 그래프 ADT를 그림 13-14(그래프 ADT의 연결리스트 구현)에 보인 것처럼 연결리스트를 사용하여 구현하기 위해 다음 A,B 두 가지 경우 각각에 대해 다음 메쏘드 들을 의사코드로 작성하라. integer deg(v): 정점 v의 차수를 반환 vertex opposite(v,e): 정점 v의 간선 e에 대한 반대쪽 끝점을 반환 boolean areAdjacent(v,w): 정점 v와 w가 인접한지 여부를 반환 iterator adjacentVertices(v): 정점 v의 인접정점을 모두 반환 iterator incidentEdges(v): 정점 v의 부착간선을 모두 반환그래프가 인접 리스트 구조로 표현됨 A..

연습문제 그래프 G의 정점은 1에서 8까지의 정수고 각 정점의 인접정점들은 아래 테이블에 나열된대로다. G를 순회할 때 주어진 정점의 인접정점들이 테이블에 나열된 순서와 동일한 순서로 반환된다고 가정하고 다음에 답해라 정점 인접정점들 1 2,3,4 2 1,3,4 3 1,2,4 4 1,2,3,6 5 6,7,8 6 4,5,7 7 5,6,8 8 5,7 #### 그래프 G를 그려라 정점 1에서 출발하는 DFS순회에서 정점들이 방문되는 순서를 구하라 1 - 2 - 3 - 4 - 6 - 5 - 7 - 8 정점 1에서 출발하는 BFS 순회에서 정점들이 방문되는 순서를 구하라 1 - 2 - 3 - 4 - 6 - 5 - 7 - 8 인접행렬 구조로 표현된 n-정점 단순그래프에서 DFS 순회가 $O(n^2)$시간에 수행하는..

사전 method 일반 integer size(): 사전의 항목 수를 반환 boolean isEmpty(): 사전이 비어있는지 여부를 반환접근 element findElement(k): (키, 원소) 항목들의 모음인 사전에 키 k를 가진 항목이 존재하면 해당 원소를 반환, 그렇지 않으면 특별 원소 NoSuchKey를 반환 갱신 insertItem(k,e): 사전에 (k,e) 항목을 삽입 element removeElement(k) : 사전에 키 k를 가진 항목이 존재하면 해당 항목을 삭제하고 원소를 반환, 그렇지 않으면 특별 원소 NoSuchKey를 반환 사전 ADT 구현 구현 형태 구현 종류 예 주요 탐색 기법 리스트 무순사전ADT 기록 파일 선형 탐색 순서사전 일람표 이진 탐색 트리 탐색트리 이진탐색..

힙 힙 순서 key(v) >= ket(parent(v)) 힙 높이 $\log{n}$ 힙을 이용한 우선 순위 큐 구현 힙 삽입 Alg insertItem(k) 1. advanceLast() 2. z= last 3. Set node z to k 4. expandExternal(z) 5. upHeap(z) 6 return Alg upHeap(v) 1. if(isRoot(v)) return 2. if(key(v) >= key(parent(v))) return 3. swapElements(v,parent(v)) 4. upHeap(parent(v))힙 삭제 Alg removeMin() 1. k = key(root()) 2. w = last 3. Set root to key(w) 4. retreatLast() - 삭..

힙 힙 순서 key(v) >= ket(parent(v)) 힙 높이 log⁡�logn 힙을 이용한 우선 순위 큐 구현 힙 삽입 Alg insertItem(k) 1. advanceLast() 2. z= last 3. Set node z to k 4. expandExternal(z) 5. upHeap(z) 6 return Alg upHeap(v) 1. if(isRoot(v)) return 2. if(key(v) >= key(parent(v))) return 3. swapElements(v,parent(v)) 4. upHeap(parent(v)) 힙 삭제 Alg removeMin() 1. k = key(root()) 2. w = last 3. Set root to key(w) 4. retreatLast() - ..