본문 바로가기

HARD56

[Leetcode] 51. N-Queens 문제 : https://leetcode.com/problems/n-queens/ 두 개의 퀸이 서로 공격하지 않도록 n x n 체스판에 n개의 퀸을 배치하라. 가능한 모든 경우의 체스판 형태를 반환하라. (Q : 퀸, . : 빈칸) (참고로 퀸은 한 번 움직일 때 앞, 뒤, 옆, 대각선 어떤 방향이든 원하는 만큼 이동 가능) 백트래킹으로 풀었다. 퀸은 앞, 뒤, 옆, 대각선 방향을 원하는 만큼 이동 가능하기 때문에 row, col, 대각선에 놓을 수 있는지 여부를 저장해야 한다. 백트래킹 구현 시 하나의 행에 퀸을 두는 경우의 수를 판단한다고 하면 하나의 행에는 하나의 퀸만 놓게 구현하면 row 에 퀸을 놓을 수 있는지 여부는 저장을 하지 않아도 된다. 열의 퀸 저장가능 여부는 n 크기의 boolean .. 2022. 6. 4.
[leetcode] 354. Russian Doll Envelopes 문제 : https://leetcode.com/problems/russian-doll-envelopes/ 배열을 width 오름차순으로 정렬한다. 조건에서 width 는 고려하지 않게 하기 위함이다. 정렬 후 앞에 있는 요소의 width는 뒤에 있는 요소의 width 보다 항상 작거나 같으므로 height 만 고려하면 된다. 결국 정렬된 후 height의 LIS(최장 증가 수열)의 길이를 구하면 이게 정답이 된다. 위와 같은 알고리즘을 사용한다고 할 때, 고려할 점이 하나 있다. [[4,5],[4,6],[6,7],[2,3],[1,1]] 입력 배열이 위와 같을 때, [4,5] [4,6] 중 하나만 선택되게 해야 한다. height의 LIS로 정답을 구할 때 width가 동일한 요소들은 하나만 선택하게 하려.. 2022. 5. 26.
[Leetcode] 32. Longest Valid Parentheses 문제 : https://leetcode.com/problems/longest-valid-parentheses/ '(', ')' 문자만 포함한 문자열이 주어질 때, 가장 긴 유효한 괄호 부분 문자열의 길이를 구하여라. DP + Stack dp[i] = s[~i] 문자열에서 s[i]를 포함한 부분 문자열의 가장 긴 유효한 괄호 부분 문자열 길이. stack 열린 괄호 문자 인덱스 문자열 s를 앞에서부터 탐색하면서 열린 괄호 문자면 스택에 저장하고 닫힌 괄호 문자이면서 스택에 값이 있으면 top 값을 가져온다. top은 현재 탐색 중인 닫힌 괄호 문자와 매칭 되는 열린 괄호 문자의 인덱스(let, index)이며 dp[i] = (i - index + 1) + dp[index-1] dp의 점화식은 위와 같다. .. 2022. 5. 24.
[Leetcode] 410. Split Array Largest Sum 문제 : https://leetcode.com/problems/split-array-largest-sum/ 음이 아닌 정수로 이루어진 nums 배열과 양수 m 이 주어졌을 때, nums 배열을 비어있지 않은 m개의 연속 하위 배열로 분할 할 수 있다. 분할한 m개의 부분배열 중 가장 큰 합을 최소화 했을 때, 부분배열 합의 최대값을 구해라. 이진탐색으로 풀었다. 부분배열 중 가장 큰 합(set, answer)을 이진탐색을 통해서 구하는 방법으로 해보자. answer가 될 수 있는 값은 제한사항을 보면 nums[i]의 최소값이 0이므로 0에서 nums배열의 합까지 가능하다. 따라서, left = 0, right = sum of nums. 로 한 후 이진탐색을 돌린다. 이진탐색은 medium = (left .. 2022. 3. 31.
[Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26.
[Leetcode] 127. Word Ladder 문제 : https://leetcode.com/problems/word-ladder/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환시퀀스 길이를 구하라. 만일 변환 불가능하다면 0을 반환하라. 126. Word Ladder2 와 비슷하게 풀었다. 126번과 이번문제와의 차이점은 반환값이 변환시퀀스 리스트인지, 변환시퀀스 길이인지이다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hit", "hot","dot","dog","lot","log","cog"] 126번 문제와 비슷하게 BFS로 풀고, 이를 위해 먼저 그래프 .. 2022. 2. 12.

티스토리툴바