자바
숨바꼭질 3 -13529번
풀이 방법 2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다. Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다. 풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다. BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다. 가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node { private int N; priva..
DFS와 BFS - 1260번
풀이 방법 전형적인 bfs, dfs 문제로 풀어보면 둘의 차이점을 잘 알 수 있다. 방문할 수 있는 정저미 여러개인 경우 정점 번호가 작은것을 먼저 방문한다는 조건으로 정렬한번만 해주면 되는 문제 였다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static ArrayList graph = new ArrayList(); static Boolean[] visited; static int N, M, V; static void dfs(int V) { visited[V] = true; System.out.print(V + " "); for (int i = 0; i < graph.get(V).size(); ..
저울 - 10159번
풀이 방법 모든 물건에서 비교 결과를 알 수 없는 물건의 개수를 출력해야 되기 때문에 플로이드-와셜을 사용했다. 일단 비교 결과를 저장할 테이블을 만들고 100으로 채워넣었다. (그냥 비교 할 수 없는 경우를 100 으로 사용했음) 자기 자신과 비교는 0으로 바꿔주었다. 내가 비교하는 수보다 크면 1, 작으면 -1 로 두었다. 플로이드-와셜을 사용해서 두 수를 비교할 때 중간에 낄수 있는 수가 있으면 넣어 주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..
백도어 - 17396번
풀이 방법 다익스트라로 최단 경로를 구하는 문제이다. 최단 경로를 구하는 과정에서 지나간 지점인지 확인할 때 시야가 보이는 지점인지 확인해서 경로를 지나가지 않도록 설정하고 시야가 보이더라도 넥서스라면 경로가 지나가도록해서 최단경로를 구하도록 구현했다. 내 코드 package com.company; import java.io.*; import java.util.*; class Node implements Comparable { private int index; private Long distance; public Node(int index, Long distance) { this.index = index; this.distance = distance; } public int getIndex() { ret..
최단경로 - 1753번
풀이 방법 전형적인 다익스트라 문제이다. 우선순위 큐를 이용한 다익스트라 알고리즘을 구현해서 풀이했다. 2021.10.01 - [분류 전체보기] - 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜) 내 코드 package com.company; import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable { private int distance; private int index; public Node(int index, int distance) { th..
최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜)
최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 단일 출발 최단 경로 : 어떤 하나의 지점에서 나머지 모든 지점으로 경로 단일 도착 최단 경로 : 모든 지점에서 어떤 하나의 지점으로 경로 (간선을 뒤집으면 단일 출발 최단 경로 문제와 같음) 단일쌍 최단 경로 : 모든 지점 쌍들 사이의 최단 경로 BFS 가중치가 없거나 모든 가중치가 동일한 그래프에서 사용 다익스트라 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착 에서 사용 벨만-포드 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착에서 사용 플로이드-워셜 전체 쌍 최단 경로에서 사용 다익스트라 최단 경로 ..
1로 만들기 - 1463번
풀이 방법 생각 DP 문제로 점화식을 생각해야 했다. 일단 0과 1은 0번으로 고정이라서 값을 넣어주었다. Bottom-up 방식으로 2부터 n까지 계산해 주었다. 이전 수에서 1을 더하는 경우를 생각해서 이전 수의 횟수에서 1을 더해주는 경우 2로 나누어 떨이지기 때문에 2로 나눈 수의 횟수에 1을 더하는 경우 3으로 나누어 떨어지기 때문에 3으로 나눈 수의 횟수에 1을 더하는 경우 이 세가지를 비교해서 최솟값을 만들어 주었다. 내 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Mai..
API 개발 고급 - 실무 필수 최적화
API 개발 고급 - 실무 필수 최적화 OSIV(Open Session In View)와 성능 최적화 OSIV와 성능 최적화 Open Session In View: 하이버네이트에선 Seesion Open EntityManager In View: JPA에선 EntityManager (관례상 OSIV라 한다.) OSIV ON spring.jpa.open-in-view : true -> 기본값 WARN 7781 --- [ restartedMain] JpaBaseConfiguration$JpaWebConfiguration : spring.jpa.open-in-view is enabled by default. Therefore, database queries may be performed during view r..
API 개발 고급 - 컬렉션 조회 최적화
API 개발 고급 - 컬렉션 조회 최적화 주문 조회 V1: 엔티티 직접 노출 주문 조회 V2: 엔티티를 DTO로 변환 주문 조회 V3: 엔티티를 DTO로 변환 - 페치 조인 최적화 주문 조회 V3.1: 엔티티를 DTO로 변환 - 페이징과 한계 돌파 주문 조회 V4: JPA에서 DTO 직접 조회 주문 조회 V5: JPA에서 DTO 직접 조회 - 컬렉션 조회 최적화 주문 조회 V6: JPA에서 DTO로 직접 조회, 플랫 데이터 최적화 주문내역에서 추가로 주문한 상품 정보를 추가로 조회하자.(OneToMany)를 조회하고, 최적화하는 방법을 알아보자. Order 기준으로 컬렉션인 OrderItem 와 Item 이 필요하다. 앞의 예제에서는 toOne(OneToOne, ManyToOne) 관계만 있었다. 이번에..
트리의 부모 찾기 - 11725번
트리의 부모 찾기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 27396 11727 8664 42.697% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 예제 입력 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 예제 ..