DFS, BFS 배웠다.
살려줘...........
Math.sqrt를 사용하지 않고 제곱근을 구하는 메서드를 작성하기.
바빌로니아 법이란 게 있다길래 그걸 사용해봤다.
double x = 1;
double before = 0;
while (!String.format("%f", 10000 * before).equals(String.format("%f", 10000 * x))) {
before = x;
x = (x * x + num) / (2 * x);
}
return String.format("%.2f", x); 나는 반올림해서 소수 둘째자리를 반환할거니 비교는 넉넉하게 넷째자리까지 비교해봤다.
음... 이 문제는 바빌로니아법을 사용하지 않아도
x를 1씩 늘려가다가 x의 제곱이 num을 넘어가면
x - 1한 후에 0.1씩 늘려가다가 제곱이 num을 넘어가면 ...
이런 식으로 풀 수는 있을 것 같은데.
음... 코테 준비한다고 바빌로니아법 이런 걸 외워야하나.
내가 못 풀 것 같은 수학 문제들이 나올 걸 대비해서 저런 걸 외우고 있어야하진 않겠..지?
너비 우선 탐색Breath First Search : 가까운 정점부터 탐색
즉, 한 정점을 기준으로 같은 레벨에 있는 정점들을 탐색한 후 그 다음 레벨에 있는 정점들을 탐색하는 식으로 탐색한다.
queue를 활용하여 구현한다.
-BFS는 완전탐색을 수행한다.
-최단 경로 탐색에 유리하다.
-큐를 사용하기 때문에 방문한 정점들을 저장하고 있어야 한다. 그래프의 크기가 커지면 메모리 사용이 그만큼 더 커진다.
-그래프의 크기가 크거나(정점의 개수가 많다) 밀도가 높으면(간선의 개수가 많다) 성능이 저하된다.
-시작 정점에서 도달할 수없는 정점은 탐색하지 않는다.
-방문 여부를 체크하는 자료구조를 사용해야 무한 루프를 방지할 수 있다.
깊이 우선 탐색Depth First Search : 하나의 경로를 끝까지 탐색한 후 다음 경로를 탐색
스택 혹은 재귀를 활용하여 구현한다.
-DFS는 완전탐색을 수행한다.
-현재 경로의 정점들만 저장해두면 되니 BFS에 비해 메모리 사용이 적다.
-Cycle을 고려해야한다. 이를 고려하지 않는다면 무한루프에 빠질 수 있다.
-DFS로 찾아낸 경로는 최단 경로가 아닐 수 있다.
-경로의 특징을 저장해야하는 문제는 DFS를 활용해야한다.
-검색 대상 그래프의 크기가 크다면 DFS를 고려해야 한다.
