old/Algorithm Solving (58) 썸네일형 리스트형 LeetCode 191. Number of 1 Bits 자바 문제 풀이 문제 Number of 1 Bits - LeetCode 문제 해결 방법 -이 문제는 프로그래밍 언어에서 바이너리 구조를 알고 있느냐 묻는 문제입니다. -C, C++같은 저급언어라면 이 문제를 반드시 알고 있어야 하지만, 자바에서는 굳이 알아야 할 필요는 없다고 생각합니다. -문제는 unsigned integer이라고 상정하라고 했지만, 자바는 unsigned가 없습니다. -자바의 bitwise operator인 ‘>>>’와 논리게이트인 ‘&’를 알면 쉽습니다. 자바 연산자 & 란 논리게이트인 AND 연산입니다. 1&1이면 1을 반환 1&0 혹은 0&1이면 0을 반환합니다. 자바연산자 >>> 란 비트를 시프트하는 연산자 입니다. 111이라는 비트가 있으면 오른쪽으로 한칸 옮겨서 011이 됩니다. 시간복잡도.. LeetCode 289. Game of Life 자바 문제 풀이 문제 Game of Life - LeetCode 문제 해결 방법 -조건 주위 live cell의 개수가 2보다 작으면 dead 주위 live cell의 개수가 2와 같으면 유지 주위 live cell의 개수가 3과 같으면 live 주위 live cell의 개수가 3보다 많으면 dead -즉 이미 죽었느냐 살았느냐 보다는 주위에 있는 live cell의 개수를 세는게 중요함 -보드의 끝부분에 있을때는 없는 부분에 주의하여, null pointer가 안나도록 해야함. -이미 업데이트된 정보를 다시 검색하지 않으므로, 새로운 2D어레이를 생성해서 사용하는게 좋음. 시간복잡도: O(mn), 공간복잡도: O(mn) https://github.com/eunhanlee/LeetCode_289.GameofLife.gi.. LeetCode 108. Convert Sorted Array to Binary Search Tree 자바 문제 풀이 문제 Convert Sorted Array to Binary Search Tree - LeetCode 문제 해결 방법 -정렬된 어레이를 가지고 바이너리 서치트리에 밸런스 있게 넣는 문제입니다. -이진트리는 밸런스가 맞아야 하므로, 바이너리 서치 트리를 만드는 법을 아느냐고 묻는 문제입니다. 바이너리 서치 트리는 보통 재귀함수를 사용해서 구현합니다. root는 전체 어레이의 중간값을 넣습니다. 왼쪽노드역시 왼쪽부분의 중간값을 넣습니다. 오른쪽 노드 역시 오른쪽 부분의 중간값을 넣습니다. -재귀함수가 아닌 반복문으로 구현할경우, 코드자체가 복잡해지고 이해하기 어렵지만, 오버플로우의 위험성이 사라진다는 장점이 있습니다. 시간복잡도: O(log n), 공간복잡도: O(n) https://github.com/eu.. Seating Arrangement 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 현재 좌석이 비어있고 양쪽에 빈 자리가 있는 경우에만 새로운 사람이 앉을수 있다. 현재 좌석을 차지하면 양쪽에 새로운 사람이 앉을수 없다. possible case 000 100 001 [01 [10 [00 10] 01] 00] 시간복잡도: O(m), 공간복잡도: O(1) class Solution { public static boolean is_possible_to_get_seats(int n, int m, int[] seats) { int possibleSeat = 0; // 가능한 좌석 수를 저장할 변수 for (int i = 0; i < m; i++) { boolean left = false, right = false; // 왼쪽과 오른쪽에 빈 자리가 있는.. LeetCode 131. Palindrome Partitioning 자바 문제 풀이 문제 Palindrome Partitioning - LeetCode 문제 해결 방법 -특정 스트링의 부분문자열 중에서 Palindrome만 찾는 문제입니다. -Palindrome은 앞뒤를 뒤짚어도 똑같은 문자열 혹은 숫자를 뜻합니다. aba → aba -모든 부분문자열을 찾고, 경우의 수들 중에서 Palindrome인 경우만 찾는것입니다. -다만, 굳이 ‘모든’ 부분문자열을 찾을 필요는 없습니다. 앞쪽에서 이미 Palindrome이 아니라면, 나중에 나오는 조합역시 Palindrome이 아니기 때문입니다. -abaabb의 부분문자열 중, abaa이후에 abaab이든 abaabb이든 Palindrome이 될수가 없습니다. -그러므로 부분문자열을 찾는 알고리즘 중, 백트래킹을 사용하여, 이후에 나오는 조합을.. Geek's Village and Wells 문제의 자바 해결 방법: 효율적인 알고리즘 문제 Problem_Link 문제해결방법 모든 W를 찾는다 W에 거리에 따라 H에 표시한다 N과 .의 경우, 0을 표시한다 N에 둘러쌓인 H의 경우 -1을 표시한다 H=8 H=6 H=4 H=6 H=8 H=6 H=4 H=2 H=4 H=6 H=4 H=2 W=0 H=2 H=4 H=6 H=4 H=2 H=4 H=6 H=8 H=6 H=4 H=6 H=8 W에 거리에 따라 H에 표시할때, 하나의 정점에서 시작해서 차례대로 연결된 정점을 하나씩 방문해서 거리를 표시하므로, 이는 문제에서 BFS (Breadth-First Search) 너비 우선 탐색을 사용하라는 것임을 알수 있습니다. 참고: 그래프 탐색: DFS,BFS 트리: inorder, preorder, postorder 시간복잡도: O(nm), 공간복잡도: O(.. LeetCode 230. Kth Smallest Element in a BST 자바 문제 풀이 문제 Kth Smallest Element in a BST - LeetCode 문제 해결 방법 -이진 트리에서 K번째 노드를 출력받는 문제입니다. -이진트리에서 작은수에서 큰수대로 출력하는 방법은 DFS-inorder입니다. -DFS, inorder를 k만큼 반복한후 출력합니다 -다른 노드의 값이 필요하지 않으므로, 재귀함수가 아닌 그냥 반복문을 사용합니다. -Follow up: 이진트리는 기본적으로 검색에 빠르고 수정이 느리므로, 이진트리말고 다른 데이터 스트럭쳐를 쓰는것이 좋습니다. 하지만 반드시 이진트리를 써야한다면, 트리노드를 LinkedList가 아닌 Double Linked List로 구현 값이 아닌 노드를 반환 새로운 값을 insert 이미 가지고 있는 노드에서 이전 노드의 값(새로운 값)을.. LeetCode 238. Product of Array Except Self 자바 문제 풀이 문제 Product of Array Except Self - LeetCode 문제 해결 방법 ”The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.”의 뜻은 곱셈연산시 32비트를 넘어가지 않는다는 뜻입니다. 즉, int를 사용해서 계산을 해도 괜찮습니다. 오버플로우가 일어나지 않습니다. 시간복잡도는 O(n)이여야 합니다. 나누기를 사용할수 없습니다. 문제 자체는 어렵지 않지만, 제약조건떄문에 어려워 지는 문제입니다. 푸는 방법은 다음과 같습니다. 자신을 제외한 왼쪽을 곱한 수를 가진 리스트를 만든다. 자신을 제외한 오른쪽을 곱한 수를 가진 리스트를 만든다. 두 자리수를 곱한다. 즉, 시간복잡도에 대해서 잘.. 이전 1 2 3 4 5 6 7 8 다음 목록 더보기