01 01

슬라이딩 윈도우(Sliding Window)에 대해 이야기합니다. 브루트포스(Bruteforce, 완전 탐색)와 비교한 코드 조각을 기입해뒀습니다. 슬라이딩 윈도우로 풀 수 있는 백준 문제도 끝에 첨부합니다."슬라이딩 윈도우를 가볍게 이해하기"가 목표라면 도움이 되는 문서입니다.   슬라이딩 윈도우(Sliding Window)는 "고정된 크기 또는 가변 크기의 윈도우(부분 구간)를 한 칸씩 이동하면서, 이전 계산 결과를 활용하여 중복 연산을 줄이는 기법"입니다.윈도우는 말 그래도 "구간"입니다. 중복 연산을 줄이는 기법이란 건, 아래 예제에서 얘기할 브루트 포스(Bruteforce)과 비교하면 이해할 수 있습니다. 슬라이딩 윈도우는 연속된 배열의 합이나 특정 패턴을 구할 때 사용됩니다.   특정 패턴을 ..

Big O의 O(n)과 O(log n)의 성능 비교실생활에서 O(n)만큼의 시간이 드는 행위, O(log n)만큼의 시간이 드는 행위를 찾고, 코드로 구현해 실행 결과를 확인한 뒤, 성능 차이를 비교한 문서입니다.  Big O에서 O(n)과 O(log n)O(n)과 O(log n)은 시간 복잡도와 공간 복잡도를 표현하는 점근 표기법(Big O 표기법의) 중 하나이다. 입력 데이터의 크기를 n이라고 할 때, 연산 횟수가 최대 n만큼 필요한 경우를 O(n), log n 만큼 필요한 경우 O(log n) 으로 표현한다.예를 들어 데이터의 크기가 1백만 개(1_000_000)일 때,O(n)은 1_000_000 번을, O(log n)은 (*일반적으로 log의 밑은 10이나, Big O 에서 log의 밑은 2) 약..