정보처리기사 필기
시험 직전 요약장
판단 기준과 헷갈리는 개념, 대표 예제를 짧게 확인하세요.
트리·순회·그래프 표현
원래 이론 →헷갈리는 개념
표를 좌우로 밀어 나머지 열을 확인하세요. 키보드: ←·→, Home·End
| 기준 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 저장 공간 | O(V²) | O(V + E) |
u-v 간선 존재 확인 | O(1) | 일반적인 리스트에서는 O(deg(u)) |
정점 u의 모든 이웃 확인 | O(V) | O(deg(u)) |
| 적합한 그래프 | 간선이 많은 밀집 그래프 | 간선이 적은 희소 그래프 |
| 무방향 그래프 특징 | 행렬이 대칭 | 각 간선을 양쪽 리스트에 저장 |
인접 행렬은 정점 수만으로 공간이 정해지므로 간선이 적어도 O(V²)를 사용한다. 인접 리스트는 실제 간선 중심으로 저장하므로 희소 그래프에서 공간을 절약하고 이웃 정점을 빠르게 순회할 수 있다.
대표 계산·예제
예를 들어 루트를 레벨 1로 두고 레벨이 4개인 포화 이진 트리는 각 레벨에 1, 2, 4, 8개의 노드가 있으므로 전체 노드는 15개다. 같은 트리의 높이를 간선 수로 세면 3이다.
내 최근 연습 오답
현재 브라우저의 연습 채점 기록에서 공개된 단원과 연결된 오답을 확인합니다.
오답 기록을 확인하고 있습니다.