Medium174 [Leetcode] 516. Longest Palindromic Subsequence 문제 : https://leetcode.com/problems/longest-palindromic-subsequence/description/ 주어진 문자열 s에서 가장 긴 회문 부분 수열의 길이를 찾으세요. 부분 수열이란 다른 수열에서 일부 또는 전혀 없애지 않고 남은 원소들의 순서를 변경하지 않고 유도할 수 있는 수열입니다. DP로 풀 수 있습니다. dp[i][j] = s[i~j] 의 부분 수열의 가장 긴 펠린드롬 길이. dp[i][j] = dp[i+1][j-1] + 2 (s[i] == s[j]) = max(dp[i+1][j], dp[i][j-1]) (s[i] != s[j]) 점화식은 위와 같습니다. 만약, 문자열의 가장 앞과 뒤의 문자가 같다면 문자열의 가장 앞, 뒤 문자를 부분 수열에 포함하여 길.. 2023. 4. 14. [Leetcode] 71. Simplify Path 문제 : https://leetcode.com/problems/simplify-path/description/ 주어진 문자열 path는 Unix 스타일 파일 시스템에서 파일 또는 디렉토리까지의 절대 경로(슬래시('/')로 시작)입니다. 이를 간소화된 카노니컬 경로로 변환하세요. Unix 스타일 파일 시스템에서 마침표(.)는 현재 디렉토리를 의미하며, 두 개의 마침표(..)는 상위 디렉토리를 의미합니다. 여러 개의 연속된 슬래시(//)는 하나의 슬래시(/)로 처리됩니다. 이 문제에서는 '...'와 같은 다른 마침표 형식은 파일, 디렉토리 이름으로 처리됩니다. 카노니컬 경로는 다음과 같은 형식을 가져야 합니다: 1. 경로는 슬래시(/)로 시작합니다. 2. 두 개의 디렉토리는 하나의 슬래시(/)로 구분됩니다... 2023. 4. 12. [Leetcode] 2390. Removing Stars From a String 문제 : https://leetcode.com/problems/removing-stars-from-a-string/description/ 문자열 s가 주어지며, s는 별표(*)를 포함합니다. 한 번의 작업에서 다음을 할 수 있습니다: s에서 별표 하나를 선택합니다. 그 별표 왼쪽에서 가장 가까운 비 별표 문자를 제거하고, 그 별표 자체도 제거합니다. 모든 별표가 제거된 후의 문자열을 반환합니다. 참고 - 입력은 항상 작업이 가능하도록 생성됩니다. - 결과 문자열은 항상 고유함이 보장됩니다. stack을 사용합니다. 문자를 앞에서부터 탐색하면서 별표가 아닌 문자인 경우 스택에 문자를 넣습니다. 별표인 경우 스택의 탑에 있는 문자를 제거합니다. 모든 문자열을 탐색했으면 스택에서 문자를 제거하면서 정답 문자열.. 2023. 4. 11. [Leetcode] 2300. Successful Pairs of Spells and Potions 문제 : https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/ spells와 potions이라는 길이가 각각 n과 m인 두 개의 양의 정수 배열이 주어집니다. 여기서 spells[i]는 i번째 주문의 강도를 나타내고, potions[j]는 j번째 물약의 강도를 나타냅니다. 그리고 주문과 물약의 강도를 곱한 값이 success 이상이면 성공적인 것으로 봅니다. 각 주문에 대해 성공적인 값을 이룰 수 있는 물약과 주문 pair 수를 나타내는 배열을 구하세요. 그리디 문제입니다. 먼저 spells와 potions를 정렬해야 하는데, 구하고자 하는 배열은 각 spell에 대한 값을 원하므로 spells는 해당 값의 인덱.. 2023. 4. 8. [Leetcode] 881. Boats to Save People 문제 : https://leetcode.com/problems/boats-to-save-people/description/ people이라는 배열이 주어지는데, people[i]는 i번째 사람의 몸무게를 나타냅니다. 그리고 무게 제한이 limit인 무수히 많은 보트가 있습니다. 각 보트는 최대 limit 무게까지 운반할 수 있으며, 최대 두 사람이 탈 수 있으며 두 사람의 무게 합이 limit 이하여야 합니다. 주어진 모든 사람을 운반하기 위해 필요한 최소 보트 수를 구하세요. 한 번에 두 명이 탈 수 있습니다. 투포인터로 해결할 수 있습니다. 먼저 people 배열을 오름차순 정렬합니다. 왼쪽부터 탐색하는 left 인덱스, 오른쪽부터 탐색하는 right 인덱스를 준비합니다. 만약 한 보트에 가장 무거운.. 2023. 4. 7. [Leetcode] 1254. Number of Closed Islands 문제 : https://leetcode.com/problems/number-of-closed-islands/description/ 0(육지)과 1(물)로 이루어진 2차원 그리드가 주어집니다. 섬은 4방향으로 연결된 0으로 이루어진 최대 그룹이며, 폐쇄된 섬은 1로 둘러싸인 섬입니다. 폐쇄된 섬의 수를 반환하세요. 섬은 물로 완벽하게 둘러쌓여야 하므로 배열의 가장자리와 맞닿아 있는 육지는 섬으로 보지 않습니다. 따라서, 먼저 가장자리부터 탐색하면서 DFS 혹은 BFS로 가장자리 땅이 육지인 경우 연결된 육지들을 전부 물로 바꿔주는 사전작업을 해줍니다. 이 후, 땅들을 다시 탐색하면서 탐색 중인 땅이 육지인 경우 정답을 1 추가한 뒤, 마찬가지로 DFS/BFS로 연결된 육지들을 모두 물로 바꿔줘서 중복 정답.. 2023. 4. 6. 이전 1 2 3 4 ··· 29 다음
