tony9402

보호되어 있는 글입니다.

간선 정보를 저장할 때는 두가지를 이용하여 저장할 수 있다. 1. 인접행렬 공간 복잡도 O(V^2) 간선 유무 확인 시간 O(1) 2. 인접리스트 공간 복잡도 O(V+E) 간선 유무 확인 시간 O(1) (x) - BFS는 현재 정점에서 가장 가까운 곳부터 차례대로 탐색을 해나가는 너비우선탐색 Queue를 사용 기준점으로부터 가까운 곳부터 간다. 최적의 해를 구하라 - DFS는 현재 정점부터 갈 수 있는 곳까지 파고 들어 탐색하는 깊이우선탐색 Stack(또는 재귀)을 이용 백트레킹에 유리 DFS/BFS를 사용하면서 조심해야할 것 : 이미 방문한 정점에 다시 갈 수 있으니 visited 배열을 만들어 체크해야한다.

STL은 Standard Template Library의 약자이며 Problem Solving에 편리하게 쓰이는 템플릿이다. 1. find find함수는 algorithm 헤더 파일에 있다. find함수의 생김새는 find(iterator first, iterator last, const T& val) 이와 같다. 간략히 설명을 하면 찾고차 하는 값을 Linear하게 검색하여 그 값이 존재하면 위치를 가리키는 iterator를 반환하고 값이 존재하지 않으면 end()를 반환한다. 시간복잡도 : O(n) 2. sort sort함수는 find와 마찬가지로 algorithm 헤더파일에 존재한다. sort는 두가지로 정의되어있다. - sort(iterator begin, iterator end) - sort(i..