코딩테스트/백준
-
[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
-
[Dev-Ping9] 백준 1011번 - Fly me to the Alpha Centauri (Java)코딩테스트/백준 2021. 11. 17. 14:38
# 문제설명 x에서 y까지 최소한의 jump 로 가야한다. (02->3->2->1 ) , ( 1->2->3->3->2->2->1 ) 등으로의 jump 방식만 채택할 수 있다. jumpDistance[n] 을 1부터 n까지 계속 증가하고, n부터 1까지 계속 감소하는 clean하게 jump 했을시의 거리로 정의하자. ex) (1->2->1) , (1->2->3->2->1) ... 그리고 가야할 거리가 jumpDistance[n] 를 초과하지 않는 직전의 n을 찾으면, jumpDistance[n] 의 jump를 시행 후, 남은거리를 뭐로든 채워넣으면 되지 않을까? jumpDistance[n]을 살펴보면, 아래의 두가지 정도의 점화식을 찾을 수 있다. [1번] jumpDistance[n] = jumpDista..