본문 바로가기

Category/Algorithm8

222-풀링 백준 222-풀링 문제 링크https://www.acmicpc.net/problem/17829 2025. 7. 29.
파이썬 2차원 배열에서의 누적합, 구간합 2차원 배열에서의 누적합(Prefix Sum)을 계산하고 이를 활용해 구간합을 효율적으로 구하는 방법은 다음과 같습니다.1. 2차원 배열의 누적합 계산2차원 배열에서의 누적합은 prefix[i][j]를 다음과 같이 정의합니다:prefix[i][j]=원점 (0,0)부터 (i,j)까지의 모든 원소의 합계산식prefix[i][j] = array[i][j] + prefix[i−1][j] + prefix[i][j−1] − prefix[i−1][j−1]array[i][j]: 현재 값prefix[i−1][j]: 위쪽 영역의 누적합prefix[i][j−1]: 왼쪽 영역의 누적합prefix[i−1][j−1]: 중복된 영역(대각선 방향)의 누적합을 빼줌2. 2차원 구간합 계산구간합을 구하고자 하는 범위가 (x1,y1)부터.. 2024. 12. 12.
우선순위 큐(Priority Queue)와 코딩 테스트 활용법 1. 우선순위 큐(Priority Queue)란?우선순위 큐는 가장 높은(또는 낮은) 우선순위를 가진 요소를 빠르게 꺼낼 수 있는 자료구조입니다.일반적인 큐(First In, First Out)와 달리, 삽입 순서가 아닌 우선순위에 따라 요소를 처리합니다.1.1 특징자동 정렬:요소가 삽입될 때, 우선순위를 기준으로 내부적으로 정렬됩니다.효율적인 접근:우선순위가 가장 높은 요소를 꺼내는 작업은 O(log N)의 시간 복잡도를 가집니다.활용 목적:우선순위가 중요한 작업을 빠르게 처리하는 데 사용됩니다. 예: 다익스트라 알고리즘, 작업 스케줄링 등.2. 파이썬에서 우선순위 큐 구현파이썬에서는 우선순위 큐를 heapq 모듈을 이용해 구현합니다.heapq는 최소 힙(min-heap) 기반으로 작동하며, 기본적으로.. 2024. 11. 28.
최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 1. LIS란 무엇인가?1.1 정의주어진 배열에서 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.부분 수열은 배열의 원소 중 일부를 선택하여 만든 수열이며, 원소의 순서는 유지되어야 합니다.1.2 예제입력 배열: [10, 20, 10, 30, 20, 50]가능한 부분 수열:[10, 20] (길이: 2)[10, 20, 30] (길이: 3)[10, 20, 30, 50] (길이: 4)결과:LIS: [10, 20, 30, 50]LIS의 길이: 42. LIS 문제 해결 방법LIS 문제를 해결하기 위해 두 가지 대표적인 접근법이 있습니다.동적 계획법 (Dynamic Programming, DP)시간 복잡도: O(N²)간단하고 직관적.작은 배열에 적합.이분 탐색 (Binary Search)시간 복잡.. 2024. 11. 28.
파라메트릭 서치(Parametric Search)란? 파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 방법입니다. 주어진 범위 내에서 특정 조건을 만족하는 값의 최대/최소를 찾기 위해 이분 탐색을 활용합니다.이 기법은 주로 이분 탐색을 변형하여 사용하며, 시간 복잡도를 크게 줄일 수 있는 강력한 방법입니다.1. 파라메트릭 서치의 핵심 아이디어최적화 문제란?어떤 값을 최대화하거나 최소화하는 문제를 의미.예: "길이 x로 나누었을 때 가능한 가장 큰 값을 찾기", "시간을 최소화하는 경우".결정 문제로 변환주어진 조건을 만족하는지 '예/아니오(True/False)'로 판단하는 문제로 바꿉니다.이 조건을 만족하는 값을 이분 탐색으로 찾아냅니다.이분 탐색 활용범위를 좁히며 조건을 만족하는 값의 최대/최소를 찾습니다.결.. 2024. 11. 28.
DP(다이나믹 프로그래밍, Dynamic Programming) DP(Dynamic Programming)란?DP는 문제를 작은 부분 문제(subproblems)로 나누어 해결하고, 그 결과를 저장하여 동일한 문제를 다시 계산하지 않도록 하는 알고리즘 설계 기법입니다. 중복되는 계산을 줄여 효율성을 극대화하는 것이 핵심입니다.언제 DP를 사용할까?DP는 문제를 해결하는 데 다음 두 가지 조건이 만족될 때 사용합니다:Overlapping Subproblems (겹치는 부분 문제):동일한 부분 문제가 여러 번 반복해서 계산됩니다.예를 들어 피보나치 수열 계산 시, 동일한 피보나치 값이 반복적으로 계산됨.Optimal Substructure (최적 부분 구조):문제의 최적 해답이 부분 문제의 최적 해답으로 구성됩니다.즉, 작은 문제들의 최적 결과를 합쳐서 전체 문제의 최적.. 2024. 11. 22.

티스토리툴바