본문 바로가기

분류 전체보기242

[백준] 1477: 휴게소 세우기 - JAVA https://www.acmicpc.net/problem/1477 풀이이분탐색으로 풀어야겠다는 생각이 바로 들지 않았다. 우선순위큐를 이용해 풀어보려고했는데 잘 되지 않아서 구글링의 도움을 받았다. 이분탐색을 하는데 휴게소들 사이의 거리를 기준으로 탐색한다. 이분탐색을 어떤걸 기준으로 하는지 찾는 것이 어려웠다. 휴게소 간 거리이기때문에 left를 1로, right를 l-1로 놓고 진행했다. mid만큼의 거리를 두고 이미 있는 휴게소들 사이에 mid만큼 거리로 몇 개나 더 세울 수 있는지 체크한다. 이렇게 헤아린 개수를 통해 구간을 좁혀나간다.  메모리: 14268KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19.
[백준] 2458: 키 순서 - JAVA https://www.acmicpc.net/problem/2458 풀이1 ~ n번 학생들에 대해 m개의 관계가 주어지는데, 각각의 관계에는 a번 학생이 b번 학생보다 작다는 것을 알려준다. 이 관계들을 이용해 자신이 몇 번째 등수인지 정확히 알 수 있는 사람의 수를 세는 문제이다. 모든 정점끼리 탐색을 해야하기 때문에 플로이드-워셜 알고리즘을 사용했다. 플로이드-워셜은 O(n^3)의 시간복잡도를 갖는다. 핵심 로직은 다음과 같다.for (int k = 0; k i와 k가 연결되어있고, k와 j가 연결되어 있다면, i와 j는 연결되었다고 보는 것이다. 모든 정점끼리 연결 여부를 체크했다면 각 학생별로 연결된 학생의 수가 n-1인지 확인하면 된다.  메모리: 36932KB시간: 604ms언어: Java 11.. 2024. 5. 19.
[백준] 11657: 타임머신 - JAVA https://www.acmicpc.net/problem/11657 풀이도시마다 연결된 줄이 있고, 줄마다 가중치가 있다. 가중치에는 음수값도 있어서 1번도시에서 어떤 도시로 가는 과정에서 무한히 오래 전으로 돌릴 수 있으면 -1을 출력해야한다. 그렇지 않다면 2번~n번 도시까지 가는 가장 빠른 시간을 출력한다. 음수 가중치가 있기 때문에 벨만포드 알고리즘을 사용하는 문제였다. 벨만포드 알고리즘에서는 우선 `정점의 개수 - 1`만큼 루프를 돈다. 먼저 정점의 사이즈만큼 dist 배열을 만들어 출발지를 0으로 설정하고 나머지 값은 INF로 설정한다. `정점의 개수 - 1`만큼 루프를 돌면서 dist의 값이 INF가 아닌 정점에 대해 연결 된 정점까지 걸리는 cost를 최솟값으로 갱신한다. `정점의 개수 -.. 2024. 5. 19.
[백준] 1744: 수 묶기 - JAVA https://www.acmicpc.net/problem/1744 풀이길이 n의 수열이 주어지고, 이 수열의 합을 구하는 문제이다. 수열내의 두 수를 묶어 그 수들을 곱하는 것으로 계산 할 수 있다. `{-1, 2, 1, 3}` 과 같은 수열이 있다면, 2와 3을 묶어 6으로 만들고, `-1 + 1 + 6 = 6` 으로 6이 최대값이 된다. 음수는 같은 음수끼리 곱하거나, 0과 곱할 때 합에서 이득을 볼 수 있으므로 0이하인 것들은 minus 리스트에 담고, 0보다 큰 수들은 plus 리스트에 담았다. 두 리스트를 정렬해서 minus에 있는 것들은 작은 순으로 2개씩 묶고, plus에 있는 수들은 큰 순으로 2개씩 묶었다. 다만, 1의 경우는 `{1, 1}` 의 수열에서 볼 때, `1 + 1` 이 `1 .. 2024. 5. 19.
[자바] Gradle 테스트 코드 제외하고 빌드하기 프로젝트를 진행하며 사이트를 운영하고 있었다. 새벽시간에 자동으로 빌드를 하게 해놨었는데 빌드되는데 시간이 너무 오래걸려서 ec2서버가 뻗어버리는 일이 있었다. ec2서버를 더 좋은 등급으로 업그레이드해도 돼겠지만... 빌드할 때 test코드를 실행하는 것이 배포 시간중 많은 양을 잡아먹고있었기 때문에 이를 해결하기로 했다. gradle을 사용하고 있었고, gradle에서 테스트코드 없이 빌드하는 방법을 찾아 적용했다. 1. build.gradle에 설정 추가하기// build.gradletasks.withType(Test) { enabled = false}2. -x 옵션을 사용해 test 태스크 제외하기gradle build -x test두 옵션 중 하나를 적용하면 빌드 시 test태스크가 제외되.. 2024. 5. 19.
[백준] 8983: 사냥꾼 - JAVA https://www.acmicpc.net/problem/8983 풀이x축에 사냥꾼들의 위치가 주어지고, 동물의 좌표가 x, y 좌표로 주어진다. 사냥꾼의 총의 사정거리가 주어지고, 동물을 몇 마리 잡을 수 있는지 구하는 문제이다. 동물을 기준으로 자신을 잡을 수 있는 사냥꾼이 있는지 판별했다. 동물의 위치로부터 사정거리 내에 있는 x축 위 점의 최소, 최대를 구한다. 이를 left, right로 하고 이분탐색을 통해 사냥꾼의 위치가 이 범위 안에 있는지 확인한다.  메모리: 55416KB시간: 700ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Animal { int x; .. 2024. 5. 19.
[백준] 17471: 게리맨더링 - JAVA https://www.acmicpc.net/problem/17471 풀이구역들이 서로 어떻게 연결되어있는지 주어진다. 구역들을 2개의 그룹으로 나눠, 각각의 인구수의 합의 차가 최소가 되게 해야한다. 그룹들은 서로 연결되있어야한다. 먼저, n개의 지역을 2개의 그룹으로 나눴다. 나눠진 그룹안의 지역들이 서로 연결되어 있는지 체크 후, answer를 갱신해주었다.  메모리: 16012KB시간: 160ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, answer; static int[] population; static ArrayList> graph; static boolean[] sel;.. 2024. 5. 19.
[백준] 16724: 피리 부는 사나이 - JAVA https://www.acmicpc.net/problem/16724 풀이N * M 지도에 U, D, L, R이 주어진다. 각 칸에서 어느 방향으로 한 칸 이동할 수 있는지를 나타낸다. 각 칸에서 이동시키기 편하게 하기 위해 U, D, L, R을 0, 1, 2, 3으로 치환하여 저장했다. 방문처리가 안된 칸에서부터 dfs를 시작하여 이동할 수 있는 칸을 지날때 union메서드를 통해 같은 그룹으로 묶어주었다. 최종적으로 그룹의 수를 구하면 답이 된다.  메모리: 72688KB시간: 560ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, .. 2024. 5. 19.
[스프링] [JPA] 페이징 성능 개선: 커버링 인덱스 페이징 성능을 개선할 방법으로는 NoOffset 페이징, 커버링 인덱스를 사용하는 것이 있다. NoOffset페이징은 페이지 번호를 의미하는 offset을 쓰지않고, 그대신 이전 페이지의 끝부분을 가지고있다가 조회의 첫 부분을 찾을 때 사용하는 것이다. 이 방법은 특정 페이지별로 조회가 안된다는 단점이 있다. 현재 진행중인 프로젝트에서는 해당 방법은 사용할 수 없어서 커버링 인덱스를 사용해 개선했다. 커버링 인덱스란 쿼리를 충족시키는 데 필요한 데이터를 갖고 있는 인덱스를 말한다. 커버링 인덱스를 이용해 출력할 데이터들의 id값을 조회한 후, 해당 id값이 담긴 List를 이용해 데이터를 조회하는 방식으로 구현했다. 이렇게 하면 커버링 인덱스를 구할 때 where, order by, offset, lim.. 2024. 5. 19.
[백준] 24391: 귀찮은 해강이 - JAVA https://www.acmicpc.net/problem/24391 풀이건물을 돌아다닐 때, 서로 연결되어있는 건물은 밖으로 안나가고 이동할 수 있다. 몇 번 밖으로 나와야하는지 구해야한다. 서로 연결된 건물들을 union메서드를 이용해 한 parent로 묶었다. 그렇게해서 i번 건물과 i-1번 건물이 parent가 다르다면 answer을 1증가시켰다.  메모리: 52100KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 19.

티스토리툴바