Algorithm23 [Algorithm] BFS (너비 우선 탐색) 알고리즘 FIFO 탐색 (First In First Out) DFS:LIFO 큐 자료구조 이용 시간복잡도: O(V+E) 알고리즘 아이디어 1.BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 2.큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입 3.큐 자료구조에 값이 없을 때까지 반복하기 큐에 노드가 없을 때까지 앞선 과정을 반복한다. 선입선출 방식으로 탐색한다. 수도코드 Algorithm bfs(g,v) visitied[v] = true Q.enqueue(v) while (Q) v= Q.dequeue() for (w adjacent to v) if (!visited[w]) visited[w] = true Q.enqueue(w) 참고자료 https://velog.io/@sangmin7648.. 2023. 3. 25. [Algorithm] DFS (깊이 우선 탐색) 알고리즘 DFS 알고리즘 (깊이 우선 탐색) 그래프의 모든 정점을 한 번만 방문하는 알고리즘 특징 재귀 함수로 구현 스택 자료구조를 이용 FILO(First In Last Out): 먼저 들어온 데이터가 나중에 나간다. 시간복잡도 O(V+E) 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 때 배열이 필요하며, 그래프는 인접 리스트로 표현한다. 알고리즘 정리 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 3. 스택 자료구조에 값이 없을 때까지 반복하기 (이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는다. 수도코드 stack Algorithm dfs(graph,v) stack.push(v) w.. 2023. 3. 25. [BOJ] 백준 11399 ATM (파이썬 python) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘, 삽입 정렬 인프런 강의를 보고 참고하였습니다~ Step 1 문제 분석 ATM에서 모든 사람이 가장 빠른 시간에 인출하는 방법을 그리디 방식으로 해결한다. ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 것이 곧 그리디 방식이다. 이를 위해서는 인출 시간을 기준으로 값을 정렬해야한다. (오름차순) 정렬을 마친 후에는 각 사람이 돈을 인출하는데 필요한 시간을 .. 2023. 3. 23. 이전 1 ··· 3 4 5 6 다음
