본문 바로가기

알고리즘 문제/Leetcode283

[leetcode] 126. Word Ladder II 문제 : https://leetcode.com/problems/word-ladder-ii/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환횟수 문자열 변경 리스트들을 구하라. beginWord는 wordList에 없어도 되지만 endWord는 wordList에 있어야만 변경 가능한다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] // output [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog.. 2021. 7. 25.
[leetcode] 85. Maximal Rectangle 문제 : https://leetcode.com/problems/maximal-rectangle/ 0과 1로 이루어진 배열이 주어질 때, 1로만 이루어진 직사각형의 최대 크기를 구하라. 배열 크기가 row x cols 인데 row, cols 모두 최대 200이다. row, cols 의 최대크기가 동일하니까 해당 크기를 N이라 봤을 때, 직사각형의 크기를 구하려면 직사각형의 왼쪽 위 지점을 구하기 위해 O(N^2), 이때, 오른쪽 아래 지점을 구하기 위한 O(N^2)가 드므로 완탐으로 구하면 총 O(N^4)이 소요된다. N의 최대 크기는 200이므로 TLE가 발생할 것이다. 시간을 좀 더 줄 일 수 있는 방법을 찾아야한다. 배열을 탐색하면서 오른쪽 아래 지점을 고정시키고 왼쪽 위 지점을 탐색해가면서 만들 수.. 2021. 7. 24.
[leetcode] 236. Lowest Common Ancestor of a Binary Tree 문제 : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 트리가 주어질 때, 노드 p, q의 최하위 공통조상(LCA; Lowest Common Ancestor)를 찾아라. 재귀함수로 풀었다. 이 함수는 탐색하는 노드를 루트로 하는 서브트리에서 p, q를 찾은경우 해당 노드를 반환하거나, 만약 두노드의 최하위 공통조상인 경우 해당 노드를 반환한다. p, q 가 서브트리에 없는 경우는 NULL을 반환한다. 현재 탐색 중인 노드가 p 또는 q 인 경우 현재 노드를 반환한다. 왼쪽 자식, 오른쪽 자식들을 탐색노드로 함수를 호출한다. 왼쪽, 오른쪽 자식들에서 p, q를 찾았다면(NULL이 아니라면) 현재 탐색중인 노드가 LCA가 되므로.. 2021. 7. 22.
[Leetcode][611] Valid Triangle Number 문제 : https://leetcode.com/problems/valid-triangle-number/ 0이상의 정수배열 nums가 주어질 때, 이 들 중 3개 수를 골라서 삼각형을 만들 수 있는 경우의 수를 구해라. 투포인터로 풀었다. nums 배열을 오름차순 정렬한다. nums를 처음부터 탐색하면서 탐색하는 정수는 고정적으로 사용하는 변의 길이다. (let, a) 탐색한 정수의 바로 다음 정수들을 탐색하는데 이를 다음으로 선택하는 변의 길이이다. (let, b) 삼각형을 만들기위한 2개의 변을 고정했다. 삼각형이 되기 위한 조건은 두 개의 변의 길이 합이 나머지 하나(최장길이 변)의 길이보다 커야한다. 나머지 변을 c라고 하자. 만일 이전 탐색으로 구한 길이들의 관계가 a + b > c 였다면, b는.. 2021. 7. 15.
[leetcode] 639. Decode Ways II 문제 : https://leetcode.com/problems/decode-ways-ii/ A ~ Z 문자가 1 ~ 26 숫자로 인코딩된다.(01, 02 는 1, 2와 다르다.) 숫자와 * 문자로 이루어진 문자열이 주어진다. * 문자는 0을 제외한 1~9로 대체할 수 있다. 입력 문자열을 디코딩하였을 때 만들 수 있는 문자열들의 경우의 수를 구해라. 백트래킹과 DP(memoization)을 이용해서 풀었다. dp[ind] = 입력문자열[ind~]로 만들 수 있는 정답 경우의 수 ind 번째 문자를 탐색 중일 때, 해당 문자는 십의자리로 디코딩될수도 있고, 일의자리로 디코딩 될 수도 있다. 두 가지 경우의 수를 구한뒤 더해준다. 십의 자리로 디코딩될 수 있는 경우의 수를 먼저 알아보자. 만일 ind+1 번.. 2021. 7. 14.
[leetcode]1047. Remove All Adjacent Duplicates In String 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/ 문자열을 탐색하면서 정답 문자열을 만든다. 만약 탐색중인 문자가 정답 문자열의 마지막 문자와 같다면 문자를 추가하지 않고 정답 문자열의 마지막 문자를 삭제한다. 정답문자열이 비어있거나 탐색중인 문자와 정답 문자열의 마지막 문자와 다르다면 정답문자열에 탐색중인 문자를 추가한다. 시간복잡도는 O(N). N = |입력 문자열| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1047.%20Remove%20All%20Adjacent%20Duplicates%20In%20String.cpp 2021. 6. 28.

티스토리툴바