결론부터 말하면,

 

아래처럼 코드 처럼 JpaRepository를 상속받은 인터페이스가 있다고 할 때,

public interface BoardJpaRepository extends JpaRepository<BoardEntity, Long>

"BoardJpaRepositoryImpl" 이라는 클래스를 만들면, Spring이 해당 레포지토리의 "커스텀 구현체" 라고 인식합니다.

 

---

 

Spring 스터디를 진행하면서 과제를 받았습니다.

 

과제 내용은 "JDBC 로 간단하게 CRUD 구현하고, JPA로 바꿔보기"

 

저는 순수 JDBC / Spring JDBC / JPA 순으로 구현하려고 했습니다.

 

DB접근 방식만 바뀌고, 동작하는 메서드는 동일하기 때문에

 

BoardRepository 라는 추상화된 레포지토리 인터페이스를 두고, JDBC / Spring JDBC / JPA가 구현하도록 했습니다.

클래스 다이어그램은 아래와 같습니다.

 

JDBC / Spring JDBC 까지 구현할 때는 문제가 없었습니다.

BoardService에서는 BoardRepository에만 의존하고, Profile에 따라 구현체를 주입해주기때문에 Service나 Controller코드에서도 변경이 없었습니다.

 

그런데 JPA로 구현할 때가 문제였습니다.

 

먼저, BoardJpaRepository는 JpaRepository를 상속받게 하였고

public interface BoardJpaRepository extends JpaRepository<BoardEntity, Long> {
    // 필요한 메서드들..
}

 

 

BoardJpaRepositoryImpl 클래스는 아래와 같습니다.

@Profile("jpa")
@Repository
@RequiredArgsConstructor
public class BoardJpaRepositoryImpl implements BoardRepository {

    private final BoardJpaRepository boardJpaRepository;

    @Override
    public Board findById(Long id) {
        return boardJpaRepository.findById(id)
                .map(e -> e.toBoard())
                .orElse(null);
    }
    
    // 기타 BoardRepository 인터페이스 구현...
}

 

 

그런데 위처럼 구현하고 서버를 켰더니..

 

***************************
APPLICATION FAILED TO START
***************************

Description:

The dependencies of some of the beans in the application context form a cycle:

 

문구와 함께

 

 

boardJpaRepositoryImpl 에서 순환참조가 일어난다고 하는 것이었습니다. 제일 처음에 말한 결론을 모른 상태로 문제를 해결하려니 많은 시간이 소요됐습니다.

 

https://docs.spring.io/spring-data/jpa/reference/repositories/custom-implementations.html#repositories.single-repository-behavior

 

Custom Repository Implementations :: Spring Data JPA

The approach described in the preceding section requires customization of each repository interfaces when you want to customize the base repository behavior so that all repositories are affected. To instead change behavior for all repositories, you can cre

docs.spring.io

스프링 공식 문서에서

 

사진과 같은 내용을 확인할 수 있습니다.

결국에는 JpaRepository를 상속받은 인터페이스명 + Impl을 붙인 클래스는 Spring이 자동으로 커스텀 구현체로 감지한다는 것이었고,

BoardJpaRepository프록시를 생성하려고 하니, 커스텀 구현체(BoardJpaRepositoryImpl)를 생성해야 하고, BoardJpaRepositoryImpl는 생성자에서 BoardJpaRepository를 주입받도록 정의되어있으니까, 생성 -> 주입 -> 생성 -> ... 의 무한 루프에 빠지게 되는 것이었습니다.. 단순히 BoardJpaRepositoryImpl 같은 네이밍이 아닌 다른 이름, 저는 BoardJpaCustomRepositoryImpl 로 바꾸어 해결했습니다.

 

굳이 BoardJpaRepositoryImpl를 써야겠다고 하면 공식문서에는 @EnableJpaRepositories 의 repositoryImplementationPostfix 옵션을 바꾸거나, @Bean 팩토리 메서드를 직접 만들라고 합니다.

https://boj.ma/9502/t

 

9502번: Bones’s Battery

 

boj.ma

 

모든 학교 간 이동을 가능하게 하는 최소 배터리 용량을 찾고싶은 문제입니다.

충전은 최대 K번 할 수 있고 시작시 용량이 0이기 때문에 시작할때 반드시 한 번 충전을 해야합니다.

 

용량을 최소한으로 소모하여 이동하는게 이득이기 때문에 어떤 두 정점간 최단경로로 이동하는것이 최적입니다.

 

문제에서 원하는 값은 "최대 K번 충전하여 모든 학교간 이동을 가능하게 하는 충전량의 최소값" 입니다.

완탐을 떠올려 보면

1회 충전 시 충전량이 1일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 2일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 3일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

1회 충전 시 충전량이 4일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

...

1회 충전 시 충전량이 X일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?

처럼 결정 문제로 바꿀 수 있고, 위 결정문제에 대한 정답은 단조성을 보이기 때문에 즉, 특정 용량 이후로는 항상 가능하다는 대답이 나오기 때문에 이분탐색으로 최적화가 가능합니다.

 

모든 정점쌍 간 최단경로를 구해야하고, N이 작기 때문에 플로이드 워셜로 최단경로를 구할 수 있습니다.

 

시간복잡도는 이분탐색으로 가능한 구간에 매 탐색마다 플로이드를 돌리기 때문에

$O(N^3 log_210^{11})$ 이 됩니다.

 

코드 (C++)

