[초기 접근 방법] - 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 체크 → 음의 사이클 유무 파악 → 벨만포드 알고리즘 사용 [생각] 1. '타임머신' 문제 이후 오랜만에 풀었던 벨만포드 알고리즘 문제 2. 어떻게 접근하는지, 풀어야하는지 잊어서 여러 블로그를 참고해서 이해했다. 3. 파이썬에서 float('inf') - int 를 해도 그대로 무한대이다.. 4. 시작 지점과 관계가 없다면, 그저 현재 그래프에서 음의 사이클이 있는지 파악하게 된다. 음.. 일단 타임머신 문제에서 parameter로 1을 넘겼지만, 1 시작 지점과 관계없이 알고리즘이 진행되었다. ( 이 때는, 1 노드 시작을 하려면 "minDis[start] != INF" 를 넣어야 하는지도 인지하지 못했음... ㅎ..

목표. OneToMany 관계 최적화 하기 Order를 조회할 때, OneToMany 관계인 OrderItem(컬렉션)을 조회할 때 성능을 최적화하는 방법 정리. 컬렉션 페이징 조회 최적화 1. ToOne 관계를 모두 fetch join 한다. 2. 컬렉션은 지연 로딩으로 조회한다. (fetch join X) 3. 지연 로딩 최적화를 위해서 hibernate.default_batch_fetch_size / @BatchSize 를 적용한다. - hibernate.default_batch_fetch_size : 글로벌 설정(application.yml) - @BatchSize : 개별 설정 → 컬렉션이나 프록시 객체를 설정한 size만큼, 한번에 IN Query로 조회한다. 1. V1 : 엔티티 직접 노출 ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net [초기 접근 방법] 일단 사이클이 존재하려면 "간선의 개수(E)가 노드의 개수(N) 이상"이어야 한다. 따라서 마지막 N번째 탐색을 할 때 (사이클이 존재하지 않더라도) 최소 거리가 갱신이 된다면, 음의 사이클이 존재한다는 의미이다. [생각] - 벨만포드 알고리즘의 기본 문제 - 어떻게 풀 지 생각이 나지 않는다면, 위의 플로우를 떠올리..

목표. xToOne 관계 최적화 하기 Order를 조회할 때, 지연 로딩이면서 xToOne 관계인 Member와 Delivery를 조회할 때 성능을 최적화하는 방법 정리. 쿼리 방식 선택 권장 순서 1. 우선 엔티티를 DTO로 변환한다. 2. 필요하면 "fetch join"으로 성능을 최적화 한다. 3. 높은 성능이 요구되면 DTO로 직접 조회한다. 4. 마지막으로는 JPA가 제공하는 네이티브 SQL / JDBC Template에서 SQL 직접 사용하자. 1. V1 : 엔티티 직접 노출 문제 1) API 스펙이 변함 : Entity가 변하면 API 스펙이 변한다. 문제 2) '무한 루프' 발생 : 양방향 연관관계인 Member, Order 사이에서 루프에 빠진다. → 한 쪽에 @JsonIgnore 해주어..

https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net [초기 접근 방법] 1. 1번 발전소에서 N번 발전소까지만 가면 된다. 즉, "1"에서 "N"까지의 최소 경로를 구해야 하므로, 다익스트라 알고리즘을 사용한다. 2. 추가 전선의 길이가 최소가 되게끔 이동한다. 이 때, 두 발전소 사이의 전선 길이가 M을 초과해서는 안된다. 2차원 좌표를 그래프로 표현하면 공간 복잡도가 100억이 나오므로 불..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [초기 접근 방법] 1. 어느 위치에 떨어지는 것이 아이템을 가장 많이 얻을 수 있는가? 2. 모든 노드에서 간선에 대한 수색 범위를 펼쳐서 아이템을 얻는 개수를 구해야 한다. → graph[i]를 중심으로 탐색 범위, 'graph[i][j]