코딩테스트
-
[Dev-Ping9] 백준 1436번 - 영화감독 숌 (Java)코딩테스트/백준 2021. 12. 18. 15:41
# 문제 설명 1666, ... , 5666, 6660, 6661 등의 변칙규칙으로 구현하기 귀찮게 정의되어 있기에, 이게 되나 하고 단순하게 짰다. 주어진 N의 크기도 작고, 시간제한도 2초(2억번 연산가능)로 넉넉한 편이기에 대충 통과 될거 같긴 했지만... 정말로 되네.... 이런거 공들여서 규칙찾기도 시간낭비 같아서 그냥 그대로 마무리했다. # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new..
-
[Dev-Ping9] 백준 1018번 - 체스판 다시 칠하기 (Java)코딩테스트/백준 2021. 12. 18. 12:08
# 문제 설명 N과 M이 50보다 작으며, 시간제한은 2초라 그냥 손에 잡히는대로 풀면 풀리는 문제 # 수행시간 단순 무식하게 접근 했을 때, 8X8 의 비교연산을 (N-7)X(M-7) 번 한다. (그냥 구현만 제대로하면 된다는 뜻) 허나 N과 M의 범위가 커질때를 대비하여 더 나은 성능에 대한 고민을 해보았다. [1X8 블록]을 만들어 옮기면서 비교하면, 추가되는 원소에 대한 비교만 해주면 되기때문에 비교연산이 1X(N-7)X(M-7) 로 줄어드나 Big-O 표기법으로 봤을 때 아무 의미 없을 것이다. 그래서 아무 걱정없이 문제가 시키는대로 구현하기로 했다. # 코드구현 백준(맞힌사람)에서 Java 11 로 검색해서 높은순위에 공개된 코드에는 나처럼 board를 만들지 않는다... boolean 변수 ..
-
[Dev-Ping9] 백준 7568번 - 덩치 (Java)코딩테스트/백준 2021. 12. 14. 11:56
# 문제 설명 덩치 등수를 구하기 위해서는 한 사람이 그 외에 모든 사람과 비교를 해야 하므로, 그저 문제를 잘 이해하고, 그에 따른 구현능력이 필요한 문제인 것 같다. # 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][] human; static void printArr(int[][] arr){ for(int i=0;iq){ return true; } else if(p>x && q>y){ return false; } return true; } public s..
-
[Dev-Ping9] 백준 2231번 - 분해합 (Java)코딩테스트/백준 2021. 12. 14. 10:56
헐... 21등 했어요... 🥺🥺🥺 # 문제설명 [Base Description] 생성자가 여러개 있을 수 있음 -> 모든 경우를 탐색해야 한다 -> 그 중에 가장 작은수를 찾아야함 [N의 최대 값인 1백만으로 가정] >> 찾아지는 생성자(m)은 상당히 큰 수 일 것이 자명 >> 0에서 N까지 탐색하는 방법은 상당히 비효율적 >> 일정범위 이하로는 탐색할 필요가 없을 것이 자명 [어디까지를 탐색범위로 제한할 것인가?] >> N = m + sub(m) >> sub(m) 은 아무리 크더라도, N의 자릿수갯수 * 9 이하 >> sub(m) 을 최대값으로 가정했을때 만족하는 m 이하로는 탐색할 필요가 없음 (반대로 말하면, 해당 m보다 큰값만 탐색하면 됨) # 코드구현 import java.io.Buffered..
-
[Dev-Ping9] 백준 2447번 - 별 찍기 - 10 (Java) [DP]코딩테스트/백준 2021. 11. 24. 19:51
하하하하하핳하하하 풀었다 이 말이야 하하하하하하!!!! 😘 # 문제 설명 입력은 3^1 에서 3^7까지 이다. [작은 사각형부터 k=1, k=2, k=3] # 규칙 찾기 k=1 인 사각형을 만들 수 있다면, k=2 를 만들때 k=1을 사용하면 될 것 같은 느낌이다. 즉, k=1인 사각형을 dp[1]이라 부른다면, dp[2]는 8개의 dp[1] + 중앙이 빈 형태이다. k=n 일때의 사각형을 만들려면, k=n-1 사각형의 크기가 9개가 필요하다...! 그리고 9개 중, 5번째 사각형은 공백이어야한다. String으로 저 로직을 처리하려면, 개행문자 때문에 상당히 복잡하다. (한번 해봤다가 피봤다...) 그리고 이전의 부분구조가 다음의 부분구조에 쓰이므로 DP문제임이 암시되기에, 배열로 선언하고 사용하는게 ..
-
[Dev-Ping9] 백준 11653번 - 소인수분해 (Java)코딩테스트/백준 2021. 11. 22. 18:32
# 문제설명 소수찾기 알고리즘을 구현해봤다면, 약수들의 중간값인 sqrt(n) 까지만 돌리면 된다는 것을 알고 있을 것이다. 그럼 구현만하면 끝 # 코드 구현 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..
-
[Dev-Ping9] 백준 9020번 - 골드바흐의 추측 (Java) (N을 2개의 수의 합으로 표현하기)코딩테스트/백준 2021. 11. 19. 15:15
# 문제 설명 수학적 지식을 배워가는 좋은 문제다... (.. 😇) 수에 대한 센스가 있느냐가 코딩시간과 수행시간을 압도적으로 단축시킨다. 모든 경우의 수를 검색하여, 그중에 또 작은 경우를 찾는 바보가 저 말고 또 있으실까... ㅎ..ㅎ... (근데 통과는 됨..) # 문제 풀이 입력으로 들어오는 N은 짝수이며, 어떠한 짝수를 두수의 합으로 나타내는 모든 경우의 수를 찾는 방법은 해당 짝수를 2로 나눈 뒤, 한쪽에는 + a 다른 한 쪽에는 -a를 취하는 방법이다. [*기초..기초..] N = (N/2 - a) + (N/2 + a) 이 방법은 항상 만족하며, case를 빠트리는 경우도 없다. 즉, 해당 로직으로 가장 빨리 발견하는 두 소수의 조합이 최소의 차를 가지는 골드바흐 파티션이다. # 구현 코드 ..
-
[Dev-Ping9] 백준 1978번 - 소수찾기 (Java)코딩테스트/백준 2021. 11. 17. 15:08
* 1은 소수가 아니다. 😨 * 약수가 있냐 없냐 찾는 것이기 때문에 주어진 숫자의 1/2 범위까지만 검색하면 된다. * 사실 약수의 중간값은 주어진숫자에 루트를 씌우는 거란다. ㅎㅎ;;;; * 수알못은 퇴근하겠습니다. # 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class test{ static boolean isPrime(int num){ for(int i=2; i