#include <bits/stdc++.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define NM 15*15+10
#define MAX 150010
#define BIAS 1048576
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };


int main() {
	fastio;

	int t;
	cin >> t;
	while (t--) {
		int n, K, m;
		cin >> n >> K >> m;
		vector<vector<ll>> dist(n, vector<ll>(n, LINF));

		for (int i = 0; i < n; i++) dist[i][i] = 0;

		for (int i = 0; i < m; i++) {
			ll a, b, c;
			cin >> a >> b >> c;
			dist[a][b] = min(dist[a][b], c);
			dist[b][a] = min(dist[b][a], c);
		}

		for (int k = 0; k < n;k++) {
			for (int i = 0; i < n; i++){
				for (int j = 0; j < n; j++) {
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}

		auto ok = [&](ll x)->bool {
			vector<vector<ll>> tmp(n, vector<ll>(n, INF));
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n;j++) {
					if (i == j) tmp[i][j] = 0;
					else if (dist[i][j] <= x) tmp[i][j] = 1;
				}
			}
			for (int k = 0; k < n;k++) {
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						tmp[i][j] = min(tmp[i][j], tmp[i][k] + tmp[k][j]);
					}
				}
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (tmp[i][j] > K)  return false;
				}
			}

			return true;
		};

		ll l = 0, r = LINF;
		ll ans = r;

		while (l <= r) {
			ll mid = l + r >> 1;
			if (ok(mid)) {
				ans = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		cout << ans << endl;

	}
	

	return 0;
}

 

'알고리즘 문제 풀이' 카테고리의 다른 글

백준 33543 둘이 한 팀  (0) 2025.03.03
백준 2001 보석 줍기  (2) 2024.08.31
백준 17943 도미노 예측  (0) 2024.07.18
백준 7346 유전자 함수  (0) 2024.05.16
백준 23889 돌 굴러가유  (0) 2024.05.16

https://boj.ma/33543/t

 

33543번: 둘이 한 팀

 

boj.ma

문제 요약은

\[
\sum_{i=1}^{N} \max\Bigl( A_i + \text{A증가량}, \; B_i + \text{B증가량} \Bigr)
\]
를 쿼리마다 구하는 문제입니다.

 

당연히 일일히 업데이트 치고, 매번 합을 구하게 되면 시간초과입니다.

$\max(x, y)$ 를 생각해봅시다. $\max(x, y)$ 는  $\max(x, y) = y + \max(x - y, 0)$ 로 나타낼 수 있습니다.

따라서 우리가 구하려는 $ \max( A_i + \text{A증가량}, \; B_i + \text{B증가량})$ 를 바꾸면,

$\max(A_i + \text{A증가량}, B_i + \text{B증가량}) = B_i + \text{B증가량} + \max((A_i + \text{A증가량}) - (B_i + \text{B증가량}), 0)$ 가 됩니다.

따라서 원래 수식을 아래와 같이 나타낼 수 있습니다.

\[\sum_{i=1}^{N} (B_i + \text{B증가량}) + \sum_{i=1}^{N} \max((A_i - B_i) + \text{A증가량 - B증가량}, 0)\]

 

앞쪽 식은 초기 B배열의 전체 합과 쿼리마다 B를 업데이트 칠 때마다 B증가량에 더해주면 $O(1)$에 구할 수 있습니다.

뒤쪽 식은 $(A_i - B_i)$ 를 미리 계산해둔 배열을 만들어두고, 정렬후 누적합 배열을 만들어 줍니다.

이후 각 쿼리마다 A증가량 - B증가량은 $O(1)$ 에 업데이트 하고, $ \sum_{i=1}^{N} \max((A_i - B_i) + \text{A증가량 - B증가량}, 0) $ 을 이분탐색으로 빠르게 구해줍니다.

 

$ A_i - B_i $ 배열을 정렬하고 누적합을 구해놓는다고 했습니다. 순서가 원래 배열의 순서에서 깨지더라도 상관없습니다.

합은 어차피 $A_i - B_i + \text{A증가량 - B증가량}$ 이 0보다 큰것들만 더해지기 때문에 0보다 큰게 몇개인지만 관심가지면 됩니다.

 

 

따라서  $(A_i - B_i) + \text{A증가량 - B증가량}  \geq 0$ 가 되는 $i$를 이분탐색으로 빠르게 찾고, 

$ N - i $ 개 원소에 대해 $ A_i - B_i + \text{A증가량 - B증가량} $ 의 합은  

$$ \text{psum}[N] - \text{psum}[\text{idx}] + \text{(A증가량 - B증가량)}  \times (N - \text{idx}) $$  

으로 나타낼 수 있습니다.

최종 수식은 아래와 같습니다.

\[
\text{sumB} + n \times \text{B증가량} + \left[ (\text{ psum }[n] - \text{ psum }[\text{idx}]) + \text{ (A증가량 - B증가량) } \times (n - \text{idx}) \right]
\]

 

이제 수식대로 구현해주면 됩니다.

 

코드는 생략합니다.

 

 

 $\max(x, y) = y + \max(x - y, 0)$ 아이디어가 중요한것 같습니다.

'알고리즘 문제 풀이' 카테고리의 다른 글

백준 9502 Bones’s Battery  (0) 2025.03.04
백준 2001 보석 줍기  (2) 2024.08.31
백준 17943 도미노 예측  (0) 2024.07.18
백준 7346 유전자 함수  (0) 2024.05.16
백준 23889 돌 굴러가유  (0) 2024.05.16

+ Recent posts