Develog

문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 제출한 답안 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_1520 { private static int H,W; private static int[][] map, dp; private static final int[] dx = {..

문제 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]; // 방문 여부..

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..

해시테이블과 해시맵은 기본적으로 동일한 개념을 가지고 있습니다. 해시테이블은 데이터를 저장하는 자료구조 중 하나로, 키 (Key)와 값(Value)으로 이루어진 데이터를 저장하고 검색하는데 사용됩니다. 키를 이용하여 값에 접근하므로, 데이터를 빠르 게 검색할 수 있습니다. 해시맵은 자바의 컬렉션 프레임워크에서 제공하는 클래스 중 하나로, 해시테이블을 구현한 클래스입니다. 즉, 해시맵은 해시테 이블의 일종으로, 기본적인 개념과 사용 방법은 동일합니다. 하지만 해시맵은 해시테이블보다 좀 더 최적화된 구조와 알고리즘을 사용하여 보다 높은 성능을 제공합니다. 해시맵은 동기화 된(Synchronized) 버전과 동기화되지 않은(Unsynchronized) 버전이 존재하며, 동기화된 버전은 멀티스레드 환경에서 안 ..