Passwd

[알고리즘] 슬라이딩 윈도우

개요2025.05.19-[알고리즘] 투 포인터에서 배열을 효율적으로 탐색하는 방법 중 하나인 투 포인터 알고리즘에 대해서 알아보았다. 이번 글에서는 투 포인터 알고리즘과 함께 언급되는 슬라이딩 윈도우라는 알고리즘에 대해서 알아본다. 슬라이딩 윈도우슬라이딩 윈도우란 네트워크에서 사용하던 알고리즘으로 고정 사이즈의 윈도우가 이동하면서 윈도우 내의 데이터를 이용해 문제를 풀이하는 알고리즘이다.교집합의 정보를 공유하고 차이가 나는 양 끝의 원소만 갱신하는 방식으로 구현하는데, 배열 내 일정 범위의 값을 비교할 때 유용하다. 투 포인터 알고리즘과 연동하여 많이 사용한다. 투 포인터 VS 슬라이딩 윈도우슬라이딩 윈도우와 유사한 알고리즘은 투 포인터 알고리즘이 존재한다. 다만 부분 배열의 길이가 가변적인 ..

[알고리즘] 투 포인터

개요알고리즘 문제를 풀어내다 보면 간혼 투 포인터 알고리즘이라는 단어를 접할 때가 있다. 배열을 순회할 때 사용하는 것 같은데, 이번 글에서는 투 포인터 알고리즘에 대한 개념을 알아본다 투 포인터 알고리즘1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘으로, 보다 쉽게 표현하면 리스트에 순차적으로 접근할 때 두 점의 위치를 기록하면서 처리하는 알고리즘이라고 할 수 있다.특정 조건을 만족하는 부분 구간을 효율적으로 탐색할 수 있기 때문에 이중 for문으로 처리해 시간복잡도가 O(N^2)인 작업을 O(N)으로 줄일 수 있다. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용한다. 구현 방식일반적으로 투 포인터 알고리즘은 다음과 같이..

개요최근 이차원 배열을 나선 순환하는 알고리즘 문제를 풀었다. 방법은 알았는데, 그걸 실제로 구현하는 것에서 약간 어려움이 있었어서 적절한 구현 방법을 정리해두려고 한다. 이 글에서 구현하고자 하는 것은 n 행, m 열로 이루어진 이차원 배열을 나선 순회하는 코드이다. 출발 시 이동 방향은 오른쪽이다. 방법아이디어는 다음과 같다.각 방향 별 끝 갑을 초기화한다.끝에 다다랐을 때 끝 값을 갱신한다.구현해 보자. 1. 배열 및 끝 값 초기화# n행 m열 배열 초기화spiral_list = [[0 for _ in range(m)] for _ in range(n)]# 방향 별 끝 값lp_left_side = 0lp_right_side = m - 1lp_up_side = 1 # i == 0 부터 순회 하므로..

문제문제 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/N개의 정수로 구성된 비어 있지 않은 배열 A가 있다. 배열 A의 연속된 요소는 도로 위의 연속된 자동차를 나타내며, 배열 A에는 0 또는 1로만 구성되어 있다. 이때, 0은 동쪽으로 이동하는 차량을 나타내고 1은 서쪽으로 이동하는 차량을 나타낸다.목표는 지나가는 차를 세는 것으로, P가 동쪽으로 이동하고 Q가 서쪽으로 이동할 때 0 ≤ P 한 쌍의 차 (P, Q)가 지나간다고 한다.예로 들어 아래와 같은 배열 A가 있다고 하자. A[0] = 0 A[1] = 1 A[2] = 0 A[3] = 1 A[4] = 1지나가는 차의 쌍은 (0, 1), (0, 3), ..

문제문제 : https://www.acmicpc.net/problem/1926어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.   풀이BFS 방식으로 풀어낼 수 있는 문제이다. 1. 입력값  초기화입력으로 받는 n과 m, 그리고 그림을 초기화한다.n, m = map(int, sys.stdin.readline().split())graph = [list(map(int, sys.stdin.readline().split())) for i in ran..

문제문제 : https://leetcode.com/problems/monthly-transactions-i/description/?envType=study-plan-v2&envId=top-sql-50+---------------+---------+| Column Name | Type |+---------------+---------+| id | int || country | varchar || state | enum || amount | int || trans_date | date |+---------------+---------+id는 테이블의 PK이고, 이 테이블은 들어오는 트랜잭션에 대한 정보를 가지고 ..

문제문제 : https://app.codility.com/programmers/lessons/1-iterations/binary_gap/양의 정수 N에서 바이너리 갭은 이진수에서 양 끝이 1로 둘러싸인 연속된 0의 최대 수이다.예로 들어, 숫자 9는 이진수로 1001이고, 길이가 2인 바이너리 갭을 가진다. 숫자 529는 이진수로 1000010001이며, 길이가 4이고 3인 두 개의 바이너리 갭을 가진다. 숫자 20인 이진수로 10100이고 길이가 1인 바이너리 갭을 가지고, 숫자 15는 이진수로 1111이고 바이너리 갭을 갖고 있지 않다. 숫자 32 또한 이진수로 100000으로 바이너리 갭을 가지고 있지 않다. 양의 정수 N이 주어지면 가장 긴 바이너리 갭의 길이를 반환하는 함수를 작성하라. N에 바..

문제문제 : https://leetcode.com/problems/primary-department-for-each-employee/?envType=study-plan-v2&envId=top-sql-50다음과 같은 스키마를 가진 테이블 Employee가 존재한다.+---------------+---------+| Column Name | Type |+---------------+---------+| employee_id | int || department_id | int || primary_flag | varchar |+---------------+---------+employee_id는 직원의 ID이고,  department_id는 직원이 속한 부서의 ID이다. employ..

문제문제 : https://leetcode.com/problems/is-subsequence/?envType=study-plan-v2&envId=leetcode-75문자열 s, t가 주어질 때 s가 T의 하위 문자열이면 True를 반환하고, 하위 문자열이 아니면 False를 반환하는 프로그램을 작성하라.여기서 하위 문자열이란, 나머지 문자의 상대적인 위치를 방해하지 않고 일부 문자열을 삭제하여 원래 문자열에서 형성되는 새로운 문자열을 말한다.  예시 )- s가 abc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이다.- s가 axc이고 t가 ahbgdc인 경우, t는 s의 하위 문자열이 아니다.   풀이정규표현식 패턴을 만들어, t가 패턴에 일치하는지 확인하는 방식으로 구현했다.예로 들어 s가 a..

문제문제 : https://leetcode.com/problems/average-selling-price/description/?envType=study-plan-v2&envId=top-sql-50 테이블 : Prices+---------------+---------+| Column Name | Type |+---------------+---------+| product_id | int || start_date | date || end_date | date || price | int |+---------------+---------+(product_id, start_date, end_date)는 테이블의 PK이다.테이블의 각 행은 sta..