Problem Solutionsliding window 연속된 3개 숫자를 뒤집어서 모두 1로 바꿀 수 있는 최소한의 횟수를 구하는 문제.당연히 2중포문을 쓰면 시간초과가 발생한다.n-2까지만 검사해서 nums[i] == 0 이면 i ~ i+2까지 비트연산으로 1, 0을 뒤집는다.연산이 끝나면 answer+=1비트연산 파이선으로 ^= 이더라? 괜히 if~else 구문으로 바꾸고있었네 마지막에 2개숫자가 0이면 연속된 3자리가 아니라 못바꾸므로 바로 리턴 -1아니면 answer return Codeclass Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i i..

Problem Solutionsliding window 처음에 구현으로 2중 포문 돌렸다가 time limit exceeded 났던 문제.이 문제도 똑같이 sliding window 기법으로 풀어야된다.원형 배열이라서 colors[: k-1]개만큼 기존 배열에 더해준다.그리고 이전 원소와 값을 비교하며 (index 범위는 1 부터 시작) count 를 증가한다.count가 k 이상이면 조건을 만족하므로 answer ++만족하지않으면 count = 1 로 초기화하여 다시 리셋해준다. Codeclass Solution: def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int: n = len(colors) ..

ProblemSolutionstringsliding window blocks string에서 연속된 B의 개수가 k개가 될 수 있도록 가장 최소한의 변경해야되는 W 수를 구하는 문제.substring에서 힌트를 얻어서 k길이만큼 substring을 구하고 W의 개수를 구한뒤 가장 최소값을 리턴하였다. 나는 구현으로 일일이 string을 검사하는 방식으로 풀이했는데 슬라이딩 윈도우 기법을 사용하면 더 최적화된 알고리즘 O(N)으로 해결할 수 있다. Codeclass Solution: def minimumRecolors(self, blocks: str, k: int) -> int: n = len(blocks) answer = 999 if 'W' in blocks a..

Problem Solutionarrayn*n 2차 배열에서 중복된 값, 존재하지 않는 값을 찾는 문제.hash를 사용해서 frequency를 구한다음에 정답을 구해도되고나는  1~n*n까지 연속된 숫자이므로 visited 를 사용해서 이미 방문했는지를 체크하도록 했다.  Codeclass Solution: def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]: answer = [] n = len(grid) visited = [0] * (n*n + 1) twice_num = 0 missing_num = 0 for i in range(..

Problem SolutiondbLCS (Longest Common Subsequence)이 문제의 힌트를 보고 LCS 알고리즘을 사용한 문제라는 것을 알았다.LCS 알고리즘에 대한 설명은 다른 블로그에서 더 자세하게 설명해두어서 참고했다!https://chanhuiseok.github.io/posts/algo-34/ 알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘LCS 알고리즘이란?chanhuiseok.github.io 단 LCS 의 길이를 구하는 알고리즘이라서 LCS 문자를 찾으려면 역추적(back tracking)을 이용해서 구해야한다. 주어진 2개의 string의 LCS 를 구하는 규칙은 아래와 같다.문자열을 비교하여 같았을 때현재 칸에 들어..

Problem Solutiondphashi, j를 피보나치 수열 마지막 두 숫자로 두고 dp[(i, j)] 에 해당 수열의 길이를 저장한다.해시맵 index_map 을 사용하여 빠르게 arr[k] 의 index를 찾을 수 있도록한다.해시셋을 이용하여 arr[i]+arr[j] in arr 여부를 확인한다.Bruteforce 로 풀면 time limit exceeded 나는 문제. db를 사용해서 풀어햐한다. (i, j)를 마지막 두 숫자로 하는 피보나치 수열 찾기!즉, arr[i], arr[j]를 고정하고, arr[i] + arr[j] == arr[k]가 되는 k를 찾아가야 합니다.이를 위해 j를 기준으로 i를 선택하고, (i, j) 쌍을 만들도록 설계합니다.반복문을 돌때 j부터 돌아서 항상 idb[(i,..