코딩테스트
-
[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..
-
[Dev-Ping9] 백준 10757번 - 큰 수 A+B (Java)코딩테스트/백준 2021. 11. 16. 17:49
# 문제 설명 A, B 2^64까지 표현가능 즉, 기본자료형으로는 입력조차 받기 버겁다. (String으로 받아줘야 한다) 단순 구현 문제이다. # 접근 방법 String으로 A와 B를 받은 후, 각 자릿수를 더해 다시 String으로 리턴 해주면 된다. 굳이 클래스를 정의하지 않아도 되나, 필자는 클래스 문법을 한번 더 복습하는 겸, 클래스로 구현했다. Tip1) 초등학교때 배운것처럼 1의 자리부터 덧셈하자..! (즉 계산은 String의 가장 끝 인덱스로 부터 시작한다) Tip2) 10자리수와 10자리수를 더하면 11자리수가 되거나 10자리 수가 된다. # 구현 코드 import java.io.Buf..
-
[Dev-Ping9] 백준 2775번 - 부녀회장이 될테야 (Java)코딩테스트/백준 2021. 11. 16. 16:05
... 다 작성하고 저장을 안했다.... 😥 # 문제 설명 k>=1, n
-
[Dev-Ping9] 백준 2869번 - 달팽이는 올라가고 싶다 (Java)코딩테스트/백준 2021. 11. 16. 12:45
# 문제 설명 달팽이가 귀엽다... 미끄러진다니... 시간제한 0.15 초 이므로 Brute-Force로는 못품 (for문을 돌리는 순간 통과 안될 것) 규칙을 찾자! 이왕이면 식으로 바로 구할 수 있어야 0.15초를 뚫을 것이다. # 규칙 (식) 하루동안 달팽이가 올라가고 미끄러진 높이는 A-B (달팽이의 속력) 정상에 올라서면 -B 가 발생하지 않음 (딱 한번만 B가 제외된다는 뜻) 그럼 올라갈 나무 높이에서 미리 -B를 해주면 됨 (미끄러졌다는 건 올라갈 나무높이가 더 길어졌다는 건데, 더 짧게 만들어주는 것) day = (tree-B) / (A-B) 가 성립 (올림 처리를 해줘야 한다. 9미터를 4의 속도로 올라가면 3일이 걸리기 때문) 아래의 식으로도 유도 할 수 있다. // up = A-B(d..
-
[Dev-Ping9] 백준 1193번 - 분수찾기 (Java)코딩테스트/백준 2021. 11. 16. 11:43
# 문제 설명 시간제한이 0.5초 이므로 Brute-Force 한 방법은 통과될 가능성이 낮다. 그럼 규칙이 있을테니, 규칙을 찾아본다 # 규칙 대각선을 기준으로 Lv 1 ~ Lv N 이라 정의하면, Lv N 의 원소의 갯수는 N개, 분모와 분자의 합은 N+1 이 된다. Lv N의 n번째 원소의 분모는 n이며, 분자는 (N+1) - n 이 된다. 하지만, 문제에서 정의된 규칙에 따라 지그재그로 배열을 만들기 때문에 홀수일때와 짝수일때로 경우를 나눠주면 된다. # 구현코드 (Java) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ static int re..
-
[Dev-Ping9] 백준 13398번 : 연속합 2 (Java)코딩테스트/백준 2021. 11. 8. 21:03
# Description # 어떤 접근 방법이 좋을까? 1. 문제의 답은 최적의 해를 구하는 것 2. 이전의 해를 이용하여, 지금의 해를 구할 수 있는가? (부분 구조가 성립하는가? => Yes) => 1번과 2번 문항을 통해 DP를 적용 시킬 수 있다는 근거를 가지게 되었다. 3. 단순무식하게 풀었을 때 연산량이 많은가? f(a) 를 a 부터 시작한 [연속합2] 의 최대라 정의 했을때, => 1~N , 2~N , 3~N, .... , N~N => O(N^2) 4. 공간의 제약이 많은가, 시간의 제약이 많은가 => Description을 보면, 확실히 시간의 제약이 많다. (시간제한 및 n의 최대값) => 보통 1초에 1억번 연산가능 (N^2 이면, N=100_000일때, 1천억번 연산해야함 => 1천초..