본문으로 건너뛰기

2026-06-11 학습 일지

오늘 한 일​

  • 그래프 자료구조 개념 정리
  • 그래프 표현 방법(인접 행렬/인접 리스트)과 탐색(DFS/BFS) 학습

배운 내용​

그래프 기본​

  • 정점(vertex)을 간선(edge/link)으로 연결한 자료구조 — 연결 관계 표현
  • 트리도 그래프의 일종
    • 트리: 사이클 없음 + 상하 관계(계층적 구조)
    • 그래프: 사이클 가능 + 상하 관계 없음 → 더 일반적인 연결 관계 표현

그래프 종류​

  • 연결 그래프: 임의의 두 정점 사이에 경로 존재 ↔ 비연결 그래프
  • 방향 그래프 ↔ 무방향 그래프
  • 가중치 그래프: 간선에 가중치(비용, cost) 부여. 양수·음수 모두 가능
  • 서브 그래프: 특정 그래프의 정점·간선 일부로 이루어진 그래프

그래프 표현​

  • 인접 행렬: N×N 행렬, <행, 열> = <출발 정점, 도착 정점>
    • 연결 1 / 비연결 0, 가중치 그래프는 가중치 값으로 표기
    • 무방향 그래프는 양방향 연결로 간주 → 행렬이 대칭
  • 인접 리스트: 정점마다 연결된 정점들을 연결 리스트로 관리
인접 행렬인접 리스트
공간O(V²)O(V+E)
두 정점 연결 확인O(1)O(차수)
유리한 경우밀집 그래프희소 그래프

그래프 탐색​

  • DFS(깊이 우선 탐색): 더 이상 방문할 정점이 없을 때까지 최대한 깊이 탐색 반복
    • 구현: 방문 여부 배열 + 스택 (뒤로가기)
  • BFS(너비 우선 탐색): 가까운 정점부터 최대한 넓게 탐색 반복
    • 구현: 방문 여부 배열 + 큐 (연결 정점 줄세우기)
  • 시간 복잡도: 둘 다 인접 리스트 기준 O(V+E), 인접 행렬 기준 O(V²)

내일 할 것​

  • 정처기 실기 계산 문제풀이 시작 (6/22 접수 전 워밍업)