본문 바로가기

전체 글156

[백준] 11657번 타임머신 _ Python 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번째 탐색을 할 때 (사이클이 존재하지 않더라도) 최소 거리가 갱신이 된다면, 음의 사이클이 존재한다는 의미이다. [생각] - 벨만포드 알고리즘의 기본 문제 - 어떻게 풀 지 생각이 나지 않는다면, 위의 플로우를 떠올리.. 2024. 1. 8.
3. API 개발 고급 - 지연 로딩과 조회 성능 최적화 목표. 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 해주어.. 2024. 1. 8.
[백준] 1277번 발전소 설치 _ Python 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억이 나오므로 불.. 2024. 1. 7.
[백준] 14938번 서강그라운드 _ Python https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [초기 접근 방법] 1. 어느 위치에 떨어지는 것이 아이템을 가장 많이 얻을 수 있는가? 2. 모든 노드에서 간선에 대한 수색 범위를 펼쳐서 아이템을 얻는 개수를 구해야 한다. → graph[i]를 중심으로 탐색 범위, 'graph[i][j] 2023. 12. 30.
[백준] 11265번 끝나지 않는 파티 _ Python https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net [초기 접근 방법] - M명의 사람들의 출발점이 모두 다르다. → 따라서 플로이드 알고리즘으로 모든 노드 간의 최단거리를 구한다. 1. A 시작점에서 B 지점까지의 최단 경로를 구한다. 2. 위 최단 경로가 C 오픈 시간보다 빠르면 → 파티장에 도착할 수 있다: 길면 → 파티장에 도착할 수 없다. [생각] - 다익스트라나 벨만 포드에 비해, 구현이 직관적이며 간.. 2023. 12. 29.
[백준] 18352번 특정 거리의 도시 찾기 _ Python https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net [초기 접근 방법] - 특정 노드에서 출발하여, 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력 - 특정 노드이므로, bfs 탐색과 다익스트라 알고리즘을 사용할 수 있다. [생각] - bfs로는 금방 풀었지만, 다익스트라 알고리즘 복습하는 문제로 좋았다. [코드] 1) bfs # 풀이 시간 : 20분 # 시간복잡도 :.. 2023. 12. 27.

티스토리툴바