기록

문제백준 22856번 - 트리 순회유사 중위 순회를 수행하면서 이동한 횟수를 계산하는 문제입니다.유사 중위 순회는 다음 규칙을 따릅니다:현재 노드의 왼쪽 자식 노드가 존재하고 방문하지 않았다면, 왼쪽 자식으로 이동합니다.그렇지 않고 오른쪽 자식 노드가 존재하고 방문하지 않았다면, 오른쪽 자식으로 이동합니다.그렇지 않고 현재 노드가 중위 순회의 마지막 노드라면, 탐색을 종료합니다.그렇지 않다면 부모 노드로 이동합니다.중위 순회를 따르는 방식으로 이동하며, 이동한 횟수를 출력합니다.풀이1) 문제풀이트리를 left와 right 배열로 표현하여, 각 노드의 왼쪽과 오른쪽 자식 정보를 저장합니다.중위 순회의 마지막 노드를 findLastNode 함수로 찾아냅니다.마지막 노드는 오른쪽 자식이 없을 때까지 오른쪽으로..

문제백준 20207 - 달력여러 일정이 주어질 때, 이를 달력에 배치하고 차지하는 직사각형 면적을 구하는 문제입니다. 일정은 시작일과 종료일로 주어지며, 겹치는 일정이 있는 경우 이를 높이로 표현합니다. 이를 통해 달력의 전체 면적(폭 × 높이)을 계산하는 것이 목표입니다.풀이1) 일정 마킹날짜를 기준으로 일정의 시작과 끝을 배열에 기록합니다.시작일에는 +1, 종료일 다음 날에는 -1을 기록하여 일정의 변화를 마킹합니다.이를 통해 특정 날짜에 일정이 시작되고 끝나는 구간을 표시할 수 있습니다.for (int[] pair : eventList) { int start = pair[0]; int end = pair[1]; board[start]++; board[end + 1]--;} 예를..

문제https://www.acmicpc.net/problem/14719이번 글에서는 백준 온라인 저지의 14719번 문제, "빗물" 문제를 다뤄보겠습니다.2차원 세계에 블록이 쌓여있고, 비가 내린 후 고일 수 있는 물의 총량을 계산하는 문제입니다.풀이문제의 핵심 아이디어어떤 칸에 고일 수 있는 물의 양은 다음과 같이 계산할 수 있습니다:해당 칸에서 왼쪽 방향으로 가장 높은 블록과 오른쪽 방향으로 가장 높은 블록 중 더 낮은 값을 찾습니다.그 값에서 현재 칸의 블록 높이를 뺀 값이 고일 수 있는 물의 양입니다.식으로 나타내면:물의 양 = Math.min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 칸의 높이위 계산을 모든 칸에 대해 수행한 후, 이를 모두 더하면 전체 고인 물의 양을 구할 수 있습니다.P..

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..