CS/알고리즘16 [알고리즘] Directed Graph에서 사이클 찾기 방향이 있는 그래프에서 싸이클을 찾는 방법을 알아보자. Using BFS Kahn 알고리즘을 사용한다. www.geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs/ Detect Cycle in a Directed Graph using BFS - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.. 2023. 4. 15. [알고리즘] 최단 경로 역추적 다익스트라 알고리즘과 플로이드 와샬을 사용한 최단거리 찾기 문제에서 종종 출제되는 경로 역추적 문제이다. 최단 거리와 그 경로를 찾는 문제로 다익스트라 알고리즘과 플로이드 와샬의 역추적 접근 방법이 약간 다르다. 공통점 최단 거리가 업데이트 될 때 경로 역시 업데이트 한다. 다익스트라 path[NODE] = PREV NODE에 도착하기 전 거쳐야 하는 노드가 PREV 경로 초기화 for (int i = 1; i dist[curNode] + a.first) { ... path[a.second] = curNode; } 경로를 추적할 땐 dst -> src까지 거꾸로 내려간다. vector answer; int x = dst; while (x != path[x]) { answer.push_back(x); x .. 2021. 4. 11. [알고리즘] 이분탐색 Binary Search O(n)이 걸리는 선형 탐색을 O(log n)로 줄일 수 있는 방법이다. 일반적으로 이분탐색이라 하면 // 주어진 조건 내에서 최솟값을 구하라고 할 때 int left = 0, right = MAX; while(left 2021. 2. 1. [알고리즘] 선형 자료 구조에서 탐색(Search) 자료구조 초반에 등장하는 내용 확실히 정리하고 가도록 하자. 3가지 형태의 Search 1) find arbitrary - 원하는 임의의 원소를 찾는다. 2) find first/last - 가장 처음으로/마지막으로 들어온 원소를 찾는다. 3) find max/min - 가장 큰/작은 원소를 찾는다. 또 다른 탐색 Traversal 비선형자료구조(트리, 그래프)에서 사용하는 탐색이다. 주어진 집합 내에서 시작원소로부터 도달 할 수 있는 모든 원소를 찾는 과정이다. 선형/비선형 자료구조 선형 자료구조는 배열, 연결리스트, 스택, 큐 비 선형 자료구조는 그래프. 트리 가 있다. 자료 구조에 따라 분류 1) 선형 자료구조 search 알고리즘 시간 복잡도 검색 추가 삭제 sorted array arbitrar.. 2021. 1. 21. 이전 1 2 3 4 다음
