CodeClover

https://www.acmicpc.net/problem/1260📌 문제 탐색하기DFS, BFS 문제로 ,,, 그래프 탐색 문제 입니다. 방문된 점을 출력하라고 했으니 순서가 중요한 문제입니다. 📌 가능한 시간복잡도가능한 시간복잡도는 입력받은 정점의 개수 N ,간선의 개수 M으로 ...정점과 간선을 한번씩 탐색해서 BFS , DFS 모두 동일하게 O(N+M) ,리스트에 간선 정보를 넣고 정렬해야하니까 O(M logM)따라서 가능한 시간복잡도는 모두 더한값 O(N+M) + O(M logM) 입니다. 📌 코드 설계하기그래프는 List> 으로 인접 리스트를 사용하고 DFS는 스택 ,BFS는 큐를 사용해서 구현하면 된다. 📌 정답 코드import java.io.*;import java.util.*;..

[문제링크]https://www.acmicpc.net/problem/2644 📌 문제 탐색하기그래프 문제로 사람들을 노드라고 생각하고 그래프로 표현이 가능하다. ( 양방향 관계 )두 노드 간 최단 경로를 참색하여 촌수를 계산하는 문제이다. 만약에 노드가 연결되어 있지 않은 경우 -1을 출력한다.📌 가능한 시간복잡도 각각 최대 한번씩만 방문하기 때문에 시간복잡도는 O(N)이다.📌 코드 설계하기탐색하는 방법이 DFS인지 BFS인지에 따라서 풀이가 달라지는데,,, 효율적인 문제풀이 방식이 어떤 방식인지 고민됨. BFS 사용해서 문제 풀이 진행visited[] 배열을 만들어서 방문여부를 저장하는 배열 만들기그리고 큐를 사용해서 현재 탐색하고 있는 노드와 촌수를 저장하기. 📌 정답 코드import java..

큐 생성 방법 ( 3 ) LinkedList 사용한 큐 생성 ( => BFS 구현시 주로 사용 )Queue queue = new LinkedList();요소의 삽입과 삭제가 빠르다는 장점 ( O(1) ) 요소 접근이 느리다는 단점 ( O(n) ) ex . bfs 구현 ( 큐의 요소를 빈번하게 추가하고 제거하기 때문에 요소의 삽입과 삭제가 빠른 LinkedList 를 주로 사용한다. ) PriorityQueue 사용한 큐 생성 Queue queue = new PriorityQueue();요소가 우선순위에 따라서 정렬되어 처리된다는 장점 삽입과 삭제가 비교적 느리다는 단점 ex . 다익스트라 알고리즘 처럼 우선순위가 중요한 경우 ArrayDeque 사용한 큐 생성Queue queue = new ArrayDe..