본문 바로가기

전체 글

 (172)
[Leetcode 15/100] Course Schedule - Medium 문제 풀이 방식 Graph에서 Cycle을 찾는 재귀 함수 구현 주의할 점 처음에 findCycle() 함수 설계를 잘못했는데 너무 오래 매달렸다. 초기 설계를 잘하고 아니다 싶으면 바로 포기한 후에 새로운 방식으로 구현하는 것도 하나의 방법일 것 같다. 또한, 그래프에서 Cycle을 찾는 구현 방법을 정확하게 숙지하는 것이 필요할 것 같다. 위상정렬로도 풀 수 있는 문제인데 학습하자 소스코드 class Solution { boolean[] visitied; List graph = new LinkedList(); public boolean canFinish(int numCourses, int[][] prerequisites) { visitied = new boolean[numCourses]; getGra..
[Leetcode 14/100] Find the Town Judge - Easy 문제 풀이 방식 LinkedList로 Graph를 구현하여 풀이 주의할 점 엣지 케이스를 주의 할 것, 시간 복잡도를 신경 쓸 것 그래프 문제를 많이 경험해보지 못해서 순수 구현으로 푼 느낌이다. 다른 discuss를 보고 풀이를 참고해서 다시 풀어봐야 할 것 같음.. 소스코드 class Solution { LinkedList res = new LinkedList(); int sizeFlag = 0; public int findJudge(int N, int[][] trust) { if(N == 1) return 1; makeGraph(N, trust); LinkedList judgeList = findByJundgeList(); if(sizeFlag > 1) return -1; return findByJ..
SpringBoot와 Lombok의 기본 annotation 정리 스프링 프레임워크에서는 다양한 어노테이션 기능을 지원하고 있다. 이 글에서 각 어노테이션이 무슨 의미를 뜻하고 어떠한 기능을 사용자에게 제공해주는지 알아보자! @RestController Controller + ResponsBody 기존의 Controller 어노테이션의 Return 값에 ResponseBody를 적용한 것으로 json으로 결과를 반환한다. 기존의 Controller는 View(화면)을 리턴하고 json 형태의 데이터를 반환할 때 @ResponseBody를 추가해줘야 했는데 이러한 기능을 통합시킨 어노테이션이다. @RequsetMapping Controller 어노테이션이 클래스 위에 선언되었다면 RequestMapping은 클래스 내의 메서드 위에도 선언될 수 있다. 요청된 URL을 어..
[Leetcode 13/100] Minimum Absolute Difference in BST - Easy 문제 풀이 방식 BST의 정렬된 특성 + inorder 재귀 구현 이용 inorder은 left -> selft -> right로 트리를 방문하므로 inorder로 트리를 순회했을 때, 순차적으로 방문할 수 있다. 주의할 점 트리 순회방식인 preorder, inorder, postorder를 이해하자 preorder : slef -> left -> right로 루트가 가장 먼저 나온다 inorder : left -> selft -> right 가장 왼쪽 노드가 먼저 나온다. (BST일 경우 정렬된 결과 볼 수 있음) postorder : left -> right -> root 루트가 가장 늦게 나온다. 소스코드 /** * Definition for a binary tree node. * public c..
[Leetcode 12/100] Maximum Subarray - Easy 문제 풀이 방식 kadane's algorithm을 활용한 풀이 구간의 최대 합을 구하기 위해 사용할 수 있는 알고리즘으로 주요 수식은 아래와 같다. S[i] = Math.max(arr[i], arr[i] + S[i-1]) S 배열은 이 구간까지의 최대 합으로 만약 최대 합보다 현재 인덱스 배열의 값이 크다면 초기화를 시켜주는 방식이다. 주의할 점 브루트 포스 방식으로 모든 배열을 탐색하게 될 경우 O(n^2)의 시간복잡도를 가진다. 그러나 시간을 그만큼 주지 않는 경우가 대부분이므로 O(n)으로 풀어야 success를 받을 수 있다. 소스코드 class Solution { public int maxSubArray(int[] nums) { if(nums.length == 0) return 0; int s..
[Leetcode 11/100] First Bad Version - Easy leetcode.com/problems/first-bad-version/ First Bad Version - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 Binary Search 활용, 이 문제에서는 isBadVersion이라는 API를 제공해주므로 활용해서 풀면 된다. 주의할 점 완전 탐색으로 LInear 시간 만큼 탐색하게 되면 TLE를 볼 수 있다. 소스코드 /* The isBadVersion API is defined in the par..
[Leetcode 10/100] Find the Smallest Divisor Given a Threshold - Medium leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/ Find the Smallest Divisor Given a Threshold - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 이진 탐색을 활용한 구현 주의할 점 문제를 정확하게 이해하는 것이 가장 중요하다고 느꼈다. -> 문제를 한번에 이해하지 못해서 많은 시간이 소모 됨. 완전 탐색으로 시도할 경우 시간복잡도가 10^6 *..
[Leetcode 9/100] Beautiful Arrangement - Medium leetcode.com/problems/beautiful-arrangement/ Beautiful Arrangement - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 방식 DFS를 활용하여 모든 경우의 수를 탐색하여 조건 처리 주의할 점 모든 경우의 수를 탐색하여 마지막에 조건을 처리하게 되면 TLE를 보게 된다. 그러므로 조건을 만족하지 않는 경우 재귀 함수를 호출하지 않도록 조건을 설정하는 것이 필수 소스코드 class Solution { in..

티스토리툴바