공대생 도전 일지

연습문제 그래프 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() - ..