# Sliding Window
Leetcode - 209. Minimum Size Subarray Sum
sub-array의 합이 주어진 target보다 크거나 같은 sub-array의 최소 길이는? (없다면 0 리턴)전형적인 슬라이딩 윈도우 전략if (sum >= target) -> st++ 앞부분 사이즈 줄이기if (sum < target) -> end++뒷부
알고리즘 강의 정리3 : 문제 해결 패턴
유용하게 쓰일 수 있는 일반적인 패턴 몇가지를 학습하면 도움이 된다.패턴은 코드를 작성하는 일반적인 접근법, 즉 원형빈도 카운터라고 부르는데 꼭 이렇게만 불리지는 않음.배열이나 객체의 값의 포함 유무나 빈도를 모을때 쓴다중첩 반복문이나 O(n^2)를 피할 수 있어서 유
Sliding Window
Sliding Window 알고리즘은 윈도우 즉 일정한 범위를 가지고 있는 것을 유지하면서 이것을 이동하는 것이다.imageSliding Window 알고리즘 문제인지 판별하는 조건 3가지 First thing is, we have given something like
3. Longest Substring Without Repeating Characters
start와 end가 substring의 시작과 끝을 가리킨다. substring의 길이와 substring의 각 알파벳을 해쉬에 넣었을 때의 길이가 같은지를 확인하여 중복된 알파벳이 존재하는지 여부를 확인한다. 만약 중복된 알파벳이 있다면, end에 있는 알파벳과 같
Leetcode - 567. Permutation in String
s2가 s1문자열의 permutation을 포함하고 있다면 true를 리턴하라. permutation 이라서 back tracking을 떠올릴 수 있지만 그렇게 풀면 대단히 느려진다. permutation 이라는것은 각 문자의 frequency가 항상 동일하다는 뜻.
Leetcode - 28. Find the Index of the First Occurrence in a String
주어진 haystack 문자열에서 needle 문자열을 탐색했을때, 발견된 첫번째 인덱스를 리턴, 없다면 -1리턴. 해시값 비교하기. O(n\*m)kmp 알고리즘
[Object Detection] Architecture - 1 or 2 stage detector 차이
Object detection 아키텍처에는 1-stage detector과 2-stage detector가 있습니다. 본 글에서는 두 아키텍처 모델의 차이점에 대해 알아보려고 합니다.
Leetcode 3. Longest Substring Without Repeating Characters with Python
Dynamic programming이 생각나는 문제
[Algorithm] 연속된 자연수의 합
N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.만약 N=15이면7+8=154+5+6=151+2+3+4+5=15와 같이 총 3가지의 경우가 존재한다.첫 번째 줄에 양의 정수 N(7
Leetcode - 480. Sliding Window Median 풀이 [H]
주어진 배열을 순회하면서 k 크기의 window size 의 모든 median값을 구하라.https://leetcode.com/problems/sliding-window-median/sliding window 문제는 매번 윈도우 크기 k를 모두 계산할 필요가
[Algorithm] 연속 부분수열
N개의 수로 이루어진 수열이 주어집니다.이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.만약 N=8, M=6이고 수열이 다음과 같다면1 2 1 3 1 1 1 2합이 6이 되는 연속부분수열은 {2, 1, 3}, {1,
[Algorithm] 최대 매출
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면12 1511 20 2510 20 19 13 15
76. Minimum Window Substring
개략적으로 얘기하면 배열에서 가장 처음 만족하는 배열의 시작 index와 끝index를 찾습니다.그리고 while을 통해 또 다른 배열의 조합이 있을때까지 찾습니다.찾는 방법은 left위치의 문자와 right위치의 문자가 같을때 까지 right를 늘립니다.그리고 원하는
Sliding Window 문제
s로 주어지는 문자열 안에서 p로 주어지는 문자열의 Anagram을 찾고 시작부분의 인덱스를 리턴하라.해시테이블과 sliding window기법을 사용하는 좋은 문제였다. p크기 만큼의 윈도우를 s내에서 하나씩 오른쪽으로 이동하면서 체크하면 됨.Runtime: 12 m
[알고리즘] 슬라이딩 윈도우(Sliding window), 투 포인터(Two pointer)
슬라이딩 윈도우는 일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는 알고리즘이다. 한 칸씩 이동 하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다.일정 길이 최댓값을 구하는 함수일정 길이 최솟값을 구하는 함수투 포인터는 데이터에
[백준] 문자열 폭발 (문자열) 🥇
문제보기 1) len(폭발문자열) <= len(현재 문자열): 을 만족하면, 폭발 문자열 == 현재 문자열을 만족하는지 비교해준다.1)을 만족하지 않으면, 문자열을 계속해서 추가시켜준다. 자료구조는 stack을 이용했다.2) 문자열을 비교하기 위해서, start와
Leetcode - 438. Find All Anagrams in a String
s로 주어지는 문자열 안에서 p로 주어지는 문자열의 Anagram을 찾고 시작부분의 인덱스를 리턴하라.해시테이블과 sliding window기법을 사용하는 좋은 문제였다. p크기 만큼의 윈도우를 s내에서 하나씩 오른쪽으로 이동하면서 체크하면 됨.Runtime: 12 m
Leetcode - 424. Longest Repeating Character Replacement
대문자로 구성된 문자열이 주어지고, 아무 문자로 바꿀수 있는 횟수 k가 주어질때, 동일한 문자로 구성된 substring의 최대 갯수는?생각하기 어려웠던 문제였다. discussion을 좀 참고했음. right와 left를 O(n)동안 하나씩만 이동해도 결과를 얻을수
Leetcode - 1652. Defuse the Bomb
주어진 배열값과 k값으로 폭탄을 해체하는 코드를 생성해라. 코드를 생성하는 방법은, 각 자리수를 k개만큼 이전/이후 까지를 더한값으로 계산하면 된다. 아래 예시를 확인!주의할 사항은 순환배열이라는 사실. https://leetcode.com/problems/d
Leetcode - 159. Longest Substring with At Most Two Distinct Characters
문자열이 주어질때, 최대 2개로만 구성된 가장 긴 substring 길이를 리턴하라.two pointer & sliding window (with hashtable)hashtable빈도수가 2개 이하일때 -> right 증가hashtable빈도수가 2개 초과일때 ->