Problem : https://leetcode.com/problems/longest-square-streak-in-an-array Difficulty : Medium Status : Solved Time : 00:04:39  문제 설명 더보기정수 배열 nums가 주어질 때, nums의 부분 수열은 다음을 만족할 때 연속 제곱이라고 부른다부분 수열의 길이가 최소한 2이다.부분 수열을 정렬한 후, 첫 번째 원소를 제외한 나머지 원소들은 이전 원소의 제곱수이다.nums의 연속 제곱의 최장 길이를 반환하라. 만약 그러한 연속 제곱이 없다면 -1를 반환하라.부분 수열은 남은 원소의 순서를 바꾸지 않고 일부 원소를 제거함으로써 얻어지는 배열을 의미한다. 풀이 부분 수열의 정의는 약간의 함정이 있다. square ..

Problem : https://leetcode.com/problems/count-square-submatrices-with-all-ones Difficulty : Medium Status : Solved Time : 00:05:29  문제 설명 더보기0 혹은 1로 구성된 m * n 행렬이 주어질때, 모든 값이 1로 이루어진 정사각 부분행렬의 개수를 반환하라.  풀이 정사각형의 개수를 새는 DP 문제는 꽤나 자주 빈출되는 문제이다(이제는 공식처럼 외워 쓸 수 있을 정도로 자주 보이기에, DP 문제의 숙련도를 쌓기에는 그리 추천하지 않는다. 2023.02.21 - [PS/백준] - [백준/1460] 진욱이의 농장 (Python3) [백준/1460] 진욱이의 농장 (Python3)Problem :https:..

Problem : https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets Difficulty : Medium Status : Solved Time : 00:11:57  문제 설명 더보기정수 배열 nums가 주어질때, nums의 부분집합을 bitwise OR 연산하였을 때 가능한 가장 큰 값을 찾고, 최대 bitwise OR값을 도출하는 공집합이 아닌 서로 다른 부분집합의 개수를 반환하라. 어떤 배열 a가 어떤 배열 b의 부분집합이려면, a는 b에서 특정 원소(0개도 가능)를 제거함으로써 얻어질 수 있어야 한다. 두 부분집합은 선택된 원소의 인덱스가 다르다면 다르다고 취급된다. 어떤 배열 a의 bitwise OR은 a[0] OR a..

Problem : https://leetcode.com/problems/extra-characters-in-a-string Difficulty : Medium Status : Solved Time : 00:22:04  문제 설명  더보기0-인덱스의 문자열 s와 단어들의 사전인 dictionary가 주어진다. s를 하나 이상의 겹치지 않는 부분 문자열로 나누며, 부분 문자열은 dictionary 내에 존재해야 한다. 이 부분 문자열 어디에도 속하지 않는 잉여 문자들이 존재할 수 있다. s를 최적으로 쪼갠다고 가정할 때, 남는 잉여 문자들의 최소 개수를 반환하라. 풀이 순수 DP로도 풀 수 있다. 조금 비효율적이겠지만.현재 idx를 기준으로현재 idx의 문자가 잉여 문자임을 가정한다. 그렇다면 dp[idx+..

Problem : https://leetcode.com/problems/different-ways-to-add-parentheses Difficulty : Medium Status : Solved Time : 00:18:44  문제 설명  더보기주어진 문자열과 부호로 이루어진 수식을 입력으로 받아, 숫자와 연산자를 그룹화하는 모든 가능한 경우의 수를 계산하여 반환하라. 어떤 순서로 반환하여도 상관 없다. 생성된 테스트케이스는 출력값이 32비트 정수 내에 존재하며, 결과의 서로 다른 가짓수는 10^4를 초과하지 않는다. 풀이 처음에는 DP로 풀면서 뭐야, 왜 이렇게 복잡해? 싶었으나.. 내 착각이었다. DP로 풀면 결국 O(N^3)에 가까운 비효율적인 방식의 풀이가 되므로, 조금 다른 접근 방식이 필요하다..

Problem : https://www.acmicpc.net/problem/4243 4243번: 보안 업체 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상점의 수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 시작점의 위치 a (1 ≤ a ≤ N)가 주어진다. a번째 점, pa = s가 시 www.acmicpc.net Difficulty : Platinum 3 Status : Solved Time : 00:14:10 문제 설명 더보기 명우는 보안 업체의 직원이고, 강남역에 있는 상점 여러 개를 도보로 순찰하는 업무를 맡고 있다. 강남역은 선분으로 나타낼 수 있고, 명우의 회사와 상점은 왼쪽부터 순서대로 선분 위의 점 pi로 나타낼 수 있다. 회사는 pa에 있고,..