[Boj_9251] LCS

문제 설명https://www.acmicpc.net/problem/9251 ▸ 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. ▸ 입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. ▸ 출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 📍 문제 정보🥇 문제 레벨 : 골드 1🔔 문제 유형 : 다이나믹 프로그래밍, 문자열💬 풀이 언어 : Java 문제 풀이문제를 풀기 전, 먼저 최장 공통 부분 수열(LCS, ..

• format_list_bulleted Algorithm/BOJ
• · 2023. 9. 20.
• textsms

[Boj_2167] 2차원 배열의 합

문제 설명https://www.acmicpc.net/problem/2167 ▸ 문제2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. ▸ 입력첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M). ▸ 출력K개의 줄에 순서대로 배열의 합..

• format_list_bulleted Algorithm/BOJ
• · 2023. 9. 11.
• textsms

[알고리즘] 유니온 파인드(Union-Find)

유니온 파인드(Union-Find) 유니온 파인드는 트리나 그래프에서 두 노드가 같은 집합(또는 같은 그래프 구성 요소)에 속해 있는지 판별하기 위한 알고리즘이다. 핵심은 두 가지 연산이다.1️⃣ Find 특정 원소가 속한 집합의 대표(루트) 원소를 찾는 연산2️⃣ Union 두 집합을 하나로 합치는 연산 유니온 파인드의 핵심 아이디어각 노드는 자신이 속한 집합의 부모 노드(parent) 정보를 가진다.처음에는 모든 노드가 자기 자신을 부모로 갖는다.union 연산이 수행될 때, 한 집합의 루트 노드가 다른 집합의 루트 노드를 가리키게 된다.이를 통해 트리 형태의 집합 구조가 만들어진다. Find 연산 private static int find(int x) { if (parents[x] == x..

• format_list_bulleted Algorithm
• · 2023. 9. 7.
• textsms