코딩테스트
-
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를 활용해 어떤 간선이..
-
[코드트리 조별과제] 냉방 시스템코딩테스트/코드트리_Java 2024. 8. 4. 21:18
문제 : 냉방 시스템 어려운 알고리즘이 들어가진 않지만 구현 조건이 까다로워서 시간을 많이 쓴 문제이다. 코드는 아래와 같다import java.io.*;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static StringBuilder sb = new StringBuilder(); static int n, m, k, time; static int[][] curCool, nextCool; static boolean[][][] wall; static..
-
[코드트리 조별과제] 산타와 선물 공장 2코딩테스트/코드트리_Java 2024. 7. 27. 23:00
문제 : 산타와 선물 공장 2 2번 기출을 처음 풀어봐서 좀 더 깔끔하게 풀 수 있는 방법이 있어보이는데, 코드가 더러워서 아쉽다.LinkedList를 직접 구현하는 방식으로 풀었다. 코드는 아래와 같다import java.io.*;import java.util.*;public class Main { static class Box { Box prev, next; int idx; } static class Belt { Box head, tail; int cnt = 0; } static StringTokenizer st; static BufferedReader br = new BufferedReader(new InputStre..
-
[코드트리 조별과제] 바이러스 백신코딩테스트/코드트리_Java 2024. 7. 18. 21:06
문제 : 바이러스 백신 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제는 아래와 같다N x N 크기의 도시에 병원, 벽, 바이러스가 있고, M개의 병원에 백신을 제공할 수 있다. 백신이 제공된 병원을 시작으로 매 초마다 상하좌우로 인접한 지역 중 벽을 제외한 지역에 백신이 공급되기 때문에 그 자리에 있던 바이러스 제거M개의 병원을 적절히 골라 최대한 빨리 바이러스를 없애고자 함3 ≤ n(전체 크기) ≤ 501 ≤ m(병원의 수) ≤ 10문제를 봤을 때 전체 x개의 병원 중 m개의 병원을 고른다는 점 에서 조합을매 초마다 상하좌우로 인접한 지역에 백신이..
-
[코드트리 챌린지] 메이즈 러너코딩테스트/코드트리_Java 2023. 10. 9. 20:11
문제 : 메이즈 러너 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 삼성 코딩테스트 대비 기출이라 참고하는 용도 정도로 글을 보면 좋으리라 생각됩니다. 코드는 아래와 같습니다. import java.util.*; import java.io.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringBuffer sb = new StringBuffer(); static StringTokenizer st; ..
-
[코드트리 챌린지] 세 수의 최대 곱(S3)코딩테스트/코드트리_Java 2023. 10. 2. 18:08
문제 : 가장 짧은 부분합 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제는 아래와 같다 원소가 n개 들어 있는 수열에서 특정 구간을 잡았을 때 그 합이 s 이상이 되는 것 중, 가장 짧은 구간의 길이를 구하는 프로그램을 작성해보세요. 첫 번째 줄에 n과 s가 공백을 두고 주어집니다. 두 번째 줄에 수열의 각 원소가 공백을 두고 차례대로 주어집니다. 1 ≤ n ≤ 100,000 1 ≤ s ≤ 109 1 ≤ 원소 값 ≤ 10,000 실력 진단에서 틀린 문제이고 처음 투 포인터를 생각하긴 했지만, 원소 값이 10,000이길래 n^2으로도 풀리리라 생..