728x90 Algorithm - Java/How to3 [How to] 슬라이딩 윈도우(Sliding Window) 프로그래밍 문제를 풀다 보면,부분 배열의 최대합, 최대 길이와 같은특정 조건을 만족하는 구간 찾기와 같은 문제들을 자주 만나게 된다.이런 문제들을 단순 반복문으로 풀면 시간 복잡도가 O(N²) 이상으로 커지는 경우가 많은데이때 쓰이는 것이 바로 슬라이딩 윈도우(Sliding Window)이다.말 그대로 고정된 크기의 창(윈도우)을 왼쪽에서 오른쪽으로 한 칸씩 밀어가며 배열이나 문자열을 탐색한다.전체 데이터를 순회하지 않으면서 탐색하기에 시간복잡도와 공간복잡도 모두 효율적으로 사용할 수 있다.예제1: 최대 연속 부분합 구하기[문제 설명]길이 N의 정수 배열 arr와 정수 k가 주어진다. 이때, 연속된 k개의 원소를 선택했을 때의 합 중에서 가장 큰 값을 구하시오. [제한 사항] 1 ≤ N ≤ 100,000.. 2025. 5. 13. [How to] 제한 조건에 따른 시간복잡도 고려 코딩테스트 문제를 접하다 보면 언제나 보게 되는 제약 조건.주로 시간과 메모리, 그리고 입력 조건에 따라 천차만별이다.구현한 코드가 어떤 시간/공간 복잡도를 가지냐에 따라분명 답은 찾지만 시간 초과나 메모리 초과가 발생할 수 있고,언제나 최적의 알고리즘을 쓸 수 있어야 좋은 개발자가 될 수 있을 것이다. 시간 복잡도(Time Complexity)- 코드의 실행 시간은 실행 환경에 따라 달라진다. 언어, 하드웨어, 운영체제 등 다양한 환경에서 실행되기에 같은 코드라도 실행시간은 다를 수 있다.- 그렇기에 실행 시간이 아닌 연산의 실행 횟수를 카운트한다. 이를 입력 데이터의 크기에 관한 함수로 나타내고, 이를 점근적 표기법으로 나타낸다.- 점근적 표기법은 O, Ω, Θ 등의 표기가 있다. 상대적으로 가장 간.. 2025. 5. 12. [How to] 최대 연속 부분 합 구하기 (Kadane's Algorithm) 최대 연속 부분 합 문제란한 배열에서 어떤 인덱스 i부터 이후의 한 인덱스 j까지 값들을 더했을 때그 값이 최대가 되는 영역을 구하는 문제이다. 즉, 정수 배열에서 연속된 구간의 합 중에서 가장 큰 값을 찾는 것!최대 합을 찾는 문제이기에 구간은 고정 길이가 아닌 가변 길이이다.기본 풀이법1. O(N³)int answer = 0;for(int i = 0; i - 시작 인덱스와 끝 인덱스를 각각 반복문을 통해 구하고 구간 별로 반복문을 통해 구간 합을 구한 후에 비교하여 최댓값을 구한다.- 코드 작성 시에는 쉽게 생각나지만 삼중 반복인 만큼 당연히 시간복잡도 면에서 효율적이지 못 함. 2. O(N²)int answer = 0;for(int i = 0; i - 시작인덱스 지정 후 누적합 방식으로 sum을 누.. 2025. 5. 9. 이전 1 다음 728x90
