https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 핵심 우선 소수를 리스트에 담아야 한다. 그러기 위해서는 소수를 찾아야 하는데, 단순한 방법으로 찾게 되면 너무 많은 시간이 걸리게 된다. 따라서 에라토스테네스의 체를 사용해야 한다. 이를 활용해 투포인트를 사용하면 쉽게 구할 수 있다. 정답 코드 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List List = ne..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이 문제는 부분합과 투포인터를 사용하면 쉽게 풀 수 있다. 핵심 연속된 수를 계속해서 더하다가 합이 원하는 s의 값 이상이 되면 시작점을 한 칸 앞으로 당겨온다. 이후 나머지의 합을 비교하여 계속 s이상이면 다시 시작점을 당기고, 아니면 끝지점을 한 칸 올린다. 자세한 건 코드를 통해 확인해 보자. 정답 코드 import java.io.BufferedReader; import jav..
이번에는 도메인 테스트를 추가하였다. 원래 컨트롤러와 서비스단위에서만 테스트코드를 작성하였는데, 도메인도 추가하였다. 도메인 내에 있는 메서드를 테스트하였다. 코드가 너무 많기 때문에 가장 코드가 길고, 복잡한 Board를 주로 설명하겠다. 기존의 Board이다. Board @Entity @Getter @Builder @NoArgsConstructor(access = AccessLevel.PROTECTED) @AllArgsConstructor public class Board extends BaseEntity { @Id @GeneratedValue(strategy = GenerationType.IDENTITY) @Column(name = "board_id") private Long id; @Column(..
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net dfs를 사용하여 쉽게 풀 수 있다. 핵심 dfs를 사용하면 쉽게 풀 수 있다. 가중치가 있기 때문에 Node라는 클래스를 만들어서 활용하였다. 정답 코드 import java.io.*; import java.util.ArrayList; import java.util.List; public class Main{ static List[] nodes; static boolean[] visited; static int distance; public..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 핵심 DFS를 사용하여 풀 수 있다. 실제 부모와 자식관계의 트리이지만 양방향 매핑을 하는 인접 리스트로 표현하였다. 정답 코드 import java.io.*; import java.util.*; public class Main { static int N; static List nodes[]; static boolean[] visited; static int max; publi..
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 핵심 x + y + z = k 가 돼야 한다. 각각의 원소는 집합에 포함되어 있다. 또한 각각은 같은 값을 가져도 된다. 단순하게 완전탐색으로 풀면 시간복잡도에서 걸리게 된다. (3중 for문) 따라서 이분탐색을 사용하여 더 빠르게 풀 수 있다. x + y = k -z라는 식을 이용하면 된다. 정답 코드 import java.util.ArrayLis..
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 예전에 프로그래머스에서 똑같은 문제를 풀이했던 적이 있다. 이번에는 우선순위 큐를 사용하는 것이 아닌 다른 방법을 사용하였다. 핵심 https://kimtaesoo99.tistory.com/135 [프로그래머스] 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs문제이다. 핵심 1은 벽을 의미하고, 0은 이동할 수 있는 길이다. 만약 벽이 있더라도 1번 부수고 이동할 수 있다. 즉 한 번도 벽을 부수지 않음 -> 벽을 부수고 이동 벽을 이미 부순 경우 -> 이동 불가 가 된다. 하지만 벽을 부수지 않고 이동한 경우가 더 빠를 수도 있다. 따라서 벽을 부수고 탐색하는 경우와 부수지 않고 탐색하는 경우를 가지고 처리해 주었다. ..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net bfs 문제이다. 핵심 이 문제는 시작점이 여러 개인 bfs 문제이다. 시작점이 여러 개라고 해서 크게 달라지는 것은 없다. 각 시작점에서 점차 값을 증가시키면 쉽게 풀 수 있다. 정답 코드 import java.util.*; import java.io.*; public class Main { static int N; static int M; static int[][] map; s..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합 문제이다. 핵심 이 문제는 연속한 합이 입력값 M으로 나누어지는 케이스를 구하는 것이다. 이를 각 배열의 합, 그때의 나머지를 구하면 아래와 같다. index 0 1 2 3 4 5 arr[i] 1 2 3 1 2 sum[i] 1 3 6 7 9 sum[i]%M 1 0 0 1 0 이때 우선 나머지가 0인 곳은 이전까지의 합이라 생각할 수 있으며, ..
