이번 주 목표 및 회고
📢 이번주 목표는 백준 실버1까지 승급하는 것이다. 현재 골드5이다.
이번주 목표를 초과 달성했다. 더욱 더 열심히 해서 알고리즘 주차가 끝날 때에는 골드1까지 가보자
갈수록 알고리즘도 더 어려워진다. 데일리 과제 매일 풀 수 있도록 부단히 노력을 해야겠다.
오늘 스케줄
09:00~09:20 팀 모닝 스크럼09:20~12:00 데일리 과제 문제 풀이
12:00~13:00 점심 식사
13:00~17:00 데일리 과제 문제 풀이
17:00~17:40 팀 코드 선정 회의
18:00~18:20 기술 매니저님과 팀 코드 리뷰
18:20~19:20 저녁 식사
19:20~20:00 산책
20:00~00:00 백준 6문제 문제 풀이
오늘 목표
👉 데일리 과제 모두 풀기
👉 TIL 빠지지 않고 작성하기
👉 백준 6문제 문제 풀이
👉 북 스터디 참여
오늘 한 것
데일리 과제 모두 풀기TIL 빠지지 않고 작성하기백준 6문제 문제 풀이
오늘 못한 것
- 북스터디 참여
알게된 것
⭐ DFS(Depth-first Search)
- 깊이 우선 탐색
- 연결된 노드를 따라서 계속 방문을 한 후에 연결된 노드들이 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색
특징
- 자기 자 신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
- 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 이 알고리즘을 구현할 떄 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. -> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
자바에서의 DFS 구현 코드
방향 그래프 일 때의 DFS 구현 코드
import java.util.*;
class Graph {
private int V; // 정점의 수
private LinkedList<Integer> adj[]; // 인접 리스트
// 생성자
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 그래프에 간선 추가
void addEdge(int v, int w) {
adj[v].add(w);
}
// 주어진 시작 정점에서부터 도달 가능한 정점들을 DFS로 탐색
void DFS(int s) {
// 모든 정점을 방문하지 않은 상태로 초기화
boolean visited[] = new boolean[V];
// DFS를 위한 스택 생성
Stack<Integer> stack = new Stack<>();
// 현재 노드를 방문한 것으로 표시하고 스택에 넣음
visited[s] = true;
stack.push(s);
while (!stack.isEmpty()) {
// 스택에서 정점을 꺼내고 출력
s = stack.pop();
System.out.print(s + " ");
// 꺼낸 정점의 모든 인접 정점을 확인
// 방문하지 않은 인접 정점이 있다면 방문 표시하고 스택에 넣음
for (int v : adj[s]) {
if (!visited[v]) {
visited[v] = true;
stack.push(v);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("정점 2에서 시작하는 그래프의 DFS 탐색:");
g.DFS(2);
}
}무방향 그래프 일 때의 DFS 구현 코드
import java.util.*;
class Graph {
private int V; // 정점의 수
private LinkedList<Integer> adj[]; // 인접 리스트
// 생성자
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 그래프에 간선 추가
void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v); // 무방향 그래프에서는 w에서 v로의 간선도 추가
}
// 주어진 시작 정점에서부터 도달 가능한 정점들을 DFS로 탐색
void DFS(int s) {
// 모든 정점을 방문하지 않은 상태로 초기화
boolean visited[] = new boolean[V];
// DFS를 위한 스택 생성
Stack<Integer> stack = new Stack<>();
// 현재 노드를 방문한 것으로 표시하고 스택에 넣음
visited[s] = true;
stack.push(s);
while (!stack.isEmpty()) {
// 스택에서 정점을 꺼내고 출력
s = stack.pop();
System.out.print(s + " ");
// 꺼낸 정점의 모든 인접 정점을 확인
// 방문하지 않은 인접 정점이 있다면 방문 표시하고 스택에 넣음
for (int v : adj[s]) {
if (!visited[v]) {
visited[v] = true;
stack.push(v);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
System.out.println("정점 0에서 시작하는 그래프의 DFS 탐색:");
g.DFS(0);
}
}
🤔오늘의 반성
- 바쁘다는 핑계로 책을 안 읽고 있다.
- TIL을 늦게 작성했다.
👍 오늘의 칭찬
1. 지각하지 않았다.
2. 깃헙 1일 1커밋 달성
3. TIL을 빠지지 않고 작성했다.
4. 오늘의 데일리 과제 모두 풀었다.
5. 이번주 목표인 백준 골드5을 달성했다.
❗ 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
https://hanghae99.spartacodingclub.kr/reboot
'TIL' 카테고리의 다른 글
| [항해99 취업 리부트 코스 학습일지] 21일차 (0) | 2024.04.10 |
|---|---|
| [항해99 취업 리부트 코스 학습일지] 20일차 (0) | 2024.04.09 |
| [항해99 취업 리부트 코스 학습일지] 17일차 (2) | 2024.04.06 |
| [항해99 취업 리부트 코스 학습일지] 16일차 (0) | 2024.04.05 |
| [항해99 취업 리부트 코스 학습일지] 15일차 (0) | 2024.04.04 |
