본문 바로가기

전체 글657

[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.
[Programmers] 하노이의 탑 문제 : https://programmers.co.kr/learn/courses/30/lessons/12946 오랜만에 풀어보는 하노이의 탑. 재귀로 풀었다. A -> C로 N개의 원판을 옮긴다고 해보자. 가장 아래에 있는 원판을 제외한 N-1개의 원판은 커다란 덩어리로 보자. 먼저 N-1개의 원판을 하노이의탑 규칙에 어긋나지 않게 A -> B 위치로 옮긴다. 그 뒤, N 번째 원판을 A -> C로 옮긴다. 다시 N-1개의 원판을 N-2번째 원판과 그 외의 원판들로 보자. N-2 개의 원판들을 규칙에 어긋나지 않게 B -> A로 옮긴 후, N-1번째 원판을 B -> C로 옮긴다. 이를 반복하며 다시 N-2개의 원판들을 C로 옮긴다. // n개의 원판을 from -> to로 이동 fun hanoi(int .. 2021. 7. 6.

티스토리툴바