슬라이딩윈도우 검색 결과

해당 글 2건
Longest Substring Without Repeating Characters 문제를 풀면서 슬라이딩 윈도우를 정복해 봅시다.

이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다. 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다. 문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도..
자료알고/알고리즘 2021. 8. 27. 20:47
슬라이딩 윈도우 알고리즘 : 2개의 커서가 중요하다.

제가 응원하는 롯데랑 키움 경기 보느라 지금 글을 씁니다. 둘이서 경기하면 어떻게 하냐고요? 그건 좀 난감한 질문이네요. 뜬금없이 야구 이야기를 하다니. 오랫만에 ps에서 쓸 법한 알고리즘을 해 보겠습니다. 슬라이딩 윈도우라고, 코테에서 은근히 나오는 친구가 하나 있습니다. 톡에서도 질문을 받았었고요. 그것만 잠깐 해 보도록 하겠습니다. 아래의 문제를 생각해 보겠습니다. 길이가 n인 배열이 있습니다. 이 중에서 (부분 순서하고는 다른) 부분 배열을 뽑을 건데 제가 좋아하는 팀인 롯데는 1번 이상, 키움은 2번 이상 나와야 합니다. 그러한 조건을 만족하는 최소 부분 배열의 길이는 어떻게 될까요? 라는 문제를 생각해 보겠습니다. 일단 brute한 해결책을 먼저 생각해 보겠습니다. 0번 인덱스를 기준으로 보면..
자료알고/알고리즘 2020. 7. 29. 01:09