문제 https://www.acmicpc.net/problem/5854 알고리즘 Sorting 풀이 $K$번 겹치는 선분의 길이를 구하는 문제입니다. 세그먼트트리 문제에서 직사각형 관련 문제를 풀 때 비슷하게 풀어본 적이 있는 것 같습니다. 주어진 선분을 모두 구한 후 각 선분마다 선분의 왼쪽 점과 오른쪽 점을 구분합니다. 벡터에 넣어 정렬한 후, 만일 현재점이 선분의 왼쪽을 구성하는 점이라면 $psum$값을 1증가시키고 선분의 오른쪽을 구성하는 점이라면 $psum$값을 1감소시킵니다. $psum$은 현재 겹쳐진 횟수를 의미하며 해당 값이 $K$이상일때만 $ans$에 기록하여 문제를 풀었습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #de..
문제 https://www.acmicpc.net/problem/5849 알고리즘 stack 풀이 inversion을 만들지 않는 소의 개수를 구하는 문제입니다. $a_i$를 u, $b_i$를 v라고 하겠습니다. inversion을 만들지 않기 위해서는 u를 기준으로 정렬했을 때, v가 오름차순의 형태를 가져야만합니다. 오름차순을 유지하기 위해 스택을 사용해서 문제를 풀면 됩니다. 스택의 top이 현재 보고 있는 소의 v보다 크다면 이는 inversion을 만들기 때문에 계속 pop을 해주고, 지금까지 확인한 v값들보다 현재 v값이 작다면 현재 v는 inversion을 만들지 않으므로 스택에 push 해주면 됩니다. 아래 코드는 이 해설과는 다른 코드입니다. 풀이만 참고하세요. 코드 #include #de..
문제 https://www.acmicpc.net/problem/5832 알고리즘 Greedy 풀이 겹치는 선분이 있을 때, 해당 구간을 잘라 그리디하게 푸는 문제입니다. $K$ 쌍을 입력받고 선분의 끝점 값을 기준으로 정렬합니다. 현재 보고 있는 선분의 구간이 [u,v] 일 때, 선분들 중 시작점에 있는 값이 v보다 작다면 겹치는 구간이 발생하는 선분입니다. 해당 선분들은 [u,v] 구간을 자를 때 같이 해결이 되므로 $visited$배열을 통해 체크하며 답을 찾으면 쉽게 풀 수 있습니다. $K$쌍이 주어질 때 u>v 일 수도 있으니 u>v라면 swap을 통해 시작점 N >> K; rep(i, K) { int u, v; cin >> u >> v; if (u > v) swap(u, v); vt.emplac..
문제 https://www.acmicpc.net/problem/5872 알고리즘 Greedy 풀이 올바른 괄호문자열을 만들기 위해 몇 개의 문자를 추가해야하는지에 대한 문제와 거의 비슷합니다. 괄호 하나를 뒤집는 것은 두 개의 문자를 추가하는 것과 일치합니다. 왼쪽부터 문자열을 검사하며 만일 닫는 괄호가 더 많아지는 순간에는 바로 해당 괄호를 여는 괄호로 바꿉니다. 문자열 끝까지 검사한 후 괄호쌍이 맞지 않다면 $sum$만큼의 닫는 괄호를 추가해주면 해결가능합니다. 이는 $sum/2$ 횟수만큼 괄호를 뒤집는 것과 일치합니다. 코드 #include #define rep(i, n) for (int i = 0; i s; in..
로그인 인증 게시 글 목록을 회원만 조회하기 위해서는 접근하는 사용자가 데이터베이스 Member 테이블에 있는 사용자인지 확인을 하는 과정을 거쳐야합니다. 이를 위한 비즈니스 컴포넌트를 만든 후, LoginController을 작성해줍시다. Repository와 Service 인터페이스 및 구현에 대한 코드는 생략하도록 하겠습니다. @SessionAttributes("member") @Controller public class LoginController { @Autowired private MemberService memberService; @GetMapping("/login") public void loginView() { } @PostMapping("/login") public String logi..
문제 https://www.acmicpc.net/problem/1887 알고리즘 bitmask 풀이 모든 subset중 특정 subset을 포함하는 여부를 확인하는 문제입니다. $T$제한이 20이므로 비트마스크의 느낌이 팍팍납니다. 현재 subset이 어떠한 subset을 갖고 있는지는 &연산을 통해 바로 확인이 가능합니다. 코드 #include #define rep(i, n) for (int i = 0; i T >> N; rep(i, N) { cin >> cnt; while (cnt--) { cin >> num; num--; cst[i] |= (1
Querydsl 웹 애플리케이션에서 SQL은 개발/운용과정에서 수시로 바뀌게 됩니다. 다양한 검색쿼리를 미리 저장해서 사용하면 비슷한 쿼리들이 많아 관리하기가 어렵습니다. 이를 해결하기 위해 마이바티스에서는 동적 쿼리를 제공합니다. JPA에서는 @Query로 쿼리들을 관리하게 되는데 프로젝트를 로딩하는 시점에서 SQL들이 파싱되어 정적 SQL만 사용가능합니다. 따라서 동적쿼리를 이용하기 위해선 Querydsl을 사용해야합니다. Querydsl을 사용하기 위해 querydsl-apt 와 querydsl-jpa를 추가한 후 버전정보를 삭제해주도록 합시다. 버전을 명시할 경우 스프링부트에서 참조하는 querydsl과 명시한 버전이 맞지 않으면 오류가 발생할 수 있습니다.(https://devbelly.tist..
Repository 스프링 데이터 JPA를 테스트하기 위해 새로운 프로젝트를 만든 후 엔티티 클래스를 작성하도록 합시다. 그 다음으로 Repository 인터페이스를 작성해야하는데 비즈니스 클래스에서는 Repository 인터페이스를 이용하여 실질적인 데이터베이스 연동작업을 하게 됩니다. Repository 인터페이스는 스프링에서 제공하는 네 개의 인터페이스중 하나를 선택하여 사용하면 됩니다. 위 세 개는 스프링 데이터 모듈, 아래 JpaRepsitory는 스프링 데이터 JPA에서 제공하는 인터페이스입니다. 인터페이스들은 공통적으로 두 개의 제네릭 타입을 지정하게 됩니다. 첫 번째는 매핑할 엔티티 클래스를 적고 두 번째는 해당 엔티티의 Id 타입을 적게 됩니다. 일반적으로 인터페이스는 구현할 클래스를 작..
- Total
- Today
- Yesterday
- greedy
- union find
- Suffix Array
- 2-SAT
- bfs
- 이분매칭
- 세그먼트트리
- spring
- implementation
- 이분탐색
- hld
- 스위핑
- knapsack
- 정렬
- sweeping
- Oracle
- SCC
- 펜윅트리
- sorting
- kmp
- 동적계획법
- DP
- 트라이
- dijkstra
- 좌표압축
- dfs
- Segment tree
- spring boot
- Fenwick
- string
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |