Develog

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 제출한 답안 package BOJ; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BOJ_1260 { // 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000) private static int[][] graph = new int[1001][1001]; // 방문 여부..

🎯 아이템 80. 스레드보다는 실행자, 태스크, 스트림을 애용하라. java.util.concurrent 두둥등장 실행자 프레임워크라고 하는 인터페이스 기반의 유연한 태스크 실행 기능을 담고 있음 ExecutorService exec = Executors.newSingleThreadExecutor(); exec.execute(runnable); exec.shutdown(); 🎯 아이템 81. wait와 notify보다는 동시성 유틸리티를 애용하라. wait와 notify는 올바르게 사용하기가 아주 까다로우니 고수준 동시성 유틸리티를 사용하자! java.util.concurrent의 고수준 유틸리티의 세 범주 1️⃣ 실행자 프레임워크 2️⃣ 동시성 컬렉션 3️⃣ 동기화 장치 1) 실행자 프레임워크는 앞에서..

LCA(Lowest Common Ancestor)란, 트리 상에서 두 노드의 가장 가까운 공통 조상 노드를 의미합니다. 이를 구하는 방법으로는 여러가지가 있지만, 가장 일반적인 방법은 최소 공통 조상을 찾는 알고리즘 중 하나인 Tarjan's off-line algorithm을 이용하는 방법입니다. Tarjan's off-line algorithm은 DFS(Depth-First Search)를 이용하여 각 노드의 부모 노드와 깊이(depth)를 구하고, 두 노드의 깊이가 같아질 때까지 각 노드를 끌어 올리며 공통 조상을 찾는 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(N+Q)로, N은 노드의 개수, Q는 쿼리의 개수입니다. LCA using Tarjan's algorithm ( with Javasc..

깊이 우선 탐색 (DFS, Depth-First Search) 깊이 우선 탐색(Depth First Search, DFS)은 가장 기본적인 완전 탐색 알고리즘으로, 재귀를 이용하면 쉽게 구현할 수 있습니다. DFS는 탐색 공간이 제한되어 있고, 탐색 공간 내 탐색 목표가 있는지 검사할 때 유용하게 사용됩니다. DFS ( with Java ) import java.util.Stack; class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i

LIS(Longest Increasing Subsequence)란 주어진 배열에서 가장 길게 증가하는 부분 수열을 찾는 문제입니다. 즉, 주어진 배열에서 임의의 숫자 i에서 j로 갈 수 있을 때 i arr[j] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } } for..

🎯 아이템 79. 과도한 동기화는 피하라. 응답 불가와 안전 실패를 피하려면 동기화 메서드나 동기화 블록 안에서는 제어를 절대로 클라이언트에 양도하면 안된다. 동기화된 영역을 포함한 클래스 관점에서는 이런 메서드는 모두 바깥 세상에서 온 외계인이므로 예측할 수 없는 이슈를 발생 시킨다 잘못된 코드. 동기화 블록 안에서 외계인 메서드를 호출한다. public class ObservableSet extends ForwardingSet { public ObservableSet(Set set) { super(set); } private final List observers = new ArrayList(); public void addObserver(SetObserver observer) { synchronize..