Passwd

개요2025.05.26-[알고리즘] 최장 증가 수열(LIS) - DP에서 최장 증가 수열을 동적 계획법으로 찾는 방법을 정리했었다. 다만 동적 계획법의 경우에는 O(n^2)의 시간 복잡도를 가진다. 때문에 배열의 길이가 아주 큰 경우에는 보다 효율적인 방법을 사용할 필요가 있다.이 글에서는 최장 증가 수열을 O(log n)의 시간 복잡도로 찾을 수 있는 이분 탐색을 사용한 방법을 정리해 본다. 최장 증가 부분 수열이분 탐색을 활용할 때는 LIS를 기록하는 배열을 하나 생성한 뒤, 주어진 배열을 하나씩 살펴보면서 각 숫자가 증가수열에 들어갈 위치를 찾는 방식이다. 상세한 과정은 다음과 같다. 구현1. 이분 탐색숫자가 들어갈 위치를 찾는 이분 탐색 함수는 아래와 같다.증가수열의 숫자가 들어갈 위치는 현재..

문제최근 알고리즘 문제를 풀던 중 증가수열과 관련된 문제를 발견했다. 완전 탐색으로도 구현할 수 있지만 비효율적으로 보여 좀 더 좋은 방법을 정리해 본다. 최장 증가 부분 수열최장 증가 부분 수열(Longest Increasing Subsequence) 문제는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 부분 수열이 연속적이거나 유일할 필요는 없다. 예로 들어, 아래 그림과 같은 수열이 있다고 하자.이 수렬의 증가 부분 수열은 [1, 5], [1, 4], [2, 3, 8] 등 여럿 존재하지만, 그중 길이가 가장 긴 최장 증가수열을 찾으면 아래와 같다. 접근최장 증가 수열을 구현하는 대표적인 방법은 완전 탐색, DP를 이용하는 방법이다.수열의 한 원소 K에 대해, K에서 끝..

문제문제 : https://leetcode.com/problems/sliding-window-maximum/주어진 정수 숫자 배열과 왼쪽에서 오른쪽으로 이동하는 k 크기의 슬라이딩 윈도우가 있다고 하자. 슬라이딩 윈도우 내에는 k 개의 숫자만 존재한다. 슬라이딩 윈도우가 한 칸씩 오른쪽으로 이동할 때마다의 최댓값을 반환하라 예시 )Input: nums = [1,3,-1,-3,5,3,6,7], k = 3Output: [3,3,5,5,6,7]Explanation: Window position Max--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 ..

개요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에 바..