Medium174 [Leetcode] 739. Daily Temperatures 문제 : https://leetcode.com/problems/daily-temperatures/ 일별 온도 정수 배열이 주어지면 해당 날짜에서 볓 번째 날이 지났을 때 해당 날짜의 온도보다 더 높은 온도를 얻을 수 있는지 저장한 배열을 구하라. 만일 가능한 날이 없다면 0을 저장해라. 배열을 뒤에서부터 탐색하면서 stack에 탐색하는 일자의 온도보다 높은 온도만 존재하게 유지한다. 탐색하면서 만일 stack에 탐색 일자의 온도보다 높은 온도가 존재하지 않는다면 0, 존재한다면 stack의 top에 있는 온도의 인덱스에 현재 인덱스를 뺀 값을 정답 배열에 저장한다. Ex) temperatures = [73,74,75,71,69,72,76,73] 시간복잡도는 O(N) 소스코드 C++ : https://gi.. 2021. 11. 13. [Leetcode] 77. Combinations 문제 : https://leetcode.com/problems/combinations/ 백트래킹 문제. for(i = 현재 탐색중인 인덱스 ~ n){ arr 배열 뒤에 i 추가 재귀함수(i+1, arr); // 인덱스를 i+1부터 다시 탐색 arr 배열 뒤에 i 제거 } 위와 같은 재귀함수를 만들어서 arr 배열 크기가 k라면 정답 배열에 arr을 추가한다. 시간복잡도는 K크기의 배열을 만들므로 대충 O(N! / (N-K)!) 이 정도 나올듯. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/77.%20Combinations.cpp 2021. 11. 10. [Leetcode] 43. Multiply Strings 문제 : https://leetcode.com/problems/multiply-strings/ 음이 아닌 정수 num1, num2가 문자열로 주어질 때, num1, num2의 곱을 구하라. index 0 1 2 1 2 3 x 4 5 6(v) ----------- 1 8 1 2 6 ind 0 1 2 1 2 3 x 4 5(v) 6 ----------- 1 5 1 0 5 ind 0 1 2 1 2 3 x 4(v) 5 6 ----------- 1 2 8 4 index 0 1 2 3 4 5 1 8 1 2 6 1 5 1 0 5 1 2 8 +. 4 -------------------- 0 5 5 8 8 8 123 * 456 을 예로 들어보자. 한자리 수 씩 곱하는 경우 최소 한자리 최대 두자리가 나온다. (최대 : 9.. 2021. 11. 8. [Leetcode]11. Container With Most Water 문제 : https://leetcode.com/problems/container-with-most-water/ 수직선 높이를 나타내는 배열이 주어진다. 두 개의 수직선을 선택해서 그 사이에 물을 넣는다고 할 때 가능한 최대 용량은 얼마인가. 투포인터로 푼다. 왼쪽부터 시작하는 left 포인터, 오른쪽부터 시작하는 right 포인터가 있다. left, right 수직선을 선택했을 때의 용량을 구하고 이들 중 최대 값이 정답이 된다. 용량을 구한뒤 left가 right보다 낮다면 left를 +1 하고, right가 left보다 낮다면 right를 -1 해준다. 시간복잡도는 O(N). N = 배열의 크기 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/lee.. 2021. 11. 3. [Leetcode] 130. Surrounded Regions 문제 : https://leetcode.com/problems/surrounded-regions/ 'X', 'O' 로 이루어진 m x n 배열이 있다. 'O'로 둘러쌓인 'X' 구역이 있다면 이들을 모두 'O'로 바꾸어라. DFS, BFS 탐색으로 X로 이루어진 구역들을 구할 수 있다. 이 때, m x n 배열의 경계선에서부터 시작하는 X 구역들은 O로 둘러쌓인게 아니므로 범위에서 제외되어야 한다. 따라서 먼저 경계선에 존재하는 X 구역들을 모두 DFS나 BFS 탐색으로 이미 방문했다고 갱신한다. 이 후, 배열을 탐색하며 이미 방문/탐색 하지 않은 X구역들을 구한 뒤 이들을 모두 O로 바꿔주면 정답이 된다. 시간복잡도는 O(nm) 소스코드 : https://github.com/fpdjsns/Algorit.. 2021. 11. 1. [Leetcode] 222. Count Complete Tree Nodes 문제 : https://leetcode.com/problems/count-complete-tree-nodes/ 완전 이진 트리(complete binary tree)의 루트 노드가 입력으로 주어지면 트리의 노드 수를 반환해라. 시간복잡도를 O(N) 보다 작게 만들어라. 포화 이진 트리의 노드 수는 2^(트리 높이) - 1 임을 사용하자. 최좌측 단노드까지의 높이와 최우측 단노드까지의 높이가 같은 경우 포화 이진 트리가 된다. 높이가 다른 경우, 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수를 구해서 더하고 루트 노드 수인 1을 더한 값이 노드 수가 된다. 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수는 재귀함수를 이용해 구한다. 완전이진트리인지 구하기 위해 log2N이 소요되고, 최악의 경우 높이를 탐색.. 2021. 10. 29. 이전 1 ··· 7 8 9 10 11 12 13 ··· 29 다음
