728x90 note/algorithm3 BFS (Breadth First Search, 너비 우선 탐색) 접근 graph 또는 tree를 탐색하는 알고리즘이다. 특정 노드부터 시작하여 인접한 노드들을 먼저 탐색한다. (최단 경로를 찾을 때 사용) 특정 노드로부터의 거리에 따라 순서대로 탐색한다. 알고리즘 큐(queue)와 while문을 사용한다. 큐(queue)에서 꺼낼 때, 그 노드를 visit 했다고 표시한다. 큐(queue)에서 꺼낸 노드와 인접한 노드들을 큐(queue)에 집어넣는다. 큐(queue)가 empty상태가 될 때까지 수행한다. Pseudo-code while(!queue.empty){ current = queue.pop; current.visited = true; for(current.adj) if(!adj.visited) queue.push(adj); } 적용 더보기 https://jo.. 2022. 5. 22. DFS (Depth First Search, 깊이 우선 탐색) 접근 graph 또는 tree를 탐색하는 알고리즘이다. 특정 노드부터 시작하여 최대한 멀리 갈 수 있을만큼 진행한다. 바로 전 분기점까지 돌아가고 아직 방문하지 않은 다음 노드로 진행한다. (방문한 노드들은 표시한다) 알고리즘 재귀함수를 사용한다. 현재 노드를 visit 했다고 표시한다. 인접해있고 visit하지 않은 노드를 탐색하고 해당 노드의 index를 넣은 재귀함수를 호출한다. Pseudo-code dfs(current){ visited[current] = true; for(adj){ if(!visited[adj]) dfs(adj); } } 적용 더보기 https://jolly-note.tistory.com/61 [백준/baekjoon] Silver4 1388. 바닥 장식 DFS -DFS 링크 추.. 2022. 5. 22. linked list - 이중(doubly) 연결 리스트(c++) 양방향으로 연결돼있는 linked list이다. 현 노드에서 이전 노드와 앞의 노드로 갈 수 있다. + singly linked list는 각 노드가 다음 노드만 가리킨다. + circular linked list는 각 노드가 다음 노드만 가리키는데, 마지막 노드가 처음 노드를 가리키고 있다. 프로그래머스 풀이 시 doubly linked list를 만들 일이 있어서 doubly로 쓰게 되었으나, Node 만드는 법만 알면 다른것도 쉽게 만들 수 있다. Node struture을 만들어준다. 간단한거라서 struture로, 복잡한건 class로 만들자. 만드는 법을 까먹었다면(내가 까먹음) 아래를 참고해주자. https://docs.microsoft.com/ko-kr/cpp/cpp/initializing.. 2022. 4. 27. 이전 1 다음 728x90