기록

1. 우선순위 큐란?우선순위 큐는 일반적인 큐와는 달리, 각 요소가 우선순위를 가지고 있어 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다. 예를 들어, 긴급 상황에서 긴급도가 높은 환자가 먼저 치료받는 병원의 대기열과 같은 개념을 생각할 수 있습니다.C++에서는 우선순위 큐를 구현할 수 있는 여러 가지 방법이 있으며, 여기서는 priority_queue와 multiset 두 가지를 중심으로 살펴보겠습니다.2. priority_queue를 사용한 최대 힙과 최소 힙 구현C++의 priority_queue는 기본적으로 최대 힙으로 구현되어 있어, 큰 값이 먼저 나오도록 정렬됩니다. 즉, 기본 설정에서는 큰 값이 높은 우선순위를 가지게 됩니다. 하지만 최소 힙을 만들고자 한다면 다음과 같이 설정할 ..

오늘의 학습 키워드문제1: 가장 긴 감소하는 부분 수열 (BOJ 11722)공부한 내용 정리접근 방식가장 긴 감소하는 수열을 찾기 위해서는 각 원소가 이전 원소들과의 관계를 확인하여, 그중 가장 긴 감소하는 길이를 찾아야 합니다. 단순히 원소들 간의 크기만 비교하는 것이 아니라, 현재 원소가 이전 원소들과 어떻게 연결되는지를 계산하여 가장 긴 감소하는 경로를 찾아야 합니다.dp 배열은 각 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 각 원소를 순회하면서 자신보다 작은 이전 원소를 찾아, 그 원소를 기준으로 감소 수열의 최대 길이를 갱신합니다. 이를 통해 모든 원소에 대해 가능한 가장 긴 감소 수열을 구할 수 있습니다.for (int j = 0; j sequence[i]) {..

문제 소개오늘 풀어본 문제는 LeetCode 문제 중 하나로, 각 행을 내림차순 정렬한 후 열별로 가장 큰 값을 합산하는 문제입니다. 이 문제를 풀면서 자연스럽게 정렬과 람다 함수를 어떻게 활용할 수 있는지에 대해 학습할 수 있었습니다.이 글에서는 문제 풀이 과정에서 사용한 정렬 및 람다 함수에 대해 설명하고, 기존 풀이를 어떻게 더 간결하게 개선할 수 있는지 보여드리겠습니다.문제 풀이: 열별로 최대값을 더하기이 문제의 핵심은 다음과 같습니다:각 행을 내림차순으로 정렬: 각 행에서 가장 큰 값을 쉽게 선택할 수 있도록 내림차순 정렬합니다.각 열에서 가장 큰 값을 선택하여 합산: 열별로 가장 큰 값을 찾아 결과에 더하는 방식입니다.전체 코드 풀이우선 기본적인 풀이 방법을 살펴보겠습니다. C++에서 각 행을..

오늘의 학습 키워드문제 1: Heap, Priority QueueTake Gifts from the Richest Pile - LeetCode 문제주어진 문제에서는 여러 개의 선물 더미 중에서 매 초마다 가장 많은 선물을 가진 더미를 선택하고, 그 선물의 정수 제곱근만큼 남기는 과정을 k번 반복한 뒤, 모든 더미에 남은 선물의 총합을 구하는 문제입니다. 이 문제를 해결하기 위해 heap과 priority_queue를 사용하여 접근해 보았습니다.공부한 내용 본인의 언어로 정리하기문제 1: Heap, Priority Queue1. 우선순위 큐를 사용한 풀이이 문제는 가장 큰 선물 더미를 빠르게 찾고 업데이트해야 하므로 우선순위 큐(priority queue)를 사용하여 해결했습니다. priority_queu..

오늘의 학습 키워드문제 1: priority_queueBOJ 19638: 센티와 마법의 뿅망치문제 2: 완전탐색, 약수탐색, sqrtProgrammers: 카펫공부한 내용 본인의 언어로 정리하기문제 1: priority_queue(1) priority_queue 개념과 주요 사용법priority_queueC++ STL에서 제공하는 자료구조로, 데이터가 최대 힙(Max Heap) 또는 최소 힙(Min Heap)의 형태로 관리됩니다.가장 큰 값 또는 가장 작은 값을 반복적으로 처리해야 하는 상황에서 유용.기본 동작: 내림차순으로 정렬된 힙(가장 큰 값이 top()에 위치).시간 복잡도:삽입/삭제: (O(\log N))최댓값/최솟값 접근: (O(1))주요 메서드:pq.push(value): 값을 큐에 삽입.p..

오늘의 학습 키워드문제1: max_element 활용문제 링크 - 프로그래머스 "모의고사" 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 공부한 내용 정리(1) max vs max_element C++에서는 최댓값을 구할 때 std::max와 std::max_element를 상황에 맞게 선택해서 사용할 수 있습니다. 두 함수는 비슷한 목적을 가지고 있지만, 활용 방식과 반환값에서 차이가 있습니다.항목std::maxstd::max_element기능두 값 또는 세 값 중 최댓값 반환컨테이너 내에서 최댓값을 가진 요소의 반복자 반환입력값두 값, 세 값, 또는 초기화된 값들반복자 범위(begin, end)반환..

우선순위 큐를 활용한 문제 풀이와 학습 기록문제1 : 우선순위큐, 표준 입출력 동기화 해제https://www.acmicpc.net/problem/2075학습 과정: 다양한 시도와 결과문제1 : 우선순위큐, 표준 입출력 동기화 해제(1) 시도1: 메모리 초과모든 데이터를 우선순위 큐에 삽입한 후, (N)번째로 큰 값을 찾는 방식으로 접근했습니다.문제점: 메모리 초과 발생.총 (N \times N = 2,250,000)개의 정수를 큐에 저장해야 하므로 메모리 사용량이 (12)MB를 초과.각 정수가 (4)바이트라면 (9)MB가 필요하지만, 우선순위 큐의 내부 관리 메모리까지 고려하면 제약을 넘습니다.모든 데이터를 저장하기보다는 문제를 해결하는 데 필요한 최소한의 데이터만 유지해야 한다.#include #in..

문제 소개https://www.acmicpc.net/problem/2212 : 그리디고속도로 위에 여러 개의 센서를 설치하고, 센서에서 수집한 자료를 분석하기 위해 몇 개의 집중국을 세워야 합니다. 예산상의 제약 때문에 최대한 적은 영역을 커버할 수 있도록 집중국을 배치해야 합니다. 이 문제에서는 그리디 알고리즘을 이용하여 전체 커버리지의 길이 합을 최소화할 수 있도록 집중국을 배치하는 방법을 배웁니다. 또한, 문제를 해결하면서 set과 vector의 사용법, 정렬된 자료구조를 다루는 방법을 학습했습니다.학습 내용 정리1. 그리디 알고리즘그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 반복하여 전체 문제를 해결하는 방식입니다. 이 문제에서는 "가장 긴 거리 간격을 우선적으로 제거하여 구간을 최소화"하..