코딩테스트/백준_Java
-
Q. 1981 자바 : 배열에서 이동코딩테스트/백준_Java 2025. 5. 25. 23:48
Q. 1981 자바 : 배열에서 이동 문제 : boj.kr/1981P5 난이도의 문제이다. 문제를 간단히 설명하자면그래프가 주어지고 1,1 ~ n,n까지 이동하려고 할 때, 거쳐간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 문제이다.처음에 이분 탐색과 BFS를 활용한 방식으로 풀었고 아래와 같이 풀었지만 틀렸다.1. 거쳐간 수들의 (최댓값-최솟값) = mid로 정의한다.2. BFS 방식으로 이동하며 mid가 가능한지 조회한다.3. 조건에 따라 이분탐색 방식으로 mid의 범위를 좁혀나간다이 방법은 잘못된 방식이었다.static boolean determination(int mid) { visit = new boolean[n][n]; Queue que = new ArrayDeq..
-
Q. 16566 자바 : 카드 게임코딩테스트/백준_Java 2025. 5. 18. 22:55
Q. 16566 자바 : 카드 게임 문제 : boj.kr/16566P5 난이도의 문제이다. 문제를 간단히 설명하자면카드 더미가 주어진다. 이 때 상대는 나와 동일한 카드 더미를 가진다.그리고 상대의 카드가 주어질 때 상대의 카드보다 크면서 이전에 낸 적 없는 가장 작은 카드를 출력하는 문제이다.먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.1. 상대의 카드보다 크면서 이전에 낸 적 없는 카드 중 가장 작은 카드를 카드 더미에서 찾는다.2. 사용한 카드는 사용했다고 처리한다.3. 1~2 과정을 반복한다. 이렇게 푼다면 낼 수 있는 카드를 찾을 때 N^2번의 연산이 생기고, 이전에 낸 적 없는 카드를 찾는데 최악의 경우 N번의 연산이 생기므로 총 N^3 * K의 시간복잡도를 가지게 된..
-
Q. 3197 자바 : 백조의 호수코딩테스트/백준_Java 2025. 5. 11. 23:54
Q. 3197 자바 : 백조의 호수 문제 : boj.kr/3197P5 난이도의 문제이다. 문제를 간단히 설명하자면얼음, 물, 백조가 있고, 물과 인접한 얼음은 시간이 지날 때 마다 물로 변한다.백조는 물이 있는 영역으로만 지나다닐 수 있을 때, 두 백조가 만날 수 있는 최소 시간은 몇초인지 구하는 문제이다.먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.1. 물 근처의 얼음을 완전탐색을 활용해 녹인다.2. 녹인 후 백조가 만날 수 있는지 계산한다.3. 만약 백조가 만날 수 없다면 1, 2번 과정을 반복한다. 이렇게 푼다면 R, C의 범위가 1500이므로 R^2 * C^2의 시간복잡도를 가지고,시간제한은 2초이므로 이 방법은 불가능해 보였다.그래서 완전 탐색이 아닌 다른 방법을 생각해..
-
Q. 1637 자바 : 날카로운 눈코딩테스트/백준_Java 2025. 3. 2. 23:32
Q. 1637 자바 : 날카로운 눈 문제 : boj.kr/1637P4 난이도의 문제이다. 문제를 간단히 설명하자면 n개의 입력이 주어지고 입력마다 a, c, b가 주어진다.각각의 입력에 대해 a, a + b, ... a+kb(a + kb 특정한 정수 하나만 홀수개 존재한다면 그 정수와 몇개 존재하는지를 구하는 문제이다. 예를들어 아래와 같이 입력이 주어졌다면41 10 14 4 11 5 16 10 1첫 번째 입력은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10의 정수 더미를두 번째 입력은 4세 번째는 1, 2, 3, 4, 5네 번째는 6, 7, 8, 9, 10을 의미한다. 이를 모두 합치면 정수 4가 3개 존재하므로 4 3을 출력하면 된다.먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을..
-
Q. 5719 자바 : 거의 최단 경로코딩테스트/백준_Java 2025. 1. 26. 23:47
Q. 5719자바 : 거의 최단 경로 문제 : boj.kr/5719P5 난이도의 문제이다. 문제를 간단히 설명하자면 거의 최단 경로를 찾는 문제이고거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 거의 최단 경로를 찾기 위해서는 먼저 최단 경로를 찾아야 한다.그리고 경로 추적을 이용해 어떤 간선을 통해 최단 경로에 도달했는지 파악하고 해당 간선들을 끊어준 뒤다시 최단 경로를 계산하면 거의 최단 경로를 구할 수 있다.아래와 같은 방식으로 풀었다. 0. 입력값에 대해 정방향 그래프와 더불어 역방향 그래프를 저장한다.1. 시작점으로 부터 정방향 그래프와 다익스트라 알고리즘을 활용해 최단 경로를 계산한다.2. 도착점에서 역방향 그래프와 BFS를 활용해 어떤 간선이..
-
Q. 25758 자바 : 유전자 조합코딩테스트/백준_Java 2023. 8. 16. 23:27
문제 : 유전자 조합 실버 1 난이도의 문제이다. 유전자가 주어지고 이를 조합한다. 두 유전자를 조합하면 첫 번째 유전자의 첫 번째 형질(글자)와 두 번째 유전자의 두 번재 형질(글자)가 붙는다 주의해야 할 점은 들어오는 입력값은 최대 10만개이지만 실제로 유효한 값은 AA - ZZ, 중복 최대 1개 => 26 * 26 * 2 = 1352개이므로 중복 처리가 필요하다. 아래와 같은 방식으로 풀었다. 1. 유전자들을 Set에 저장하되, 중복을 한 번은 허용해야 하므로 만약 중복된 값이 들어온다면 중복 값들을 저장한 Set에 추가한다. (두 번 까지만 고려하면 된다) 2. 유전자들을 문제 조건에 따라 섞는다. 이 때 중복해서 들어온 유전자를 따로 처리하면 시간을 좀 더 줄일 수 있다 3. 문제 조건에 따라 ..
-
Q. 15657 자바 : N과 M(8)코딩테스트/백준_Java 2023. 4. 25. 23:29
Q. 15657 자바 : N과 M(8) 문제 : boj.kr/15657 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열 - 같은 수를 여러 번 골라도 된다. - 고른 수열은 비내림차순이어야 한다. - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 수열에서 원소를 선택할 때는 중복을 허용하지만, 수열은 중복하면 안된다.주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를..
-
Q. 15654 자바 : N과M(5)코딩테스트/백준_Java 2023. 4. 24. 22:59
Q. 15654 자바 : N과M(5) 문제 : boj.kr/15654 실버 3 난이도의 문제이다. N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. - N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제이다. 주의해야 할 점은 수열은 사전 순으로 증가하는 순서로 출력한다 라는 내용 때문에 수열을 입력 받은 뒤 정렬이 한번 필요하다. 이 문제는 백트래킹과 재귀함수를 이용해 풀었고, 이전 계산한 결과를 배열에 저장하고, 깊이가 최대일 때 까지 탐색을 완료하면 저장한 결과를 출력하는 방식으로 풀었다. 시간 복잡도를 계산하면, M과 N이 최대 8이므로 1. 계산 - O(N^M) 2. 출력 - O(NM) ..