Next dream Next dream

문제링크 : https://leetcode.com/problems/maximal-square/ Submission : https://leetcode.com/submissions/detail/298397463/ Java Source : https://github.com/skysign/WSAPT/blob/master/LeetCode/221.%20Maximal%20Square/src/Main.java 정사각형의 면적을 구하는 문제입니다. 코딩은 Recursive call을 사용해서, 사각형의 면적을 계산하는 방식을 사용해서 풀었습니다. 이중루프를 사용해서, 모든 위치를 방문해서, '1' 인 위치를 찾습니다. Recursive call을 사용해서, 사각형의 면적을 테두리 부분만 1인지 확인합니다. 이중 루프를 ..

루프를 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 ..