본문 바로가기
반응형

전체 글

 (237)
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(..
backtracking 알고리즘이란? 정의 Backtracking 알고리즘은 가능한 모든 해를 탐색하면서 최적의 해를 찾는 방법입니다. 백트래킹은 결정 문제(Decision Problem)를 해결하는 알고리즘 기법 중 하나로, 모든 가능한 후보 해를 탐색하면서 해를 찾는 방법입니다. 결정 문제란 "예" 또는 "아니오"로 답할 수 있는 문제를 말합니다. 백트래킹은 모든 가능성을 조사하되, 불필요한 경로는 미리 차단하여 실행 시간을 줄이는 효율적인 기법입니다. 구조 Backtracking은 재귀적인 접근 방식을 사용합니다. 후보 해를 선택하고 유효성을 검사한 후, 유효한 경우 해를 저장하거나 결과를 처리합니다. 그 다음 단계로 진행하고, 문제를 더 작은 부분 문제로 축소하여 재귀적으로 해결합니다. 불가능한 상황이 발생하면 이전 단계로 돌아가서 ..
부분문자열과 순열, 그리고 조합의 차이점, 경우의 수란? 부분 문자열 (Substring) 부분 문자열은 원래 문자열의 연속된 일부 문자를 의미합니다. 부분 문자열은 원래 문자열에서 문자들을 선택하거나 선택하지 않고 구성될 수 있습니다. 원래 문자열의 순서를 유지하면서 문자들을 연속적으로 선택하거나 제외하여 만들 수 있는 모든 가능한 문자열을 말합니다. 예를 들어, "abc"라는 문자열의 부분 문자열은 ””, "a", "b", "c", "ab", "bc", "ac", "abc” 입니다. The length of the string (n) is n Total substrings = n * (n + 1) / 2 순열 (Permutation) 순열은 원래 문자열의 문자들로 만들 수 있는 모든 가능한 순서를 가지는 문자열입니다. 즉, 원래 문자열의 문자들을 모두 사용..
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)이여야 합니다. 나누기를 사용할수 없습니다. 문제 자체는 어렵지 않지만, 제약조건떄문에 어려워 지는 문제입니다. 푸는 방법은 다음과 같습니다. 자신을 제외한 왼쪽을 곱한 수를 가진 리스트를 만든다. 자신을 제외한 오른쪽을 곱한 수를 가진 리스트를 만든다. 두 자리수를 곱한다. 즉, 시간복잡도에 대해서 잘..
LeetCode 215. Kth Largest Element in an Array 자바 문제 풀이 문제 Kth Largest Element in an Array - LeetCode 문제 해결 방법 -k번쨰로 큰 수를 찾는 문제 -내림차순(큰수부터 작은수)으로 정렬을 한다음, k번째 수를 리턴하면 된다. -Arrays.sort와 comparator를 사용하면 쉽다. 어레이를 정렬한다 k번쨰 수를 리턴한다 -PriorityQueue를 사용하는 방법도 있다. PriorityQueue에 k만큼 넣는다. k보다 많이 입력되면 가장 작은 수를 제거한다 모두 입력되고 나면 가장 작은 수가 바로 k번째 수이다. -만약 위 메서드들을 사용해서는 안된다고 한다면, 퀵솔트를 구현하라는 문제이다. -퀵솔트는 엄밀하게 따지면, O(n log n)이지만, 평균적으로 O(n)이라고 표현한다. 즉, 위 문제는 퀵솔트를 구현할수 ..
반응형

티스토리툴바