『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
기능 | 특징 | 시간복잡도 |
---|---|---|
그래프 완전 탐색 | * 재귀 함수로 구현 * 스택 자료구조 이용 | O(V+E) |
private static void mySource() throws IOException {
...
boolean[] visited = new boolean[N];
// 인접 리스트
ArrayList<Integer>[] array = new ArrayList[N];
for (int i = 0; i < array.length; i++) {
array[i] = new ArrayList<Integer>();
}
for (int i = 0; i < M; i++) {
int node = 노드;
int next = node와 연결된 노드;
// 방향 없는 그래프므로 양쪽 노드에 모두 연결
array[node-1].add(next-1);
array[next-1].add(node-1);
}
// 탐색 돌면서 연결 요소 카운팅
int count = 0;
for (int i = 0; i < array.length; i++) {
// 방문한 적 없으면 탐색 시작
if(!visited[i]) {
count++;
myDFS(visited, array, i);
}
}
System.out.println(count);
}
private static void myDFS(boolean[] visited, ArrayList<Integer>[] array, int i) {
// 방문한 적 있으면 탐색 종료
if (visited[i]) {
return;
}
// 방문했으므로 표시
visited[i] = true;
// 인접 노드 탐색
for (int node : array[i]) {
myDFS(visited, array, node);
}
}
기능 | 특징 | 시간복잡도 |
---|---|---|
그래프 완전 탐색 | * FIFO 탐색 * Queue 자료구조 이용 | O(V+E) |
private static void BFS(int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {i, j});
while (!queue.isEmpty()) {
int now[] = queue.poll();
visited[i][j] = true;
for (int k = 0; k < 4; k++) {
int x = now[0] + dx[k];
int y = now[1] + dy[k];
if (x >=0 && y>=0 && x<N && y<M) {
if (A[x][y] != 0 && !visited[x][y]) {
visited[x][y] = true;
A[x][y] = A[now[0]][now[1]] + 1;
queue.add(new int[] {x, y});
}
}
}
}
}
기능 | 특징 | 시간복잡도 |
---|---|---|
타깃 데이터 탐색 | 중앙값 비교를 통한 대상 축소 방식 | O(logN) |
int start = 0;
int end = A.length -1;
while (start <= end) {
int mid_index = (start + end) / 2;
int mid_value = A[mid_index];
if(mid_value > target) {
end = mid_index-1;
}
else if (mid_value < target) {
start = mid_index+1;
}
else {
find = true;
}
}