이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
Learn graph algorithms: BFS/DFS applications, Dijkstra, Bellman-Ford, negative cycles, and practical shortest path problems.
그래프 알고리즘은 컴퓨터 과학에서 가장 넓은 응용 범위를 가진 분야예요.
네이버 지도에서 최단 경로를 찾을 때 그래프를 써요.
인스타그램 친구 추천도 그래프 탐색이에요.
네트워크 라우팅에서 패킷이 어디로 갈지 결정하는 것도요.
그래프는 정점과 간선으로 관계를 표현하는 구조예요.
정점은 노드라고도 부르고 대상을 나타내요.
간선은 두 정점 사이의 연결을 의미해요.
방향 그래프는 간선에 화살표가 있어서 일방통행 같아요.
무방향 그래프는 양쪽 모두 이동할 수 있는 거예요.
가중치 그래프는 간선마다 비용이나 거리가 붙어 있어요.
서울에서 부산까지 삼백 킬로미터 이런 식으로 말이에요.
이번 레슨에서 BFS DFS 응용을 먼저 다뤄요.
BFS는 너비 우선 탐색이고 레벨 단위로 퍼져나가요.
DFS는 깊이 우선 탐색이고 한 방향으로 끝까지 가요.
그다음 다익스트라 알고리즘으로 최단 경로를 구해요.
벨만 포드는 음수 가중치도 처리할 수 있어요.
음수 사이클이 있으면 최단 경로가 무한히 줄어들어요.
이건 실제 환율 거래에서 차익을 찾는 문제랑 같아요.
영 일 BFS나 플로이드 워셜까지 배우면 거의 완벽해요.
각 알고리즘의 시간 복잡도와 적합한 상황을 비교해볼 거예요.
자 그러면 BFS 심화부터 시작해볼게요.