# Sliding Window

41개의 포스트

Leetcode - 3. Longest Substring Without Repeating Characters

문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.sliding window 로 해결. (discussion참고) left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.해시테이블에 빈도수를 저장. tabl

2022년 6월 20일
·
0개의 댓글

Leetcode - 219. Contains Duplicate II

배열이 주어지고 서로다른 두 인덱스 i, j가 있을때 다음의 조건을 만족하는 i,j가 있다면 true 리턴nums\[i] == nums\[j] abs(i - j) <= k.문제를 다시 풀어보면 i, j의 간격크기가 k 이하 일때, 배열값이 서로 같은 요소가 있는지

2022년 6월 13일
·
0개의 댓글

Leetcode - 2269. Find the K-Beauty of a Number

숫자num이 주어지고 k길이가 주어질때, 숫자를 k만큼 쪼갠 수가 주어진 num의 몫이 될수 있는가? 있다면 몇개 존재하나?

2022년 6월 9일
·
0개의 댓글

Programmers) 보석 쇼핑(Lv.3)

보석 쇼핑(2020 Kakao Internship)"진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매"효율성 테스트도 있는 걸로 보아 이중 for문으로 접근하면 안되겠다 싶었다. 그래서 모든 종류의 보석을 포함하는 가장 짧은 구간을 탐

2022년 5월 31일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(6) : 최대 길이 연속부분 수열(JAVA)

위 문제는 rt의 값이 lt를 따라가는 식으로 작성을 해야한다.lt, rt의 값을 0으로 고정시켜주고, rt가 0을 만나면 1로 바꾸어 주고 cnt++;를 해준다.answer는 cnt>K 가 성립이 될때, rt-lt+1 을 한 값을 넣어준다.

2022년 5월 26일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(5) : 연속된 자연수의 합(JAVA)

2중 for문으로 풀지 말자! 시간 복잡도가 커진다.위에서 했던 방법과 일치한다.배열의 크기는 입력값 N의 N/2 + 1 만큼 해준다.배열 배열의 값은 위와 같은 식으로 넣어 준다.배열 m의 크기는 입력값 n/2+1 의 크기 만큼 만들어 준다.arr0=1, arr1=2

2022년 5월 25일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(4) : 연속 부분수열(JAVA)

만약 2중 for문으로 풀게 된다면 시간복잡도는 O(N^2)이 된다.N의 범위는 1~100,000이기 때문에 O(N^2) 굉장히 큰 값이 설정된다.two pointer나 sliding window 알고리즘은 O(N^2)의 시간 복잡도를O(N)으로 바꿔 준다.sum 은

2022년 5월 25일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(3) : 최대 매출(JAVA)

Sliding window이다.위 문제를 2중 for문으로 풀게 되면 시간 복잡도가 복잡해 진다.(N \* K)위와 같은 방법으로 한 칸씩 밀어가면서 나타내는 방법이다.밀면서 각 원소의 합을 sum에 저장한다.위의 설명을 소스코드로 옮겨보자!

2022년 5월 24일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(2) : 공통원소 구하기(JAVA)

두 배열 a,b 를 오름차순으로 정렬한다.배열 a의 pointer를 p1, 배열 b의 pointer를 p2라고 한다.ap1<bp2 이므로 p1의 값을 1증가 시켜준다.b배열은 p2의 값을 증가 시켜도 오름차순으로 정렬되었기 때문에 같은 값이 있을 수 없다.ap1

2022년 5월 24일
·
0개의 댓글
post-thumbnail

[알고리즘] Two pointers, Sliding window(1) : 두 배열 합치기(JAVA)

🎨 쉬운 문제인데, 정렬로 문제를 풀면 시간복잡도가 커진다.n을 입력받고 입력받은 n만큼의 크기 배열 a를 만든다.m을 입력받고 입력받은 m만큼의 크기 배열 b를 만든다.for 문과 nextInt()를 이용해 입력값을 배열에 저장한다.출력을 위한 코드T.solutio

2022년 5월 24일
·
0개의 댓글
post-thumbnail

[Leetcode]187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.For example, "ACGAATTCCG" is a DNA sequence.When studyin

2022년 5월 19일
·
0개의 댓글
post-thumbnail

[백준/ 파이썬] 2559번 수열

백준 2559번 수열백준 2559번 문제는 누적합을 이용하는 문제입니다.Sliding window을 활용해서 간단하게 문제를 풀 수 있습니다.Sliding window를 간단하게 설명한 그림입니다.전체코드

2022년 5월 4일
·
0개의 댓글
post-thumbnail

[백준/ 파이썬] 12847번 꿀 아르바이트

백준 12847 꿀 아르바이트12847번 꿀 아르바이트 문제는 누적합 문제입니다.모든 경우에 대해서 처음부터 합을 구하는 것이 아니라 이전에 구해놓은 합으로 부터 값을 찾아가는 방식입니다.제가 예전에 만들어놓은 그림입니다. 이런 방식으로 문제를 해결할 수 있습니다.맨

2022년 5월 4일
·
0개의 댓글

[ leetcode ] Longest Substring with At Most Two Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/요즘 알고리즘은 통 안풀다가 오랜만에 리트코드를 켰다.그리고 만난 문제 문제 설명은 다음과 같다.오직 두

2022년 4월 17일
·
0개의 댓글
post-thumbnail

[Leetcode]209. Minimum Size Subarray Sum

📄 Description Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray $[nums{l}, n

2022년 4월 1일
·
0개의 댓글
post-thumbnail

[Leetcode]643. Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.Find a contiguous subarray whose length is equal to k that has the maxi

2022년 3월 30일
·
0개의 댓글
post-thumbnail

[ Python_Algorithm ] 슬라이딩 윈도우 (Sliding Window) 2

슬라이딩 윈도우에 대해 조금 더 알아보았다.문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라.먼저 브루트 포스로 풀어보면, 최소 윈도우라고 했으니 일단 T의 크기부터 시작해 점점 크기를 키워가며 모든 윈도우 크기에 대해 탐색해야

2022년 3월 15일
·
0개의 댓글
post-thumbnail

[ Python_Algorithm ] 슬라이딩 윈도우 (Sliding Window) 1

슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 의미한다. 원래 네트워크에서 사용되던 알고리즘이지만, 문제 풀이에 응용할 수 있다.슬라이딩 윈도우 기법은 투 포인터 기법과 함께 알고리즘 문제 풀이에 매우

2022년 3월 14일
·
0개의 댓글
post-thumbnail

[Leetcode/C++] 134_Gas Station

문제는 다음과 같습니다.이 문제를 두 가지 방법으로 풀었는데,처음 풀었던 풀이는 시간초과가 난 풀이입니다.풀이는 다음과 같습니다.이 방식은시작점을 찾고 시작점을 기준으로 n만큼 돌기 때문에총 시간복잡도는 O(n^2)입니다.O(n)으로 풀어야 시간초과가 안 나는것 같아서

2022년 2월 10일
·
0개의 댓글

[Leet] - 438. Find All Anagrams in a String [Hash table, Sliding Window] - c++

https://leetcode.com/problems/find-all-anagrams-in-a-string/C++풀이1\. 알파벳을 hash table 구조 적용위해 vector res(26)선언 2\. for(auto c : p)resc-'a'++ =>

2022년 2월 3일
·
0개의 댓글