본문 바로가기

알고리즘26

[자바] Leetcode 268 - Missing Number 문제 배열 nums가 주어지는데, 이때 배열에는 범위 [0,n]에 속하는 n개의 숫자가 담겨있다. 범위가 [0,n]이라면 총 n-1개의 숫자가 있어야하는데, n개만 담겨있다는 건 숫자 한개가 빠져있다는 뜻. 빠진 숫자를 반환하는 문제다. leetcode.com/problems/missing-number/ Missing Number - 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 첫 번째 Solution 쉽게 생각했다. 길이 n을 가지는 boolean 배열을 만.. 2021. 3. 4.

[자바] Leetcode 234 - Palindrome Linked List 최적화된 방법은 아니다. 일단 Linked List를 끝까지 타면서 ArrayList list에 담아주고, 그 list의 양 끝값들을 하나씩 비교해가면서 어긋나는 게 있으면 바로 answer = false를 넣고 나와버린다. Linked List를 순회하는데 걸리는 시간 O(n) + ArrayList의 절반을 순회하는데 걸리는 시간 O(n/2)해서 결국 대략 O(n)이기는 한데, 성능이 하위 70%에 속한다 ㅎ 시간이 빠른 다른 풀이를 보면 두 개의 변수 (fast, slow)를 써서 뭔가를 하는 것 같은데, 이해는 나중에 해야겠다! 처음 제출했을 때, [-129, -129] 케이스에서 Wrong Answer가 나왔다. 일단 잘못 생각했던 점은, 자바를 너무 겉핥기 식으로 했어서 그런지 Integer도 .. 2021. 3. 1.

[자바] Leetcode 100 - Same Tree 어쩌다 면접이 잡혀서 발등에 불떨어진 느낌으로 부랴부랴 문제 푸는중 ㅎ 친구한테 리트코드 추천 받아서 Difficulty Easy단계부터 풀고 있는데, 어렵지는 않다. 하지만 최적화는 정말 끝이 없고, 똑똑한 사람들은 이 세상에 많다는 걸 계속해서 깨닫게 된다. TreeNode 2개를 파라미터로 던져주면 그 2개의 TreeNode들이 동일한지 아니지를 판별하는 메소드를 짜는 문제다. Class TreeNode는 아래처럼 구현되어 있다는 가정하에 메소드 로직만 채우면 된다. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int va.. 2021. 2. 28.

[자바] 백준 2042 - 구간 합 구하기 세그먼트 트리 문제다. 세그먼트 트리는 한 번도 그 어디에서도 들어본 적도 없었는데, 아래 글 읽으니까 어느 정도 이해가 됐다. www.crocus.co.kr/648 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 요청하는 쿼리에 대해 방식이 달라질 수 있으나, 모든 쿼리를 다룰 수 없기에 구간 합에 대한 세그먼트 트리를 정리해 두었습니다. 내용이 길지만 그만큼 자세히 설 www.crocus.co.kr # 세그먼트 트리 - 시간 복잡도 : O(logN) - tree 배열과 array 배열은 다른 데이터다. array 배열은 1부터 N까지의 값이 들어가 있는 배열이라면, tree 배열은 구간합들이 들어가있는 배열이다. 트리의 노드를 각 배열에 대치시킨 것이라고 생각하면 된다.. 2021. 1. 6.

이전 1 2 3 4 5 ··· 7 다음

티스토리툴바