Computer Science/Algorithm

투포인터, 슬라이딩 윈도우

2022. 9. 1. 18:32
목차
  1. 투포인터, 슬라이딩 윈도우
  2. 투포인터
  3. 슬라이딩 윈도우

투포인터, 슬라이딩 윈도우

리스트 완전 탐색 시 성능이 좋지 않을 때 적용할만한 알고리즘이다.

  • 투포인터 : 리스트에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 방식의 알고리즘. O(n)의 성능을 낸다.
  • 슬라이딩 윈도우 : 고정 크기의 윈도우가 이동하면서 원하는 결과를 얻는 방식의 알고리즘. 처음 윈도우만 계산한 뒤 윈도우를 이동시킨다. 이동시킬때 이전 윈도우의 값을 조작한다. O(n)의 성능을 낸다.

투포인터, 슬라이딩 윈도우

투포인터

투포인터 관련 문제이다. https://www.acmicpc.net/problem/1806

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

import java.io.IOException;
import java.util.*;
import java.lang.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int N, S;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = 0; //투포인터
        int answer = 100000;
        int sum = arr[0]; //start부터 end까지의 합

        while(start <= end) {
            if(sum < S) {
                end++;
                if(end < N) sum += arr[end];
                else break;
            }
            else{
                answer = Math.min(answer, end-start+1);
                sum -= arr[start];
                start++;
            }
        }

        if(answer == 100000) System.out.print(0);
        else System.out.print(answer);
    }
}

슬라이딩 윈도우

슬라이딩 윈도우 관련 문제이다. https://www.acmicpc.net/problem/2531

 

2531번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤

www.acmicpc.net

import java.io.IOException;
import java.util.*;
import java.lang.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int n,d,k,c;
    static int answer, result;
    static int[] conveyorBelt;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        conveyorBelt = new int[n];
        visit = new int[d+1];

        for(int i=0; i<n; i++) {
            int sushi = Integer.parseInt(br.readLine());
            conveyorBelt[i] = sushi;
        }

        //처음 윈도우 계산
        for(int i=0; i<k; i++) {
            if (visit[conveyorBelt[i]] == 0) result += 1;
            visit[conveyorBelt[i]] += 1;
        }
        if(visit[c] == 0) answer = result + 1;
        else answer = result;

        //윈도우를 이동하면서 동작
        for(int i=0; i<n; i++) {
            int start = i;
            int end = (start + k) % n;

            visit[conveyorBelt[start]] -= 1;
            if (visit[conveyorBelt[start]] == 0) result -= 1;

            if (visit[conveyorBelt[end]] == 0) result += 1;
            visit[conveyorBelt[end]] += 1;

            if (visit[c] == 0) answer = Math.max(answer, result + 1);
            else answer = Math.max(answer, result);
        }
        System.out.print(answer);
    }
}

 

 

 

'Computer Science > Algorithm' 카테고리의 다른 글

[알고리즘 패러다임 - 2] DP  (0) 2022.10.04
[알고리즘 패러다임 - 1] Brute Force  (0) 2022.10.04
순열, 조합 - Brute Force  (0) 2022.10.03
이진 탐색  (0) 2022.09.16
재귀 함수  (1) 2022.08.30
  1. 투포인터, 슬라이딩 윈도우
  2. 투포인터
  3. 슬라이딩 윈도우
'Computer Science/Algorithm' 카테고리의 다른 글
  • [알고리즘 패러다임 - 1] Brute Force
  • 순열, 조합 - Brute Force
  • 이진 탐색
  • 재귀 함수
gunjoon98
gunjoon98
gunjoon98
하루한방울
gunjoon98
전체
오늘
어제
  • 분류 전체보기 (139)
    • Computer Science (60)
      • Network (14)
      • DataBase (12)
      • Algorithm (14)
      • OS (9)
      • Computer Terminology (1)
      • DataStructure (10)
    • Spring (24)
      • Spring Basic (2)
      • Spring MVC (11)
      • Spring DB (4)
      • Spring Security (2)
      • Spring Test (1)
      • Spring Legacy (2)
      • 기타 (2)
    • Java (9)
      • Basic (7)
      • OOP (0)
    • WEB (14)
      • CSS (4)
      • JS (0)
      • HTTP (10)
    • PS (11)
      • 종만북 (10)
      • 모의 코테 (0)
      • 오답노트 (1)
    • Linux (6)
      • Ubuntu (6)
    • CM (5)
      • Git (5)
    • Project (0)
      • Deubot (0)
      • Scoreboard (0)
    • Infra (5)
      • Cloud (1)
      • CI&CD (3)
      • 쿠버네티스 (1)
    • Hadoop Echo System (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

hELLO · Designed By 정상우.
gunjoon98
투포인터, 슬라이딩 윈도우
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.