Next dream Next dream

A - Frog 1을 푸셨다면 충분히 풀 수 있는 문제입니다. \begin{aligned} 문제 정의에 따라서, 2\leq N \leq 10^5 \\ v_i : i 번째\quad 까지도착하는대\quad 도달하는\quad 최소\quad 비용 (0 \leq i < N) \\ h_i 는 각 돌의 이동 비용 \\ v_i = min(abs(h_{i-k}-h_i)+v_{i-k}) \quad 1 \leq k < K \quad and \quad i-k \geq 0 \\ \end{aligned} import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..

Hamiltonian Path / geeksforgeeks.org 주의사항 1 8 이렇게 되어 있어도, 1,8 8,1 2개의 방향 모두 이동 가능함 시작이 항상 1부터가 아니고, 모든 vertex에서 시작할 수 있음 문제 링크 : https://practice.geeksforgeeks.org/problems/hamiltonian-path/0 문제 해설 : https://www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/ 정답 코드 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Hamiltonian%20Path/src/GFG.java import java.util.Scanner; // Ha..

사실 풀기는 어제 저녁에 풀었는대, 오늘 올리네요... 점점 게을러 저서 큰일입니다. ps : 어제 시켰던 삼겹살은 맛있었다는 ㅋㅋ 문제 링크 : https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0 문제 해설 : https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ 정답 자바 소스 : https://github.com/skysign/WSAPT/blob/master/geeksforgeeks.org/Nth%20Fibonacci%20Number/src/GFG.java import java.util.Scanner; // Nth Fibonacci Number / geeksforgeeks..

루프를 3번 사용해서, 모든 부분집합의 곱을 구한 뒤에, 가장 큰 값을 찾는 방식으로 푸는 방법이 있습니다. 하지만 이방법으로는 time limit에 걸립니다. 길이가 1인 부분집합을 구하고 최대값을 구하고 길이가 1일 부분집합을 길이가 2인 부분집합으로 만들기 위해서, 길이가 1인 부분집합의 다음번 수를 곱합니다. 최대값을 구합니다. 3번 ~ 4번을 반복해서, nums와 같은 부분집합을 만들때 까지 반복합니다. 이렇게 구현하면, accpected는 되지만, 그렇게 속도가 빠른 방식은 아니네요. 곱하기만 하기 때문에, 0과 음수의 개수를 고려 해서, 구현하면 보다 빠른 방식찾을 수 있을 것 같습니다. class Solution { public int maxProduct(int[] nums) { int r..

Dynamic Programming을 recurssion으로 사용해서 아래와 같이 풀면, 시간 초과로 failed 이 됩니다. 시간 초과에 대한 자세한 내용은 아래 블로그에 잘 설명되어 있습니다. https://sedew.tistory.com/m/44 입력값 N 의 N+1만큼 메모리를 사용해서, sub problems의 결과를 메모리에 저장해서, 한번 계사한 sub problem은 다시 계산하지 않도록 코딩해보겠습니다. class Solution { public int climbStairs(int N) { if(N < 2) { return N; } int r[] = new int[N+1]; r[0] = 1; r[1] = 1; for(int i=2; i

이번 문제는 간단한 링크드리스트 문제라서, 자세한 설명은 생략하겠습니다. 10이넘은 값을 carry라고 한다면, carry되어서, 다음번 노드에 1을 전달하는 부분 carry가 전달 되어서, 10을 넘겼을 때, 0으로 바꾸고 새노드를 1로 지정하는 부분 이 3가지 부분이 코딩할 때, 주된 포인트 입니다. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode a = l1, b ..

Singleton Pattern을 이해하고 있는지에 대해서 묻는 문제 입니다. import java.io.*; import java.util.*; import java.lang.reflect.*; class Singleton{ private Singleton() {} private volatile static Singleton instance; public String str; static Singleton getSingleInstance() { if(null == instance) { synchronized(Singleton.class) { if(null == instance) { instance = new Singleton(); } } } return instance; } }이렇게 구현하는 것이 가장..