IT 공부한거 올리는 블로그

bfs의 원리 1. 시작노드를 큐에 넣고 방문했다는 표시를 함 2. 큐에서 원소를 하나 빼고, 인접한 노드들에 대해 3번을 진행함 3. 방문했으면 아무것도 하지 않고, 방문하지 않았으면 원소를 큐에 넣고 방문했다는 표시를 함 4. 큐에 원소가 빌때까지 2번을 반복함 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) 참고 블로그: https://blog.encrypted.gg/941 [실전 알고리즘] 0x09강 - BFS 안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋 blog.encrypted.gg 1260번을 한 번 풀어보겠다 https://..

그래프 탐색 방법 중 대표적인 DFS와 BFS에 대해서 다뤄보려고한다 DFS와 BFS를 알기 전에 우선 이진 트리의 순회 방법에 대해서 짚고 넘어가자 트리에 있는 모든 노드를 한 번씩만 방문하는 방법인데 여기서 전위순회(Preorder Traversal) VLR방법이 DFS와 유사하다 현재 노드를 출력하고 왼쪽으로 쭉 갔다가 오른쪽이없으면 이전노드로 가서 오른쪽으로 가는 방법을 계속 방법한다 두 번째로 레벨순서 순회(Level-order Traversal) 레벨순서는 이진트리의 높이 순서대로 출력하는거다 루트노드인 + 그 다음 높은 *, E 다음으로 *, D /, C A B순서대로 출력한다 Level-order Traversal할때는 큐가 사용된다 처음에 루트노드인 +를 큐에 push 하고 반복문을 돌며..