본문 바로가기
반응형

전체 글124

[Union Find, Disjoint Set] 유니온 파인드 함수 구현 방법(재귀 사용!) 백준 1717번 문제를 풀 때 UnionFind를 사용하였다. 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Union Find는 그래프알고리즘의 일종으로 여러노드가 존재할 때 각 노드가 연결되어 있는지를 집합을 이용하여 확인하는 방식이다. Union Find를 하기위해서는 크게 3가지의 함수가 필요하다. (꼭 필요한 함수는 2가지 이다) 1. make()함수 - 먼저 각 노드들의 부모노드를 저장할 parents배열을 초기화 시켜준다. (parents 배열을 만드는 .. 2021. 9. 12.
JDBC LIKE http://yoonbumtae.com/?p=2842 JDBC에서 LIKE쓸때 문제점 ?에는 양 옆에 자동으로 ''가 들어가서 변경해주어야한다. 스프링(Spring): JdbcTemplate에서 LIKE 키워드 사용 시 SQL Injection 방지 코드 작성하는 방법 (Mysql, Mariadb) 먼저 아래 코드는 일단 동작하는 코드입니다. 표면적인 문제는 없지만 SQL Injection(이하 인젝션)의 문제점에 노출되어 있습니다. public List findByTitleAndLocale(String keyword, String locale) yoonbumtae.com 2021. 9. 10.
DB SubQuery SubQuery - Query문 내에 작성하는 Query를 SubQuery라고한다. - 기본적으로 외부 Query가 수행되기 전에 SubQuery가 먼저 수행되고 그결과를 외부 Query에서 사용한다. 단, 상호 연관 쿼리는 외부 Query한행에 대해 SubQuery가 수행되므로 SubQuery는 외부 Query의 행 수만큼 수행된다. (단, 성능이 느리기때문에 안쓰는 걸 추천) - 종류 - where절에서 사용하는 단일행, 다중행, 다중열, 상호 연관 subquery - from절에서 사용하는 inline view - 스칼라 서브쿼리(단일행, 단일열)로 조회되는 sub query - sub query가 사용되는 위치 select절, from절, where절, having절, order절 => group.. 2021. 9. 8.
백준 1654. 랜선 자르기 🅰 백준 1654. 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 문제 풀이 나무자르기와 마찬가지로 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다. start값을 1로 설정해주는게 중요하다. 또한 end값을 N개의 랜선 중 최고 길이의 값, mid = (start+end)/2 로 설정해주었다. 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고 for문안에서 각 랜선 / mid를 정수형으로 변환하여 cnt에 더해주었다. height값과.. 2021. 9. 7.
백준 2805. 나무자르기 🅰 백준 2805. 나무자르기 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ✏️ 문제 풀이 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다. start값을 0, end값을 N개의 나무중 최고 높이의 값, mid = (start+end)/2 로 설정해주었다. 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고 for문안에서 각 나무들과 mid의 차이가 0보다 크면 상근이가 가져갈 수 있는 height 값에 더해주었다. height값과 M을 비교.. 2021. 9. 7.
DB Join - 조인은 테이블의 스키마 파악이 정확하게 이루어 져야한다. 어떤 테이블의 어떤 컬럼을 기준으로 해서 조회할지에 대해 먼저 생각하고 계속 연결하면 Join이 된다. Join - 두개 이상의 테이블을 연결해서 Query(질의)하는 것 - 종류 1. 데이터 추출되는 것에 따라서 Inner Join - 조인을 위해 사용하는 비교조건(조인조건)에 맞는 데이터만 조회 => 조인 조건에 맞지 않는 데이터는 조회되지 않는다. - join할때 outer join으로 표시하지 않으면 기본적으로 inner join으로 조회된다. Outer Join - 조인 조건에 맞지 않는 데이터도 조회된다. 2. 비교 조건에 따라서 Equi Join - 비교하는 두 컬럼의 데이터가 정확하게 일치할 경우 조회됨. => 비교 연산자로 = .. 2021. 9. 7.
백준 1992. 쿼드트리 🅰 백준 1992. 쿼드트리 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ✏️ 문제 풀이 영상이 4개로 압축되어 진행되므로 4개의 시작점을 구해서 재귀를 돌려주었다. 또한 출력을 맞춰주기 위해 재귀가 시작되기 전에 "("를 출력해주고, 재귀가 끝나면 ")"를 출력해주었다. ✏️ 소스코드 import java.util.*; import java.io.*; public class Main { static int N; static int tree[][]; public static void main(.. 2021. 9. 6.
백준 11729. 하노이탑 🅰 백준 11729. 하노이탑 ✏️ 문제 풀이 ✏️ 소스코드 package divideandconquer; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; /*sysout을 사용하면 안되고 bufferedwriter를 사용해서 한번에 출력해줘야한다. * 하노이탑의 최소 이동 순서 = 2^N-1*/ public class Main_실버2_11729_하노이탑 { private static int cnt; private static Strin.. 2021. 9. 6.
백준 1780. 종이의 개수 🅰 백준 1780. 종이의 개수 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net ✏️ 문제 풀이 재귀를 이용하여 문제를 풀어주었다. 쿼드트리, 종이자르기 등과 같이 비슷한 문제로 접근하였다. 종이를 9개로 나누기 때문에 9개의 시작점을 찾아서 재귀를 돌려주었고, 첫 시작 값을 비교하여 전부 다 같은 숫자이면 각 숫자에 맞는 변수를 ++해줘서 종이의 개수를 count 해주었다. ✏️ 소스코드 package divideandconquer; import java.util.*; import java.io... 2021. 9. 6.

티스토리툴바