새발블로그

디버깅의 핵심디버깅의 목적은 코드가 실제로 어떻게 동작하고 있는지 이해하는 것특정 시점에 변수 값이 어떻게 변하고 있는지어떤 조건에서 코드의 흐름이 바뀌는지어느 부분에서 예상과 다른 결과가 나오는지이러한 점들을 파악하기 위해 출력문을 적절한 위치에 추가하는 방식이 효과적..디버깅을 효과적으로 하는 방법문제가 생긴 부분부터 출력해 보기예상과 다르게 동작하는 지점에 System.out.println() 등을 추가해 직접 확인변수의 변화 과정을 추적모든 값을 출력할 필요는 없고, 문제 해결에 필요한 값만 선별적으로 확인BFS에서 디버깅 적용하기디버깅 포인트큐(queue)의 현재 상태현재 방문 중인 노드다음에 방문할 예정인 노드방문한 노드 목록public static void bfs(Map> graph, int..

DFS & BFS를 활용한 네트워크 개수 찾기1. 네트워크란?네트워크는 서로 연결된 노드들의 집합노드 A에서 B로 직접 또는 간접적으로 도달할 수 있다면 같은 네트워크로 간주한다.연결이 전혀 없는 노드는 단독 네트워크로 취급된다.결국 네트워크 개수를 구한다는 것은 연결된 그룹의 수를 세는 것!2. DFS와 BFS의 공통점DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 모두 그래프 탐색 알고리즘이다.특정 노드에서 출발해 연결된 모든 노드를 방문한다.한 번의 DFS/BFS 실행으로 하나의 네트워크 전체를 탐색할 수 있다.이 특징을 이용하면 방문하지 않은 노드에서 DFS/BFS를 시작할 때마다 새로운 네트워크를 찾을 수 있다.3. 네트워크 개수 구하는 로직핵심 아이디어DFS/BFS 한 번 실행 = 하나의..

1. 그래프 구성List> graph = ArrayList() {{ add(List.of(1, 3, 6)); add(List.of(0, 3)); add(List.of(3)); add(List.of(0, 1, 2, 7)); add(List.of(5)); add(List.of(4, 6, 7)); add(List.of(0, 5)); add(List.of(3, 5));}};2. Setimport java.util.*;public class BFS { public void bfs(List> graph, int startVertex) { // 시작점 예약 Queue queue = new LinkedList(); Set visite..

1. 그래프 구성List> graph = ArrayList() {{ add(List.of(1, 3, 6)); add(List.of(0, 3)); add(List.of(3)); add(List.of(0, 1, 2, 7)); add(List.of(5)); add(List.of(4, 6, 7)); add(List.of(0, 5)); add(List.of(3, 5));}}; 2. Setimport java.util.*;public class DFS { public void dfs(List> graph, Set visited, int curVertex) { visited.add(curVertex); for (int nextVertex : g..

인접 행렬로 그래프 다루기그래프를 표현하는 방식 중 하나인 인접 행렬(Adjacency Matrix) 은 이차원 배열을 통해 노드 간 연결 여부를 표현한다.int[][] graph = { {0, 1, 0, 1, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 1}, {1, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 1, 0, 0}}; 1. 인접 행렬 그대로 사용하기인접 행렬에서는 graph[i][j] == 1이면 노드 i와 노드 j가 연결되..

실전 그래프 구현: Map 기반 인접 리스트그래프를 다룰 때 가장 효율적인 표현 중 하나는 인접 리스트(Adjacency List)이다.자바에서 Map> 형식을 사용해 인접 리스트를 구성하고, 실전 문제에서 활용하는 방법을 보여준다.1. 인접 리스트를 Map으로 표현하기자바에서는 각 정점과 그에 연결된 정점들을 Map에 저장하는 방식으로 인접 리스트를 표현할 수 있다.예시 코드Map> graph = new HashMap() {{ put(0, List.of(1, 3, 6)); put(1, List.of(0, 3)); put(2, List.of(3)); put(3, List.of(0, 1, 2, 7)); put(4, List.of(5)); put(5, List.of(4, 6,..

그래프의 실전 구현 - 인접 리스트 (Adjacency List)그래프를 컴퓨터 메모리 상에 표현하는 방법 중 가장 자주 사용되는 방식이 인접 리스트(Adjacency List) 이다.이 방식은 메모리 효율이 높고, 연결된 노드들만 저장하기 때문에 희소 그래프(Sparse Graph) 에 특히 유리하다.1. 인접 리스트란?인접 리스트는 각 정점마다 연결된 정점들의 목록을 따로 저장하는 구조입니다. 자바에서는 이를 List> 형태로 구현한다.아래는 8개의 정점을 갖는 무방향 그래프를 인접 리스트로 표현한 코드입니다:List> graph = new ArrayList() {{ add(List.of(1, 3, 6)); // 정점 0 add(List.of(0, 3)); // 정점 1..

그래프의 순회 (Graph Traversal)그래프 순회는 그래프의 모든 정점을 한 번씩 방문하는 과정대표적인 방식은 너비 우선 탐색(BFS) 과 깊이 우선 탐색(DFS) 이 있다.1. 너비 우선 탐색 (BFS: Breadth-First Search)BFS는 가까운 정점부터 차례로 탐색해 나가는 방식큐(Queue) 자료구조를 이용해 구현한다.BFS 알고리즘 흐름1. 시작 정점을 큐에 추가2. 큐가 빌 때까지 다음을 반복 2-1. 큐에서 정점 꺼내 방문 2-2. 연결된 미방문 정점을 큐에 추가Set 사용 Map> graph = Map.of( 0, List.of(1, 3, 6), 1, List.of(0, 3), 2, List.of(3), 3, List.of(0, 1, 2, ..