BFS3 코딩테스트 빈출 유형 정리 [코딩테스트 주요 알고리즘]- 구현 및 시뮬레이션 - 문자열 처리(해시테이블 or 스택)- 완전 탐색(브루트 포스)- 이진 탐색(매개변수 탐색)- 그래프 탐색(DFS, BFS)- 백트래킹- DP- 그리디- 투포인터 [가끔 나오는 알고리즘]- 정렬- MST(크루스칼)- 최단경로(다익스트라, 벨만-포드, 플로이드-와샬)- 위상정렬- 모든 쌍 최단경로 문제- 분리집합- 트리의 지름 구하기- 트라이 2024. 8. 4. [알고리즘] ep5-2+) DFS, BFS 구현 문제1) DFS 구현입력으로 주어지는 그래프의 DFS 순회 결과를 출력하는 프로그램을 작성하시오. 입력 그래프의 성질:n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m ≤ 1,000) 개의 간선으로 구성정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름모든 간선은 무방향 간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재구현 조건:그래프는 인접리스트 구조를 사용하여 표현해야 한다.인접 정점의 조사 순서: 정점 u의 인접 정점(or 부착 간선)들을 번호가 작은 정점부터 조사한다. (즉, 아래 DFS 의사 코드의 for 문에서 인접 정점들을 번호가 작은 정점부터 큰 순서대로 조사하라. 조사 순서에 따라 방문 결과가 달라질 수 있음에 유의할 것)입력:첫 줄에.. 2024. 7. 22. [알고리즘] ep5-2) 그래프 순회 그래프 순회(graph traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차- 수도권 전철망의 모든 역(정점)의 위치를 출력- 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집- 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 서핑 그래프의 순회로는 DFS, BFS 두 가지가 있다그래프 G에 대한 DFS 순회 또는 BFS 순회의 활용은 아래와 같다- G의 모든 정점과 간선을 방문- G가 연결그래프인지 결정- G의 연결요소들을 계산- G의 신장 숲을 계산 ① 깊이우선탐색(DFS, Depth-First Search) by 스택(재귀)n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요 "D.. 2024. 7. 21. 이전 1 다음
